From Nothing

Challenge summary

chall.sage works over a genus-5 hyperelliptic curve H: y^2 + y = x^11 over GF(p), with p chosen so that p = 1 (mod 11) (giving the curve’s Jacobian J complex multiplication by Z[zeta_11]). A random point D = k*J(Q) is formed for a secret scalar k and a secret point Q, but only D’s Mumford “u-polynomial” (D_u, degree 5) is printed — the v-polynomial is withheld (“the wise seek not what is present, but what is absent”). The scalar e = D_v(0) (the constant term of the withheld v) is then used to compute ct = e * J(P), where P = H.lift_x(flag_as_integer), and the full Mumford representation of ct (u and v) is given. We must recover e, then #J(F_p) (the group order), then compute e^{-1}*ct to get back P and its x-coordinate = the flag integer.

Step 1: recovering the missing v of D

Sage’s HyperellipticCurve(x^11, 1) means y^2 + y = x^11 (h=1, f=x^11), so the Mumford condition on a reduced divisor (u, v) is

v^2 + v = x^11   (mod u(x))

Substituting w = 2v+1 (completing the square) turns this into

w^2 = 4*x^11 + 1   (mod u(x))

D_u factors over GF(p) into 3 squarefree, coprime irreducible factors (one linear, two quadratic). For each factor we can take a square root of 4x^11+1 in the corresponding residue field (GF(p) or GF(p^2), via Tonelli-Shanks), then CRT the per-factor sign choices back together mod u(x). That gives 2^3 = 8 candidate w’s (equivalently v’s, and hence 8 candidate e = v(0) values, pairing up as e and p-1-e since flipping every sign negates w, i.e. v -> -1-v).

Step 2: the group order via CM, not point counting

Genus 5 with a 512-bit p makes ordinary point counting (Kedlaya/Schoof) infeasible. But p = 1 (mod 11) gives J complex multiplication by the cyclotomic ring Z[zeta_11] (degree 10 = 2*genus), so

#J(F_p) = Norm_{K/Q}(1 - pi)

for a Frobenius element pi in Z[zeta_11] with pi * conj(pi) = p. Rather than compute Jacobi/Gauss sums, pi can be found directly:

• p splits into 10 primes above it in Z[zeta_11], one for each primitive 11th root of unity r mod p: prime_r = (p, zeta - r). Complex conjugation sends r -> r^{-1} mod p, pairing the 10 primes into 5 conjugate pairs.
• For each of the 2^5 = 32 ways to pick one prime from each pair (a “CM type”), the product ideal has an explicit Z-basis built from p and the roots r, and the norm form Tr(a * conj(a)) on that lattice is an integral positive-definite quadratic form of rank 10.
• LLL-reduce that form’s Gram matrix (python-flint, fmpz_mat.lll with rep=‘gram’) and enumerate (Fincke-Pohst) all lattice vectors with Tr(aconj(a)) = 2p, keeping exactly those a = pi with pi*conj(pi)=p.
• This yields 72 distinct candidate values of Norm(1-pi) — one for each Galois orbit — each a ~2557-bit integer.

Step 3: pin down the real order & decrypt

Implemented Cantor’s algorithm generically (for h != 0, genus 5) using python-flint’s fmpz_mod_poly for the modular polynomial gcd/xgcd/divmod needed. For each of the 72 candidate orders N, check N * ct == O in J; exactly one N annihilates ct.

With N known, for each of the 8 candidate e’s compute e^{-1} mod N (skip the ones with gcd(e,N) != 1) and P = e^{-1} * ct. Exactly one candidate gives a linear Mumford u-polynomial u(x) = x - flag_int (the others give degree-5 u, i.e. nonsense/garbage points) — its root is the flag integer. Converting to bytes gives the flag, confirmed by re-encrypting (e * J(H.lift_x(flag_int)) == ct exactly).

Lesson

A withheld half of a Mumford representation isn’t really hidden: for a squarefree u(x), the compatible v(x) values form a small (2^{#factors}) enumerable set once you factor u and take square roots per factor. And “genus 5 over a 512-bit prime” only looks infeasible for order computation until you notice p was deliberately chosen (p = 1 mod n) to give the curve CM by Z[zeta_n] — turning a generically-hard point-counting problem into an LLL/lattice-enumeration problem in the CM order.