BITSCTF Crypto Writeup (First-Person) - Too Genus Curve¶
I solved this challenge by turning the genus-2 Jacobian discrete log into two elliptic-curve discrete logs, then using the recovered scalar to decrypt the flag ciphertext.
1. What I Got¶
I was given:
- A prime field
p - A hyperelliptic curve
y^2 = f(x)withdeg(f)=6 - Two Jacobian divisors in Mumford representation:
G = (G_u, G_v)Q = (Q_u, Q_v)enc_flagas hex
The hint text said the curve parameters looked "insane", so I expected a structural weakness rather than brute-force DLP.
2. My Main Observation¶
I computed a shift x -> X + t with:
t = -f5 / (6*f6) mod p
When I substituted this shift into f, the odd coefficients vanished, and the polynomial became:
f(X+t) = 1 + a*X^6
This is huge: the curve becomes
C': y^2 = 1 + aX^6
which is bi-elliptic and splits via maps to elliptic curves:
E1: V^2 = aU^3 + 1with map(X,Y) -> (U,V) = (X^2, Y)E2: V^2 = U^3 + awith map(X,Y) -> (U,V) = (X^-2, Y*X^-3)
So instead of solving one hard genus-2 DLP directly, I solved two elliptic DLPs.
3. How I Mapped Mumford Divisors¶
For degree-1 divisor u(x)=x-x0, mapping is direct from the point.
For degree-2 divisor u(x)=x^2+u1x+u0, I worked in Fp2 = Fp[r]/(r^2+u1*r+u0), took one root r, evaluated y=v(r), mapped the point to E1/E2, then added Frobenius conjugates to trace down to Fp.
That gave me points:
G1, Q1onE1G2, Q2onE2
4. Solving the DLP¶
I used Pohlig-Hellman on each elliptic curve subgroup generated by G1 and G2.
Because the group orders are very smooth, PH runs quickly.
I got two congruences:
k ≡ k1 (mod ord(G1))k ≡ k2 (mod ord(G2))
Then I combined them with CRT (non-coprime-safe) to get:
k ≡ k0 (mod period)
5. Recovering Exact Secret and Decrypting¶
The encryption key was derived from decimal-string secret hashing:
keystream = sha256(str(secret).encode()).digest()
and ciphertext was XOR with repeating keystream.
So I tested representatives k0 + i*period and checked for BITSCTF{...} format.
This produced:
BITSCTF{7h15_15_w4y_2_63nu5_6n6}
Full Solver Code¶
#!/usr/bin/env python3
from hashlib import sha256
from math import comb, gcd
import sympy as sp
p = 129403459552990578380563458675806698255602319995627987262273876063027199999999
f_coeffs = [
87455262955769204408909693706467098277950190590892613056321965035180446006909,
12974562908961912291194866717212639606874236186841895510497190838007409517645,
11783716142539985302405554361639449205645147839326353007313482278494373873961,
55538572054380843320095276970494894739360361643073391911629387500799664701622,
124693689608554093001160935345506274464356592648782752624438608741195842443294,
52421364818382902628746436339763596377408277031987489475057857088827865195813,
50724784947260982182351215897978953782056750224573008740629192419901238915128,
]
G_u = [95640493847532285274015733349271558012724241405617918614689663966283911276425, 1]
G_v = [23400917335266251424562394829509514520732985938931801439527671091919836508525]
Q_u = [
34277069903919260496311859860543966319397387795368332332841962946806971944007,
343503204040841221074922908076232301549085995886639625441980830955087919004,
1,
]
Q_v = [
102912018107558878490777762211244852581725648344091143891953689351031146217393,
65726604025436600725921245450121844689064814125373504369631968173219177046384,
]
enc_flag = bytes.fromhex("f6ca1f88bdb8e8dda17861b91704523f914564888c7138c24a3ab98902c10de5")
def shift_poly(coeffs, t, mod):
n = len(coeffs) - 1
out = [0] * (n + 1)
for i, a in enumerate(coeffs):
pows = [1]
for _ in range(i):
pows.append((pows[-1] * t) % mod)
for j in range(i + 1):
out[j] = (out[j] + a * comb(i, j) * pows[i - j]) % mod
return out
class Fp2:
__slots__ = ("a", "b", "u0", "u1", "p")
def __init__(self, a, b, u0, u1, p):
self.a = a % p
self.b = b % p
self.u0 = u0 % p
self.u1 = u1 % p
self.p = p
def __add__(self, other):
return Fp2(self.a + other.a, self.b + other.b, self.u0, self.u1, self.p)
def __sub__(self, other):
return Fp2(self.a - other.a, self.b - other.b, self.u0, self.u1, self.p)
def __neg__(self):
return Fp2(-self.a, -self.b, self.u0, self.u1, self.p)
def __mul__(self, other):
# alpha^2 = -u1*alpha - u0
a = (self.a * other.a - self.b * other.b * self.u0) % self.p
b = (self.a * other.b + self.b * other.a - self.b * other.b * self.u1) % self.p
return Fp2(a, b, self.u0, self.u1, self.p)
def __eq__(self, other):
return self.a == other.a and self.b == other.b
def conj(self):
return Fp2(self.a - self.b * self.u1, -self.b, self.u0, self.u1, self.p)
def norm(self):
return (self.a * self.a - self.a * self.b * self.u1 + self.b * self.b * self.u0) % self.p
def inv(self):
n = self.norm()
if n == 0:
raise ZeroDivisionError("non-invertible in Fp2")
ni = pow(n, -1, self.p)
c = self.conj()
return Fp2(c.a * ni, c.b * ni, self.u0, self.u1, self.p)
def __truediv__(self, other):
return self * other.inv()
def pow(self, e):
r = Fp2(1, 0, self.u0, self.u1, self.p)
b = self
while e > 0:
if e & 1:
r = r * b
e >>= 1
if e:
b = b * b
return r
def is_base(self):
return self.b == 0
def ec_add_fp(P, Q, c3, mod):
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and (y1 + y2) % mod == 0:
return None
if x1 == x2 and y1 == y2:
if y1 == 0:
return None
m = (3 * c3 * x1 * x1) % mod
m = (m * pow((2 * y1) % mod, -1, mod)) % mod
else:
m = ((y2 - y1) % mod) * pow((x2 - x1) % mod, -1, mod) % mod
x3 = (m * m) % mod
x3 = (x3 * pow(c3, -1, mod)) % mod
x3 = (x3 - x1 - x2) % mod
y3 = (-(m * (x3 - x1) + y1)) % mod
return (x3, y3)
def ec_add_fp2(P, Q, c3, mod):
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and (y1 + y2) == Fp2(0, 0, x1.u0, x1.u1, mod):
return None
if x1 == x2 and y1 == y2:
if y1 == Fp2(0, 0, x1.u0, x1.u1, mod):
return None
m = (x1 * x1) * Fp2(3 * c3, 0, x1.u0, x1.u1, mod)
m = m / (y1 * Fp2(2, 0, x1.u0, x1.u1, mod))
else:
m = (y2 - y1) / (x2 - x1)
x3 = (m * m) / Fp2(c3, 0, x1.u0, x1.u1, mod)
x3 = x3 - x1 - x2
y3 = -(m * (x3 - x1) + y1)
return (x3, y3)
def ec_mul(P, n, c3, mod, ext=False):
R = None
Q = P
add = ec_add_fp2 if ext else ec_add_fp
while n > 0:
if n & 1:
R = add(R, Q, c3, mod)
n >>= 1
if n:
Q = add(Q, Q, c3, mod)
return R
def ec_neg(P, mod):
if P is None:
return None
x, y = P
if isinstance(y, Fp2):
return (x, -y)
return (x, (-y) % mod)
def ec_sub(P, Q, c3, mod):
return ec_add_fp(P, ec_neg(Q, mod), c3, mod)
def map_divisor_to_elliptic(u, v, t, a, mod):
du = len(u) - 1
if du == 0:
return None, None
if du == 1:
x = (-u[0]) % mod
y = v[0] % mod
X = (x - t) % mod
U1 = (X * X) % mod
V1 = y
invX = pow(X, -1, mod)
U2 = (invX * invX) % mod
V2 = (y * pow(invX, 3, mod)) % mod
return (U1, V1), (U2, V2)
if du == 2:
u0 = u[0] % mod
u1 = u[1] % mod
r = Fp2(0, 1, u0, u1, mod)
y = Fp2(v[0], 0, u0, u1, mod)
if len(v) > 1:
y = y + (r * Fp2(v[1], 0, u0, u1, mod))
X = r - Fp2(t, 0, u0, u1, mod)
# E1: y^2 = a*u^3 + 1
P1 = (X * X, y)
P1b = (P1[0].conj(), P1[1].conj())
S1 = ec_add_fp2(P1, P1b, a, mod)
# E2: y^2 = u^3 + a
invX = X.inv()
P2 = (invX * invX, y * invX.pow(3))
P2b = (P2[0].conj(), P2[1].conj())
S2 = ec_add_fp2(P2, P2b, 1, mod)
out = []
for S in (S1, S2):
if S is None:
out.append(None)
continue
sx, sy = S
if not sx.is_base() or not sy.is_base():
raise ValueError("trace point did not land in Fp")
out.append((sx.a % mod, sy.a % mod))
return tuple(out)
raise ValueError("unexpected divisor degree")
def point_order(P, c3, mod, group_order, factors):
o = group_order
for prime, exp in factors.items():
for _ in range(exp):
cand = o // prime
if ec_mul(P, cand, c3, mod) is None:
o = cand
else:
break
return o
def dlog_prime_power(P, Q, prime, exp, c3, mod):
# assumes ord(P) = prime**exp
x = 0
P0 = ec_mul(P, prime ** (exp - 1), c3, mod)
for j in range(exp):
R = ec_sub(Q, ec_mul(P, x, c3, mod), c3, mod)
Rj = ec_mul(R, prime ** (exp - 1 - j), c3, mod)
digit = None
cur = None
for k in range(prime):
if k == 0:
cur = None
elif k == 1:
cur = P0
else:
cur = ec_add_fp(cur, P0, c3, mod)
if cur == Rj:
digit = k
break
if digit is None:
raise ValueError(f"no digit for prime={prime}, j={j}")
x += digit * (prime ** j)
return x
def dlog_pohlig_hellman(P, Q, ordP, c3, mod):
fac = sp.factorint(ordP)
residues = []
moduli = []
for prime, exp in fac.items():
pe = prime ** exp
cofactor = ordP // pe
Pi = ec_mul(P, cofactor, c3, mod)
Qi = ec_mul(Q, cofactor, c3, mod)
xi = dlog_prime_power(Pi, Qi, prime, exp, c3, mod)
residues.append(xi)
moduli.append(pe)
x = sp.ntheory.modular.crt(moduli, residues)[0]
return int(x) % ordP
def combine_congruence(a1, m1, a2, m2):
g = gcd(m1, m2)
if (a1 - a2) % g != 0:
raise ValueError("inconsistent congruences")
l = m1 // g * m2
t = ((a2 - a1) // g) * pow((m1 // g) % (m2 // g), -1, m2 // g)
t %= (m2 // g)
x = (a1 + m1 * t) % l
return x, l
def decrypt_with_secret(ciphertext, secret):
ks = sha256(str(secret).encode()).digest()
return bytes(c ^ ks[i % len(ks)] for i, c in enumerate(ciphertext))
def main():
# 1) Shift x -> X+t to get an even sextic
f6 = f_coeffs[6]
f5 = f_coeffs[5]
t = (-f5 * pow((6 * f6) % p, -1, p)) % p
shifted = shift_poly(f_coeffs, t, p)
print("[+] shift t =", t)
print("[+] shifted odd coefficients (x, x^3, x^5):", shifted[1], shifted[3], shifted[5])
if shifted[1] != 0 or shifted[3] != 0 or shifted[5] != 0:
raise SystemExit("shift failed to produce even polynomial")
a = shifted[6]
if shifted[:6] != [1, 0, 0, 0, 0, 0]:
raise SystemExit("unexpected shifted form")
print("[+] C' : y^2 = 1 + a*X^6")
print("[+] a =", a)
# 2) Map Jacobian divisors into E1 x E2
G1, G2 = map_divisor_to_elliptic(G_u, G_v, t, a, p)
Q1, Q2 = map_divisor_to_elliptic(Q_u, Q_v, t, a, p)
print("[+] G1 =", G1)
print("[+] Q1 =", Q1)
print("[+] G2 =", G2)
print("[+] Q2 =", Q2)
# 3) Solve two elliptic DLPs
N = p + 1
facN = sp.factorint(N)
ordG1 = point_order(G1, a, p, N, facN)
ordG2 = point_order(G2, 1, p, N, facN)
print("[+] ord(G1) =", ordG1)
print("[+] ord(G2) =", ordG2)
k1 = dlog_pohlig_hellman(G1, Q1, ordG1, a, p)
k2 = dlog_pohlig_hellman(G2, Q2, ordG2, 1, p)
print("[+] k1 =", k1)
print("[+] k2 =", k2)
if ec_mul(G1, k1, a, p) != Q1:
raise SystemExit("k1 check failed")
if ec_mul(G2, k2, 1, p) != Q2:
raise SystemExit("k2 check failed")
k0, period = combine_congruence(k1, ordG1, k2, ordG2)
print("[+] k ≡", k0, "(mod", period, ")")
# 4) Recover the exact representative used by encryption
for i in range(0, 16):
candidate = k0 + i * period
pt = decrypt_with_secret(enc_flag, candidate)
if pt.startswith(b"BITSCTF{") and pt.endswith(b"}"):
print("[+] secret used =", candidate)
print("[+] flag =", pt.decode())
return
raise SystemExit("flag not found in searched representatives")
if __name__ == "__main__":
main()
Output I Got¶
When I ran the script, it printed:
secret used = 91527621348541142496688581834442276703691715094599257862319082414424378704170flag = BITSCTF{7h15_15_w4y_2_63nu5_6n6}