Now that you're an expert in elliptic curves, meet their hyperactive cousin!
In this CTF challenge, we are given the following encryption script
a = 18446744073709551862
α = 115792089237316201600239092629181903022853076627057745643635536179347243697936
g = 3
n = 7
p = (a**n-1)//(a-1)
e = 0x1337deadbeef1337
assert is_prime(p)
assert pow(α, (p-1)//n, p) == a
R.<x> = PolynomialRing(FiniteField(p))
H = HyperellipticCurve(α*x^n,1,'u,v')
assert H.genus() == g
J = H.jacobian()
J = J(J.base_ring())
# The flag has to be a valid point on the curve
P = H.lift_x(Integer(int.from_bytes(b"EPT{flag_for_testing}", 'big')))
encrypted = e * J(P)
print(encrypted[0].list())
print(encrypted[1].list())
as well as the output:
[37591645601766195349914241190244587541126648045894370496224605285205051789795607044058331351759777461098164398507872, 31825584496706095821807938099201614630698246114642375148953595216939791581619471005478949323508227490535910661480600, 38070154357732543786398829210104835275871944922030673096683631338658551155399049387419283060209447466278551582717763, 1]
[21531145860198597476878989237755710606843064008828229889869373339271596611957323351613721272489730980549489312170394, 8261157019291686096998910330610725289103621846918848921362473394138486389948240100075107913867104846969233604431830, 12307880594487906245908563779709403748007966885981814022547160387211433226745858660170917861206356995209959276604903]
The encryption script works on the Jacobian of a genus-3 hyperelliptic curve. It begins by defining some constants, and calculates prime $p$:
\[\large p = \frac{a^{n}-1}{a-1}\]This is the same as the 7-th cyclotomic polynomial of $a$.
sage: (x^7 - 1)//(x - 1)
x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
sage: cyclotomic_polynomial(7)
x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
So, $p = \Phi_{7}(a)$. The script then builds the hyperelliptic curve $H: y^{2} + y = \alpha x^{7}$ over $\mathbb{F_p}$, and its Jacobian $J(\mathbb{F_p})$. The flag is encoded in the x-coordinate of point $P \in H(\mathbb{F_p})$ , and the flag is encrypted by scaling the divisor-class $J(P)$ by $e=0x1337deadbeef1337$ in the Jacobian group. We are given the pair $(u,v)$ as the ciphertext.
Since the ciphertext is generated as $e \cdot J(P)$, we could recover $J(P)$ if we knew the order of the Jacobian group $\text{#}J(\mathbb{F}_{p})$ by calculating the modular inverse of $e$. Then, we would take one root of the decrypted $u(x)$ to get the original $x$. However, we do not know the order of the Jacobian group, and it is unfortunately not as simple as calling .order() in SageMath.
We have $p = \Phi_{7}(a)$, which splits in the cyclotomic field $K$:
\[\large p = \prod^{6}_{k=1}(a-\zeta^{k})\]We pick a generator $\pi$, for example $a - \zeta$. The others are generated by the Galois automorphism $\sigma_{k} : \zeta \mapsto \zeta^{k}$. So $\sigma_{k}(\pi) = a-\zeta^{k}$.
K.<zeta> = CyclotomicField(7)
pi = K(a) - zeta
assert norm(pi) == p
def galois_embedding(k, x):
return K.hom([zeta^k])(x)
Stickelberger’s theorem gives the prime-ideal factorization of the Jacobi sum $J(\chi^{r},\chi^{s}) \in \mathbb{Z}[\zeta_{7}]$ as:
\[\large J(\chi^{r},\chi^{s}) = \prod^{6}_{i=1}\sigma_{i}(\pi)^{e_{i}}, \quad e_{i} = \left\lfloor \frac{(r+s)i}{7} \right\rfloor - \left\lfloor \frac{ri}{7} \right\rfloor - \left\lfloor \frac{si}{7} \right\rfloor\]We use $J(\chi,\chi)$, which gives :
for i in range(1,7):
e = floor((2*i)/7) - floor((i)/7) - floor((i)/7)
print(f"e{i} = {e}")
#e1 = 0
#e2 = 0
#e3 = 0
#e4 = 1
#e5 = 1
#e6 = 1
Hence, $J(\chi,\chi)$ is equal to $J_{1} = \sigma_{4}(\pi) \times \sigma_{5}(\pi) \times \sigma_{6}(\pi)$ up to a unit of $K$.
J1 = prod([galois_embedding(i,pi) for i in [4,5,6]])
Following this paper by Koblitz: https://www.cambridge.org/core/services/aop-cambridge-core/content/view/800A4343A2955C7D446B69063EB07BFC/S0008439500005786a.pdf, the order can be calculated as:
\[\large \text{#}J(\mathbb{F}_{p}) = \prod^{2g}_{i=1}(1 - \alpha_{i}) = \lvert Norm_{K/\mathbb{Q}} (1 + J(\chi,\chi)) \rvert\]Since we only have $J(\chi,\chi)$ determined up to a 7th root of unity and sign, we can sweep the 14 candidates for the correct $\text{#}J(\mathbb{F}_{p})$
\[\large \text{#}J(\mathbb{F}_{p}) = \lvert Norm_{K/\mathbb{Q}} (1 \pm \zeta^{k} \cdot J_{1})\rvert\]If the order is co-prime with $e$, we can invert the scalar and compute $C \cdot e^{-1} = J(P)$, then take the roots as mentioned before and get the original $x$.
for sgn in (+1, -1):
for k in range(7):
N = ZZ(norm(1 + sgn*(zeta^k)*J1))
if N*C != J(0):
continue
JP = pow(e, -1, N) * C
for a_root, _ in JP[0].roots():
print(long_to_bytes(ZZ(a_root)).decode())
This finally gives us the flag:
EPT{Now_you_can_count_cyclotomically_f045e0f0cd}
from Crypto.Util.number import long_to_bytes
a = 18446744073709551862
alpha = 115792089237316201600239092629181903022853076627057745643635536179347243697936
n = 7
e = 0x1337deadbeef1337
p = (a^n - 1)//(a - 1)
F = GF(p);
R.<x> = F[]
H = HyperellipticCurve(alpha*x^7, 1)
J = H.jacobian()(F)
v = R([21531145860198597476878989237755710606843064008828229889869373339271596611957323351613721272489730980549489312170394, 8261157019291686096998910330610725289103621846918848921362473394138486389948240100075107913867104846969233604431830, 12307880594487906245908563779709403748007966885981814022547160387211433226745858660170917861206356995209959276604903])
u = R([37591645601766195349914241190244587541126648045894370496224605285205051789795607044058331351759777461098164398507872, 31825584496706095821807938099201614630698246114642375148953595216939791581619471005478949323508227490535910661480600, 38070154357732543786398829210104835275871944922030673096683631338658551155399049387419283060209447466278551582717763, 1])
C = J([u, v])
K.<zeta> = CyclotomicField(7)
pi = K(a) - zeta
assert norm(pi) == p
def galois_embedding(k, x):
return K.hom([zeta^k])(x)
J1 = prod([galois_embedding(i,pi) for i in [4,5,6]])
for sgn in (+1, -1):
for k in range(7):
N = ZZ(norm(1 + sgn*(zeta^k)*J1))
if N*C != J(0):
continue
JP = pow(e, -1, N) * C
for a_root, _ in JP[0].roots():
print(long_to_bytes(ZZ(a_root)).decode())