Alpaca CTF 2026: Equation Cipher

Challenge Information

Summary

The flag is encoded as an expanded degree-30 polynomial — the product of 30 linear factors (pᵢ · x − ord(cᵢ)), one per flag character. Each prime pᵢ is the i-th prime, and each ord(cᵢ) is the ASCII value of the corresponding character. Factoring the polynomial over ℚ recovers all 30 (prime, char) pairs directly. The one wrinkle: sympy’s factor_list absorbs small leading coefficients into the polynomial’s content (here, 33 = 3 × 11), leaving two factors monic — those two characters must be recovered by multiplying the integer root back through each candidate prime.

Challenge

chal.sage

import os

FLAG = os.getenv("FLAG", "Alpaca{REDACTED}")
ps = prime_range(200)          # all primes < 200 (46 primes)
assert len(FLAG) <= len(ps)
var("x")
print(expand(prod(p*x - ord(c) for p, c in zip(ps, FLAG))))

output.txt — a single expanded polynomial of degree 30 with large integer coefficients.

The polynomial is:

P(x) = ∏ᵢ₌₀²⁹ (pᵢ · x − ord(FLAG[i]))

where pᵢ is the i-th prime (starting from p₀ = 2) and ord(c) is the ASCII code of flag character c.

What We Have

The flag starts with Alpaca{, which means the first seven factors are: (2x−65)(3x−108)(5x−112)(7x−97)(11x−99)(13x−97)(17x−123) — literally spelling out Alpaca{ in the leading coefficients and roots.

Key Observations

1. Degree Reveals Flag Length

The product of N linear factors has degree N. The output polynomial has degree 30, so len(FLAG) = 30. The primes used are ps[:30] = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.

Sanity check: the leading coefficient of P(x) equals ∏(pᵢ for i in 0..29).

2. Each Character is a Rational Root

The root of factor (pᵢ · x − ord(cᵢ)) is x = ord(cᵢ)/pᵢ. Factoring P(x) over ℚ recovers all 30 linear factors; from each factor (a·x + b) we read a = prime, b = −ord(char).

3. Naïve Root-Searching Fails Silently

A tempting approach: for each prime pᵢ, iterate over printable ASCII values c and check if P(c/pᵢ) = 0. This fails because different factors can share the same rational root.

Example: FLAG[4] is 'c' (ord=99, prime=11), giving root 99/11 = 9.
But 9 = 18/2 = 27/3 = 45/5 = 63/7 as well — so checking primes 2, 3, 5, 7 with characters whose ord divides to 9 also evaluates to zero. The search returns the wrong first hit for those primes.

The fix is to factor the polynomial so each linear factor is uniquely matched to its prime coefficient.

Solution

Factoring a degree-30 polynomial over ℚ is fast (< 0.1 s with sympy). Each factor comes back with its original leading coefficient (the prime), allowing direct lookup.

from sympy import Symbol, Poly, factor_list, primerange, QQ

x = Symbol('x')

# Coefficients from output.txt (degree 30 down to degree 0)
coeffs = [
    31610054640417607788145206291543662493274686990,
    -5546471172446267199908288813955709803894916863891,
    433377935277645564002255944149331102759097629016976,
    -20142037483382706903735824573121411902072690581870353,
    628544975730398871952578254972056210769133972308504238,
    -14103203499469477196397673041977273198535463720813511496,
    237936120625135634298766663271669339974273400622139140960,
    -3115189058113046486649615994424685527137213009829786565804,
    32401871716234905249787787204642478781456178620700250924372,
    -272588704925637211917704819950233127485929706270916078270242,
    1880938145459784850972701297509835120940908214418826398760504,
    -10763595238894425529022977468248701808343818896426097084206310,
    51526609793195732269526279558164302129809486380649140800756516,
    -207752493375686531062097899074646509781607134964754126545962428,
    709168993683880913589126689552976392852747044942203144814007928,
    -2057178862028324030398361920847595153200891849084132353697223756,
    5083636482416115163931720576158038567306017017139089684379461950,
    -10714500940878830033395315629846816330361955820426708798364298979,
    19258823542165940827067059561652735453012561234462519554892085912,
    -29480419871976010166463893203536030034901787891137207651668574577,
    38320241257145304710248587679172535167064005500317650323655681934,
    -42103071630188436582653862079777246995177378998686214418442724964,
    38840465015774891376336339299943076877369920237254794599199115720,
    -29804097541883980161879878306614825893854901879785989447615831200,
    18778736485528317301569303423227100599378393981146669277915712000,
    -9541503279865279339054547002680737522226346240120256811709440000,
    3809937603952003187190136727046451246385385383157072044908800000,
    -1150226737694531474138472921561694773373313260537777208448000000,
    246633734202321645382654677996809754173436069507161134080000000,
    -33448067898412413588890754448308946426268551579304755200000000,
    2155435801475328219020318065287659822070611098828800000000000,
]

ps = list(primerange(200))
ps_set = set(ps)

poly = Poly(coeffs, x, domain=QQ)
content, factors = factor_list(poly)   # fast — under 0.1s

flag_chars = {}

for fac, mult in factors:
    fac_coeffs = fac.all_coeffs()
    if len(fac_coeffs) == 2:
        a, b = fac_coeffs          # factor is (a·x + b)
        p_val = int(a)
        c_val = int(-b)            # root = c_val / p_val
        if p_val in ps_set and 0 < c_val < 128:
            # Normal case: leading coefficient is the prime directly
            idx = ps.index(p_val)
            flag_chars[idx] = chr(c_val)
        else:
            # Monic factor (a=1): prime was absorbed into `content`
            # Recover by trying each prime: char_ord = root * prime
            root = c_val
            for p in ps[:30]:
                c = root * p
                if 32 <= c <= 126:
                    idx = ps.index(p)
                    if idx not in flag_chars:
                        flag_chars[idx] = chr(c)

n = max(flag_chars.keys()) + 1
print(''.join(flag_chars.get(i, '?') for i in range(n)))
# → Alpaca{ok_next_Elliptic_Curve}

The Content Wrinkle — Why Two Factors Went Monic

sympy.factor_list returns polynomials in primitive form: it pulls out the integer GCD of all coefficients (the content) and returns the factored polynomial with content separated. When a linear factor (p·x − c) has a leading coefficient p that divides evenly into the content, sympy normalises it to (x − c/p) (monic form) and folds p into the content value.

Here, two factors were simplified:

Total content = 3 × 11 = 33.

To recover the prime for a monic factor, multiply the integer root back by each candidate prime and check if the result is a printable ASCII ordinal:

• Root = 36, try p=3: 36 × 3 = 108 = 'l' ✓ → FLAG[1] = 'l'
• Root = 9, try p=11: 9 × 11 = 99 = 'c' ✓ → FLAG[4] = 'c'

Approach Comparison

Flag

Alpaca{ok_next_Elliptic_Curve}

The flag text — “ok_next_Elliptic_Curve” — is the author’s teaser: subsequent challenges in this series will likely involve Elliptic Curve cryptography over finite fields, a natural next step from polynomial arithmetic over ℚ.

Key Takeaways

• Factor, don’t hunt roots: When a polynomial is constructed as ∏(pᵢ·x − cᵢ) with known distinct primes pᵢ, factoring over ℚ directly matches each factor to its prime. Independent root search is fragile — rational roots from different factors can collide.
• Sympy’s factor_list normalises to primitive form: The returned content absorbs common integer factors from leading coefficients. Always check content when factored leading coefficients don’t match expected primes — multiply roots back through candidate primes to recover the originals.
• Degree = message length: In this encoding, degree is a free side-channel leaking the exact flag length before any other analysis.
• The structure is the cipher: The title “Equation Cipher” and the construction (2x−A)(3x−l)(5x−p)(7x−a)(11x−c)(13x−a) literally spell Alpaca in the factor roots. The algebraic structure exposes the message under polynomial factorization.
• SageMath vs. sympy: The challenge is written in SageMath, but the solution can be implemented entirely in Python with sympy — no SageMath installation required.

Tools Used

• Python 3 + sympy: Polynomial factorization over ℚ (factor_list with domain=QQ)
• SageMath (reference): prime_range, expand, prod for understanding the challenge construction

References

• sympy factor_list docs: https://docs.sympy.org/latest/modules/polys/reference.html#sympy.polys.factortools.dup_factor_list
• Rational root theorem (Wikipedia): https://en.wikipedia.org/wiki/Rational_root_theorem
• Polynomial content and primitive part: https://en.wikipedia.org/wiki/Primitive_part_and_content
• SageMath prime_range: https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html