494 words
2 minutes
BITSCTF 2026 - Insane Curves - Cryptography Writeup
Category: Cryptography
Flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6}
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)andQ = (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 = Oand p+1 is extremely smooth:
That makes the discrete log in <G> solvable with Pohlig–Hellman. Target relation:
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 python3from Crypto.Cipher import AESfrom Crypto.Util.Padding import unpadimport hashlib
p=129403459552990578380563458675806698255602319995627987262273876063027199999999f=[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 encryptionkey = 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.pyOutput:
x = 91527621348541142496688581834442276703691715094599257862319082414424378704170flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6} BITSCTF 2026 - Insane Curves - Cryptography Writeup
https://fuwari.vercel.app/posts/38/bitsctf-2026-insane-curves-cryptography-writeup/