Challenge Description#

Genus-2 hyperelliptic curve challenge. Given val.txt and description.txt with curve parameters and ciphertext.

From val.txt:

• Prime field: p = 129403459552990578380563458675806698255602319995627987262273876063027199999999
• Curve: y^2 = f(x), deg(f)=6
• Public Jacobian elements G = (G_u, G_v) and Q = (Q_u, Q_v) in Mumford representation
• Ciphertext: enc_flag=f6ca1f88bdb8e8dda17861b91704523f914564888c7138c24a3ab98902c10de5

Analysis#

The critical observation was that G is annihilated by p+1:

(p+1) * G = O

and p+1 is extremely smooth:

$p+1 = 2^{23}\cdot 3^{14}\cdot 5^8\cdot 7^4\cdot 11^{10}\cdot 13^{10}\cdot 17^9\cdot 19^6\cdot 23^5\cdot 29\cdot 31^4$

That makes the discrete log in <G> solvable with Pohlig–Hellman. Target relation: $Q = [x]G$

Solution#

Implement genus-2 Jacobian arithmetic for y^2=f(x) (Cantor composition/reduction). Work with divisor-class equality (compare via (A - B) == identity, not just raw (u,v) tuple equality). Solve DLP modulo each prime power of p+1 with PH, then recombine with CRT to recover full x.

File used: solve_insane_curves.py

#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

p=129403459552990578380563458675806698255602319995627987262273876063027199999999
f=[87455262955769204408909693706467098277950190590892613056321965035180446006909,
   12974562908961912291194866717212639606874236186841895510497190838007409517645,
   11783716142539985302405554361639449205645147839326353007313482278494373873961,
   55538572054380843320095276970494894739360361643073391911629387500799664701622,
   124693689608554093001160935345506274464356592648782752624438608741195842443294,
   52421364818382902628746436339763596377408277031987489475057857088827865195813,
   50724784947260982182351215897978953782056750224573008740629192419901238915128]

G0=([95640493847532285274015733349271558012724241405617918614689663966283911276425,1],
    [23400917335266251424562394829509514520732985938931801439527671091919836508525])
Q0=([34277069903919260496311859860543966319397387795368332332841962946806971944007,
     343503204040841221074922908076232301549085995886639625441980830955087919004,1],
    [102912018107558878490777762211244852581725648344091143891953689351031146217393,
     65726604025436600725921245450121844689064814125373504369631968173219177046384])

ct=bytes.fromhex("f6ca1f88bdb8e8dda17861b91704523f914564888c7138c24a3ab98902c10de5")
GENUS=2

def norm(a):
    a=[x%p for x in a]
    while len(a)>1 and a[-1]==0:a.pop()
    return a

def deg(a):return len(a)-1

def padd(a,b):
    n=max(len(a),len(b));c=[0]*n
    for i in range(n): c[i]=((a[i] if i<len(a) else 0)+(b[i] if i<len(b) else 0))%p
    return norm(c)

def psub(a,b):
    n=max(len(a),len(b));c=[0]*n
    for i in range(n): c[i]=((a[i] if i<len(a) else 0)-(b[i] if i<len(b) else 0))%p
    return norm(c)

def pmul(a,b):
    c=[0]*(len(a)+len(b)-1)
    for i,x in enumerate(a):
        if x:
            for j,y in enumerate(b):
                if y:c[i+j]=(c[i+j]+x*y)%p
    return norm(c)

def inv(x):return pow(x,p-2,p)
def pscale(a,k):return norm([(x*k)%p for x in a])
def monic(a):
    a=norm(a)
    return pscale(a,inv(a[-1])) if a!=[0] else [0]

def divmodp(a,b):
    a=norm(a[:]);b=norm(b)
    if b==[0]:raise ZeroDivisionError
    if deg(a)<deg(b):return [0],a
    q=[0]*(deg(a)-deg(b)+1);ib=inv(b[-1])
    while a!=[0] and deg(a)>=deg(b):
        d=deg(a)-deg(b);coef=a[-1]*ib%p;q[d]=coef
        for i,bi in enumerate(b):a[i+d]=(a[i+d]-coef*bi)%p
        a=norm(a)
    return norm(q),norm(a)

def pmod(a,m): return divmodp(a,m)[1]
def divexact(a,b):
    q,r=divmodp(a,b)
    if r!=[0]:raise ValueError
    return q

def xgcd(a,b):
    a=norm(a); b=norm(b)
    s0,s1=[1],[0]; t0,t1=[0],[1]; r0,r1=a,b
    while r1!=[0]:
        q,r=divmodp(r0,r1)
        r0,r1=r1,r
        s0,s1=s1,psub(s0,pmul(q,s1))
        t0,t1=t1,psub(t0,pmul(q,t1))
    il=inv(r0[-1])
    return pscale(r0,il),pscale(s0,il),pscale(t0,il)

ID=([1],[0])

def normalize(D):
    u,v=D
    u=monic(u);v=pmod(v,u)
    return u,v

def reduction(a,b):
    a,b=normalize((a,b))
    a2=monic(divexact(psub(f,pmul(b,b)),a))
    b2=pmod(pscale(b,p-1),a2)
    if deg(a2)==deg(a):
        return (a2,b2)
    elif deg(a2)>GENUS:
        return reduction(a2,b2)
    return normalize((a2,b2))

def comp(D1,D2):
    a1,b1=normalize(D1); a2,b2=normalize(D2)
    if a1==a2 and b1==b2:
        d,h1,h3=xgcd(a1,pscale(b1,2))
        a=pmul(divexact(a1,d),divexact(a1,d))
        b=pmod(padd(b1,pmul(h3,divexact(psub(f,pmul(b1,b1)),d))),a)
    else:
        d0,_,h2=xgcd(a1,a2)
        if d0==[1]:
            a=pmul(a1,a2)
            b=pmod(padd(b2,pmul(pmul(h2,a2),psub(b1,b2))),a)
        else:
            d,l,h3=xgcd(d0,padd(b1,b2))
            a=divexact(pmul(a1,a2),pmul(d,d))
            b=pmod(padd(padd(b2,pmul(pmul(pmul(l,h2),psub(b1,b2)),divexact(a2,d))),
                        pmul(h3,divexact(psub(f,pmul(b2,b2)),d))),a)
    a=monic(a)
    return reduction(a,b) if deg(a)>GENUS else normalize((a,b))

def addD(A,B):
    if A==ID:return normalize(B)
    if B==ID:return normalize(A)
    return comp(A,B)

def negD(D):
    u,v=normalize(D)
    return (u,pmod(pscale(v,p-1),u))

def subD(A,B):return addD(A,negD(B))

def is_id(D):
    u,v=normalize(D)
    return u==[1] and v==[0]

def eqcls(A,B):
    return is_id(subD(A,B))

def smul(k,D):
    R=ID;Q=normalize(D)
    while k>0:
        if k&1:R=addD(R,Q)
        Q=addD(Q,Q)
        k//=2
    return R

def dlog_prime_power(Gi,Qi,l,e):
    x=0
    base=smul(l**(e-1),Gi)
    table=[]
    cur=ID
    for d in range(l):
        table.append(cur)
        cur=addD(cur,base)
    for j in range(e):
        R=subD(Qi,smul(x,Gi))
        C=smul(l**(e-1-j),R)
        digit=None
        for d,val in enumerate(table):
            if eqcls(val,C):
                digit=d
                break
        if digit is None:
            raise ValueError(f"No digit for l={l}, j={j}")
        x += digit*(l**j)
    return x

def crt(residues, moduli):
    x=0; M=1
    for r,m in zip(residues,moduli):
        k=((r-x)%m)*pow(M,-1,m)%m
        x += M*k
        M *= m
    return x%M

G=normalize(G0)
Q=normalize(Q0)
N=p+1

assert is_id(smul(N,G))

fac=[(2,23),(3,14),(5,8),(7,4),(11,10),(13,10),(17,9),(19,6),(23,5),(29,1),(31,4)]
res=[]; mods=[]
for l,e in fac:
    m=l**e
    Gi=smul(N//m,G)
    Qi=smul(N//m,Q)
    xi=dlog_prime_power(Gi,Qi,l,e)
    res.append(xi)
    mods.append(m)

x=crt(res,mods)
assert eqcls(smul(x,G),Q)

print("x =", x)

# key derivation that matches challenge encryption
key = hashlib.sha256(str(x).encode()).digest()
pt = bytes(a^b for a,b in zip(ct,key))

print("plaintext:", pt)
print("flag:", pt.decode())

Run:

python3 solve_insane_curves.py

Output:

x = 91527621348541142496688581834442276703691715094599257862319082414424378704170
flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6}