In this CTF challenge, we are given the following encryption script:
from sage.all import (
ComplexField,
QQ,
ZZ,
QuadraticField,
algdep,
choice,
elliptic_j,
hilbert_class_polynomial,
kronecker,
next_prime,
randint,
random_prime,
)
prec = 300
CC = ComplexField(prec)
def ideal_to_j(I):
"Associate a j-invariant to each ideal class"
I = I.reduce_equiv()
alpha, beta = list(I.basis())
K = alpha.parent()
NI = QQ(I.norm())
if NI <= 0:
raise ValueError("The ideal must be nonzero")
alpha_bar = alpha.galois_conjugate()
beta_bar = beta.galois_conjugate()
# For Im(beta/alpha) > 0, we have
#
# alpha*beta_bar - alpha_bar*beta = -Norm(I)*sqrt(D).
delta = alpha*beta_bar - alpha_bar*beta
if delta == NI*sqrtD:
# The basis has the opposite orientation.
alpha, beta = beta, alpha
alpha_bar, beta_bar = beta_bar, alpha_bar
elif delta != -NI*sqrtD:
raise ArithmeticError(
"The ideal basis has the wrong discriminant scaling:\n"
f"delta = {delta}\n"
f"expected ±{NI*sqrtD}"
)
A = ZZ(alpha.norm() / NI)
B = ZZ(-(alpha * beta.galois_conjugate()).trace() / NI)
C = ZZ(beta.norm() / NI)
tau = (-CC(B) + CC.gen() * CC(-D).sqrt()) / (2 * CC(A))
if tau.imag() <= 0:
raise ArithmeticError("Recovered point is not in the upper half-plane")
return elliptic_j(tau, prec=prec)
def key_gen(D):
bound = abs(ZZ(D))
if bound <= 2:
raise ValueError("The discriminant is too small to sample a split prime")
while True:
ell = random_prime(bound, lbound=2)
if kronecker(D, ell) == 1:
ideal = choice(K.primes_above(ell))
return ideal, ideal_to_j(ideal)
def group_action(a, j, GA_data):
"""I'm just gonna cheat, its YOUR job to solve the challenge after all..."""
for ideal, j_invariant in GA_data:
if j_invariant == j:
return ideal_to_j(a * ideal)
else:
raise ValueError("The j-invariant is not present in GA_data")
if __name__=="__main__":
p = next_prime(randint(0, 2**100))
while p % 4 != 3:
p = next_prime(p)
D = -p
K = QuadraticField(D)
w = K.gens()
sqrtD = K(D).sqrt()
ClK = K.maximal_order()
GA_cache = []
trivial_class = ClK.fractional_ideal(1)
GA_cache.append([trivial_class, ideal_to_j(trivial_class)])
public_j = GA_cache[0][1]
print(f"public j_invariant: {public_j.str()}")
sk_A, pk_A = key_gen(D)
GA_cache.append([sk_A, pk_A])
print(f"Alice sends bob... {pk_A.str()}")
sk_B, pk_B = key_gen(D)
GA_cache.append([sk_B, pk_B])
print(f"Bob sends Alice... {pk_B.str()}")
ss = group_action(sk_A, pk_B, GA_cache)
ss_B = group_action(sk_B, pk_A, GA_cache)
assert ss_B == ss
FLAG = b"ECSC{???}"
import hashlib
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
def encrypt_flag(shared_secret):
sha1 = hashlib.sha1()
sha1.update(shared_secret.str(digits=20).encode('ascii'))
key = sha1.digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(FLAG, 16))
return iv.hex(), ciphertext.hex()
print(encrypt_flag(ss))
The script implements CSIDH over $\large \mathbb{C}$ with a special group action:
def group_action(a, j, GA_data):
"""I'm just gonna cheat, its YOUR job to solve the challenge after all..."""
for ideal, j_invariant in GA_data:
if j_invariant == j:
return ideal_to_j(a * ideal)
else:
raise ValueError("The j-invariant is not present in GA_data")
The public keys are j-invariants of ideal classes, while the ideals themselves are private keys. The group action is the multiplication of ideals, and the shared secret is the ideal
\[\large I_{s} = I_{A} \cdot I_{B}\]We are given the j-invariant of the “public” ideal, Alice’s ideal, and Bob’s ideal. The goal is to reconstruct the ideals from the j-invariants to recover the shared secret and decrypt the flag
pub_j = -3.1197712970813935333025815233059028917528692370565878739706431207392400943025903079398286486e1100479732681975
alice_j = 1.1597266251125603933910992653441043163982816618818648459187602810288105825373314821350084443e9 - 3.0150568297720854611814920360902760793623646151272310123283454986895478282103754038712873498e8*I
bob_j = 398.15980631356365538459960145848563801415044610365697473965739454574633609964901087991590433 - 1355.5841259907285571993485598298233938426577514586420332333072677999276513493390612781725856*I
iv, ct = ('b18b71a1768e5a3622e525b805611b72', '60ea6a1a4dbafbc708c65819c7bd1f8304980000700bd018bf385d48fc96937c5b3c0f1076ef0814b227391709f65d6fad071f5ca5d6e22333c1109358a599e4a4288c8be98ecbccae9ed5e21116ab5b')
The ideal_to_j function converts the fractional ideal $I = \large \langle\alpha,\beta\rangle$ into its corresponding binary quadratic form. It uses the coefficients $\large A,B,C$ of the binary quadratic form to find the principal root $\large \tau$ in the upper half-plane:
This $\large \tau$ defines the period lattice of the ideal, and the script computes it’s j-invariant $\large j(\tau)$ via elliptic_j(tau, prec=prec).
By adding some debug prints to the function, we can tell that recoveirng $\large A$ and $\large B$ lets us recover the ideal basis:
I = Fractional ideal (331634390804810, 1/2*a + 615471438211751/2)
A,B = (331634390804810, -615471438211751)
The j-invariant is computed as:
A = ZZ(alpha.norm() / NI)
B = ZZ(-(alpha * beta.galois_conjugate()).trace() / NI)
C = ZZ(beta.norm() / NI)
tau = (-CC(B) + CC.gen() * CC(-D).sqrt()) / (2 * CC(A))
return elliptic_j(tau, prec=prec)
Using the j-invariant, we can recover $\large \tau$ using the following function:
def j_to_tau(j):
tau = EllipticCurve(j=j).period_lattice().tau()
return tau - floor(tau.real())
We recover $\large \tau$ up to a period ($\large j(\tau) = j(\tau+1)$), but can recover the “canonical” value by subtracting $\large 1$ if $\large \mathrm{Re}(\tau) >1$. However, with just $\large \tau$, we cannot recover $\large A,B$ since $\large p$ is also unknown.
We are also given the public j-invariant:
trivial_class = ClK.fractional_ideal(1)
GA_cache.append([trivial_class, ideal_to_j(trivial_class)])
public_j = GA_cache[0][1]
print(f"public j_invariant: {public_j.str()}")
For the trivial ideal, $\large A,B$ are both 1:
#I = Fractional ideal (1)
A,B = (1, 1)
#real tau is -0.500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 413725151243647.181888936183550186978828354095816570223784043078257876251965006889540499239*I
With $\large \tau$, we could easily recover $\large p$
\[\large \tau = \frac{-B + \sqrt{ p } I}{2A} = \frac{-1 + \sqrt{ p } I}{2}\]However, the given j-invariant is huge:
\[\large pub_j = -3.1197712970\dots \times 10^{1100479732681975}\]Recovering $\large \tau$ via EllipticCurve(j=j).period_lattice().tau() is not feasible due to the size of $\large pub_{j}$, as pari will crash. Instead, we can observe that $\large pub_{j}$ increases with $\large p$:
def check_j(A,B,p):
tau = (-CC(B) + CC.gen() * CC(p).sqrt()) / (2 * CC(A))
return elliptic_j(tau, prec=prec)
#sage: check_j(1,1,100)
#-4.40315058598e13
#sage: check_j(1,1,100000)
#-2.84240776957e431
#sage: check_j(1,1,1000000000000)
#-2.25861309281e1364376
#sage: check_j(1,1,1000000000000000000000000)
#-6.93980848830e1364376353841
#sage: check_j(1,1,10000000000000000000000000000000000)
#-5.60503543495e136437635384184134
We can use a binary-search algorithm to determine what input $\large p$ gives $\large pub_{j}$:
p = 0
ub = 2**100
lb = 0
while lb < ub-1:
p = (ub+lb)//2
x = check_j(1,1,p)
if x < pub_j:
ub = p
else:
lb = p
print(f"recovered p = {p}")
# recovered p = 650572541643865526363370192007
With $\large p$ recovered, and the ability to recover $\large \tau$ for alice and bob, we can now recover $\large A,B$ to reconstruct each ideal:
\[\large \tau = \frac{-B}{2A} + \frac{\sqrt{ p } I}{2A}\]We can take imaginary part of $\large \tau$ and solve:
\[\large A = \frac{\sqrt{ p }}{2\mathrm{Im}(\tau)}\]And then:
\[\large B = -2\cdot A\cdot\mathrm{Re}(\tau)\]with $\large A,B$, we simply reconstruct $\large \alpha,\beta$ to create the ideal:
def j_to_ideal(p, tau):
A = (p.sqrt() / (2*tau.imag())).round()
B = (-2*A*tau.real()).round()
K = QuadraticField(-p)
beta = (-B + K(-p).sqrt()) / 2
return K.ideal(A, beta)
We perform the group action to get the shared secret, before decrypting the flag:
alice_j = CC(alice_j)
alice_tau = j_to_tau(alice_j)
alice_I = j_to_ideal(p, alice_tau)
print(alice_I)
bob_j = CC(bob_j)
bob_tau = j_to_tau(bob_j)
bob_I = j_to_ideal(p, bob_tau)
print(bob_I)
def ideal_to_j(I):
I = I.reduce_equiv()
A, beta = list(I.basis())
B = ZZ(-(A * beta.galois_conjugate()).trace() / A)
tau = (-CC(B) + CC.gen() * CC(p).sqrt()) / (2 * CC(A))
return elliptic_j(tau, prec=prec)
secret_I = ideal_to_j(alice_I*bob_I)
sha1 = hashlib.sha1()
sha1.update(secret_I.str(digits=20).encode('ascii'))
key = sha1.digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(ct)
print(unpad(pt,16).decode())
# ECSC{Yarr...y0u'd_th1nk_it_b3_RR_but_'tis_th3_CC_h3_truly_l1k3s}
import hashlib
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
pub_j = -3.1197712970813935333025815233059028917528692370565878739706431207392400943025903079398286486e1100479732681975
alice_j = 1.1597266251125603933910992653441043163982816618818648459187602810288105825373314821350084443e9 - 3.0150568297720854611814920360902760793623646151272310123283454986895478282103754038712873498e8*I
bob_j = 398.15980631356365538459960145848563801415044610365697473965739454574633609964901087991590433 - 1355.5841259907285571993485598298233938426577514586420332333072677999276513493390612781725856*I
iv, ct = ('b18b71a1768e5a3622e525b805611b72', '60ea6a1a4dbafbc708c65819c7bd1f8304980000700bd018bf385d48fc96937c5b3c0f1076ef0814b227391709f65d6fad071f5ca5d6e22333c1109358a599e4a4288c8be98ecbccae9ed5e21116ab5b')
iv = bytes.fromhex(iv)
ct = bytes.fromhex(ct)
##################### RECOVER P #####################
prec = 500
CC = ComplexField(prec)
def check_j(A,B,p):
D = -p
tau = (-CC(B) + CC.gen() * CC(-D).sqrt()) / (2 * CC(A))
return elliptic_j(tau, prec=prec)
p = 0
ub = 2**100
lb = 0
while lb < ub-1:
p = (ub+lb)//2
#print(p)
x = check_j(1,1,p)
if x < pub_j:
ub = p
else:
lb = p
print(f"recovered p = {p}")
#####################################################
def j_to_ideal(p, tau):
A = (p.sqrt() / (2*tau.imag())).round()
B = (-2*A*tau.real()).round()
K = QuadraticField(-p)
beta = (-B + K(-p).sqrt()) / 2
return K.ideal(A, beta)
def j_to_tau(j):
tau = EllipticCurve(j=j).period_lattice().tau()
return tau - floor(tau.real())
alice_j = CC(alice_j)
alice_tau = j_to_tau(alice_j)
alice_I = j_to_ideal(p, alice_tau)
print(alice_I)
bob_j = CC(bob_j)
bob_tau = j_to_tau(bob_j)
bob_I = j_to_ideal(p, bob_tau)
print(bob_I)
def ideal_to_j(I):
I = I.reduce_equiv()
A, beta = list(I.basis())
B = ZZ(-(A * beta.galois_conjugate()).trace() / A)
tau = (-CC(B) + CC.gen() * CC(p).sqrt()) / (2 * CC(A))
return elliptic_j(tau, prec=prec)
secret_I = ideal_to_j(alice_I*bob_I)
sha1 = hashlib.sha1()
sha1.update(secret_I.str(digits=20).encode('ascii'))
key = sha1.digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(ct)
print(unpad(pt,16).decode())