isogeny [pqc]
First Post-Quantum Cryptography Challenge. Elliptic Curve Isogenies.
Challenge Description
from hashlib import md5
import random
secure_random = random.SystemRandom()
ls = list(prime_range(3,117))
p = 4 * prod(ls) - 1
F = GF(p)
E = EllipticCurve(F, [1, 0])
output = ""
for i in range(500):
w = secure_random.choice(ls)
while (P := E.random_point() * ((p + 1) // w)) == E(0):
pass
phi = E.isogeny(P)
for j in range(3):
Q = E.random_point(); R = phi(Q)
output += f"{Q[0]}, {R[0]}\n"
E = phi.codomain()
FLAG = "wgmy{" + md5(str(E.j_invariant()).encode()).hexdigest() + "}"
print(FLAG)
f = open("output.txt", "w")
f.write(output)
Observation
I try to make it easy to understand. (Hopefully)
Looking at the code, we can observe some fancy terms such as GF(), EllipticCurve(), isogeny(), codomain(), and j_invariant().
GF(p), Galois Field, also called Finite Field in a finite number \(p\). This \(p\) cannot just be a number, but it should be either a prime number \(p\) or a prime power \(p^{n}\), where \(n\) is a positive integer.
An EllipticCurve(GF(K), [A, B]) over a field \(K\), which in this case \(K=p\) can be represented in a way that what we called Weierstrass equation.
The initial curve EllipticCurve(F, [1,0]) is written as \(y^2=x^3+(1)x+(0)=x^3+x\)
Now, the core function isogeny(). What is this?
The figure below indicates a self-experiment where the phi \(\phi\) variable is the same as the phi() function using \(p=101\). We can observe that \(R=R_2\)
During middle school, we should’ve studied something called domain and codomain. Ultimately speaking, both things are sets. Domain is the set of possible inputs whereas the codomain is the set of possible outputs through a function. In this experiment,
- Domain, \(E\): \(y^{2}=x^{3}+x\),
Q=E.random_point() - Codomain, \(E^\prime\): \(y^{2}=x^{3}+6x+19\),
R=phi(Q) - Function: \(\phi\) (Isogeny point mapping)
The whole process can be written as,
\[\begin{aligned} \phi:E\longrightarrow E^\prime \end{aligned}\]Isogeny is a morphism of algebraic groups that is surjective and has a finite kernel. In this challenge, we don’t need to know that much, but just an advantage for solving it.
All we need to know is the challenge sage script is executing an isogeny point mapping 500 times and keeps updating the elliptic curve. Then, it takes the j_invariant() (J Function) of the final curve and converts it to MD5 hash.
The code snippet below is important. It selects the prime number from the given prime range and checks for valid transformation. If the random point \(P\) causes a point of infinity E(0) through a scalar \(\frac{p+1}{w}\), it will pass the check.
w = secure_random.choice(ls)
while (P := E.random_point() * ((p + 1) // w)) == E(0):
pass
We also have an output.txt. It contains a bunch of x-coordinates of point \(Q\) and point \(R\). Point \(R\) is the mapped point on the codomain curve from a random point \(Q\) through the isogeny function \(\phi\).
We can loop through each prime number in ls and check whether \(R=\phi(Q)\). If we look deep enough, we actually can check whether \(Q=\phi(P)\) as it uses the same isogeny point mapping function \(\phi\) and every Q[0] is given.
One thing we have to take note of is there is an inner loop in the function.
for j in range(3):
Q = E.random_point(); R = phi(Q)
output += f"{Q[0]}, {R[0]}\n"
E = phi.codomain()
The elliptic curve \(E\) only will be updated when the loop is finished. Therefore, we must include 3 sets of Q[0], R[0] per check during the checking process. For example,
Q[0] , R[0]
--------------------------------------------------------
16...83, 49922808342320980832559242591156495539757698992 <- Match Found! w=31
27...65, 260566338186376146497350077169978292242529015
34...92, 4310045734436499656236511496209408227843436562
--------------------------------------------------------
35...50, 37701162425884087311306184046315031636308074621 <- Match Found! w=101
44...81, 50047451581147700287586493748751880957336251246
33...99, 32272759279570868458181090474566343105190255082
--------------------------------------------------------
37...33, 9031544085806244528075514050683030408371880291 <- Match Found! w-97
33...38, 9998567006257800070867121766786028740396220126
10...96, 7909666908853179905233875619576214819201028097
--------------------------------------------------------
...
Above are the first 9 lines of output.txt. They are divided into 3 sets. If we experiment a bit, we can observe a pattern that every first line of R[0] in each set should have a valid candidate \(w\) in the prime range during brute-forcing. For instance, w=31 can produce R[0]=49922808342320980832559242591156495539757698992 from random point Q through isogeny.
Here is my solution script for checking \(R\) (x-coordinate R[0]) using a dockerize SageMath.
Solution
from hashlib import md5
from sage.all import *
def parse_output(file_path):
pairs = []
with open(file_path, "r") as f:
for line in f:
qx, rx = map(Integer, line.strip().split(", "))
pairs.append((qx, rx))
return pairs
def brute_force_isogeny(p, ls, output_pairs):
F = GF(p)
E = EllipticCurve(F, [1, 0])
idx = 0
while idx < len(output_pairs):
for i in range(3):
if idx + i >= len(output_pairs):
break
Qx, expected_Rx = output_pairs[idx + i]
for w in ls:
P = E.random_point() * ((p + 1) // w)
if P != E(0) and w * P == E(0):
phi = E.isogeny(P)
try:
Q = E.lift_x(Qx)
R = phi(Q)
if R[0] == expected_Rx:
print(f"{w=}, {R[0]=} in index [{idx}].")
E = phi.codomain()
break
except ValueError:
continue
idx += 3
print(E)
return E
def main():
ls = list(prime_range(3,117))
p = 4 * prod(ls) - 1
output_pairs = parse_output("output.txt")
final_curve = brute_force_isogeny(p, ls, output_pairs)
j_invariant = final_curve.j_invariant()
flag = "wgmy{" + md5(str(j_invariant).encode()).hexdigest() + "}"
print(f"FLAG: {flag}")
if __name__ == "__main__":
main()
FLAG: wgmy{5ae3ed17a8d2c66581fef7440e2dc82c}