Insane Curves - Crypto

Points: 500 | Flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6} | Solved by: Smothy @ 0xN1umb

what we got

500 point crypto chall, two files: description.txt and val.txt. description says something about a "Too Genus Curve" with equation y² = f(x) where f(x) is degree 6. so we're dealing with a genus 2 hyperelliptic curve and the challenge author thinks he's a genius lmao

val.txt gives us:

• prime p (257-bit)
• polynomial coefficients f_coeffs (degree 6)
• generator divisor G in Mumford representation (u, v)
• public key divisor Q = k * G
• encrypted flag enc_flag (32 bytes hex)

classic HECDLP setup - find private key k such that Q = k * G on the Jacobian, then decrypt.

the solve

step 1: check the prime

first thing i always do with crypto challs - look at the prime. this one ends in ...027199999999. sus af ngl

p+1 is INSANELY smooth. largest prime factor is literally 31. if you know anything about elliptic curves, a smooth p+1 screams supersingular - and supersingular = dead.

step 2: check the polynomial

f(x) factors over GF(p) into three quadratics:

this means the Jacobian is decomposable - it splits into a product of elliptic curves. but honestly we don't even need to decompose it, because...

step 3: confirm supersingular

for a supersingular genus 2 curve, the Jacobian order is (p+1)². quick check in SageMath:

order_candidate = (p + 1)^2
test = order_candidate * G_div   # scalar mult on Jacobian
# Result: identity element!

(p+1)² * G = 0. confirmed supersingular. the entire group order is (p+1)² which factors into primes no larger than 31. this is comically weak.

step 4: pohlig-hellman go brrrr

since order(G) = p+1 = 2²³ · 3¹⁴ · 5⁸ · 7⁴ · 11¹⁰ · 13¹⁰ · 17⁹ · 19⁶ · 23⁵ · 29 · 31⁴

we just run Pohlig-Hellman on the Jacobian. for each prime power q^e dividing the order:

1. project G and Q to the subgroup of order q^e
2. extract each digit in base q by brute force (max prime is 31 so this is instant)
3. CRT everything together

for (q, e) in order_factors:
    pe = q^e
    cofactor = order_G // pe
    G_sub = cofactor * G_div
    Q_sub = cofactor * Q_div

    gamma = (pe // q) * G_sub  # order q element
    h = Q_sub
    k_mod = 0

    for j in range(e):
        scale = pe // q^(j + 1)
        hj = scale * h
        # brute force d in range(q) - max 31 iterations lol
        for d in range(q):
            if d * gamma == hj:
                k_mod += d * q^j
                h = h - d * q^j * G_sub
                break

    residues.append(k_mod)
    moduli.append(pe)

k = CRT(residues, moduli)

output:

verified: k * G == Q on the Jacobian. ez clap

step 5: decrypt

tried a few key derivation methods and SHA256(str(k)) XOR enc_flag gave us clean ascii:

key = hashlib.sha256(str(k).encode()).digest()
flag = bytes(a ^ b for a, b in zip(enc_flag, key))
# b'BITSCTF{7h15_15_w4y_2_63nu5_6n6}'

flag

BITSCTF{7h15_15_w4y_2_63nu5_6n6}

"this is way 2 genus gng" - yeah fr it was way too genus. your friend ain't no genius if he's using a supersingular genus 2 curve with a 31-smooth group order lmaooo

tl;dr

1. genus 2 hyperelliptic curve DLP
2. p+1 is 31-smooth (supersingular curve)
3. f(x) splits into three quadratics (decomposable Jacobian)
4. Jacobian order = (p+1)² → all prime factors ≤ 31
5. Pohlig-Hellman trivially solves the DLP
6. SHA256(str(k)) XOR enc_flag = flag

the "insane" part was how insanely weak the parameters were ngl

smothy out ✌️