Dessine-moi une courbe elliptique
In this challenge, we are given the following code and its output.
After some research on the elliptic curves, I found this blog that explains how they solved a CTF. It is not like us because they have a and b, and that’s what we are looking for. But in this WU, we find the formula for the elliptic curve on the finite field that is y**2=x**3+ax+b (where ** is the mathematical power ).
Note that I stated that its an elliptic curve on the finite field because of what is said in the little story above and because, as in the challenge code, we have the formula
4a**3+27b**2%p!=0that need to be true.
But the more acurate equation is y**2=x**3+ax+b%p. We have two point on the curve, H and G. We can take the x and y coordinates as G_x and G_y (recpectively H_x and H_y).
So we have the following equations:
1
2
3
4
5
G_y**2 = G_x**3+a*G_x+b%p
and
H_y**2 = H_x**3+a*H_x+b%p
Let’s simplify the equations by removing, for now, the modulus p. We can find the value of b:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
G_y**2 = G_x**3+a*G_x+b
<=>
G_y**2 - G_x**3 = a*G_x+b
<=>
G_y**2 - G_x**3 - a*G_x = b
<=>
b = G_y**2 - G_x**3 - a*G_x
and
H_y**2 = H_x**3+a*H_x+b
<=>
H_y**2 - H_x**3 = a*H_x+b
<=>
H_y**2 - H_x**3 - a*H_x = b
<=>
b = H_y**2 - H_x**3 - a*H_x
Now that we just found the equation to solve b for G and H, we can mix both equations because they are both equal to b:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
b = G_y**2 - G_x**3 - a*G_x
and
b = H_y**2 - H_x**3 - a*H_x
=>
G_y**2 - G_x**3 - a*G_x = H_y**2 - H_x**3 - a*H_x
<=>
G_y**2 - G_x**3 - H_y**2 + H_x**3 = a*G_x - a*H_x
<=>
G_y**2 - G_x**3 - H_y**2 + H_x**3 = a*(G_x - H_x)
<=>
(G_y**2 - G_x**3 - H_y**2 + H_x**3)/(G_x - H_x) = a
<=>
a = (G_y**2 - G_x**3 - H_y**2 + H_x**3)/(G_x - H_x)
Now, before replacing the xs and ys, we first need to put back the modulus. For the equation to be still valid, we need to have:
1
a = ( (G_y**2 - G_x**3 - H_y**2 + H_x**3)* pow((G_x - H_x), -1,p) ) % p
This will do a division modulus p and the whole calculation needs to be modulus p.
So we have:
1
2
3
4
5
a = ( (G_y**2 - G_x**3 - H_y**2 + H_x**3)* pow((G_x - H_x), -1,p) ) % p
and
b = ( G_y**2 - G_x**3 - a*G_x ) % p
I then put everything in a python code available here.
We can run this code, and we have the flag:
The flag is 404CTF{70u735_l35_gr4nd35_p3r50nn3s_0nt_d_@b0rd_373_d35_3nf4n7s}