Writeup by sin-infosec for Lost Curve

crypto elliptic curve

November 22, 2023

Table of contents

TLDR

Recover the elliptic curve parameters knowing the coordinates of a point $G$ and the coordinates of $2G$.

Recon

I won’t get into the details of the generation of the elliptic curve here, as this is already a well-documented topic. (for example, check https://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2019/lecture-notes/MIT18_783S19_lec1.pdf)

So everything we have here is the coordinates of a point on an unknown elliptic curve, and the coordinates of the result of the point doubling of this points, we will call them $P$ and $Q=2P$. The server asks us to provide $a,b,p$ so that these 4 conditions hold:

  • the bitlength of our provided p is greater or equal than the bitlength of the original modulus.

  • $P_x^3 + aP_x + b - P_y^2 = 0 \mod p$ which is equivalent to saying that $P = (P_x,P_y)$ lies on the elliptic curve $E$ defined by its Weierstrass equation: $$E : y^2 = x^3 +ax + b \mod p$$

  • Similarly, $Q$ also needs to lie on the curve.

  • $2P = Q$

Solving

The hard part of the challenge is to recover the modulus $p$ or a suitable p as I will show later on. First let’s remind that point doubling of a point $P$ on an elliptic curve is computed as:

$$ \lambda = \frac{3P_x^2 + a}{2P_y} \mod p $$

$$ \begin{aligned} \begin{cases} Q_x &= \lambda^2 - 2P_x \mod p\\ Q_y &= \lambda(P_x - Q_x) - P_y \mod p \end{cases} \end{aligned} $$

with $Q = 2P$

By substituting $\lambda$ into the coordinates equations and getting rid of the fractions we get:

$$ \begin{aligned} \begin{cases} Q_x &= (\frac{3P_x^2 + a}{2P_y})^2 - 2P_x \mod p\\ Q_y &= \frac{3P_x^2 + a}{2P_y}(P_x - Q_x) - P_y \mod p \end{cases} \end{aligned} $$ $$ \begin{aligned} \begin{cases} Q_x &= \frac{9P_x^4 +6aP_x^2 + a^2}{4P_y^2} - 2P_x \mod p\\ 2P_yQ_y &= (3P_x^2 + a)(P_x - Q_x) - 2P_y^2 \mod p \end{cases} \end{aligned} $$ $$ \begin{aligned} \begin{cases} Q_x4P_y^2 &= 9P_x^4 +6aP_x^2 + a^2 - 8P_xP_y^2 \mod p \\ 2P_yQ_y &= 3P_x^3 -3Q_xP_x^2 + aP_x - aQ_x - 2P_y^2 \mod p \end{cases} \end{aligned} $$

So the whole problem can be redefined as finding the triplet $(a,b,p)$ that satisfies:

$$ \begin{aligned} P_x^3 + aP_x + b - P_y^2 &= 0 \mod p \\ Q_x^3 + aQ_x + b - Q_y^2 &= 0 \mod p \\ 9P_x^4 +6aP_x^2 + a^2 - 8P_xP_y^2 - Q_x4P_y^2 &=0 \mod p \\ 3P_x^3 -3Q_xP_x^2 + aP_x - aQ_x - 2P_y^2 - 2P_yQ_y &= 0 \mod p \end{aligned} $$

From this point I will show you two methods to solve:

Method 1

We have 4 polynomials, so by taking the resultants of 3 polynomials we can eliminate variables $a$ and $b$. This can be done like this in Sage:

p = int("F1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C03",16)
a = int("F1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C00",16)
b = int("EE353FCA5428A9300D4ABA754A44C00FDFEC0C9AE4B1A1803075ED967B7BB73F",16)
order = int("F1FD178C0B3AD58F10126DE8CE42435B53DC67E140D2BF941FFDD459C6D655E1",16)
gx = int("B6B3D4C356C139EB31183D4749D423958C27D2DCAF98B70164C97A2DD98F5CFF",16)
gy = int("6142E0F7C8B204911F9271F0F3ECEF8C2701C307E8E4C9E183115A1554062CFB",16)

F = GF(p)
E = EllipticCurve(F,[a,b])

P = E(gx,gy)
Q = 2*P

Px,Py = int(P[0]),int(P[1])
Qx,Qy = int(Q[0]),int(Q[1])

R.<a,b> = PolynomialRing(QQ)

f1 = Px^3 + a * Px + b - Py^2
f2 = Qx^3 + a * Qx + b - Qy^2

f3 = 9 * Px^4 + 6 * a * Px^2 + a^2 - 8*Px*Py^2 - 4*Qx*Py^2
f4 = 3 * Px^3 - 3*Px^2*Qx + a*Px - a*Qx - 2*Py^2 - 2*Py*Qy

r1 = f1.resultant(f2,a)
r2 = f1.resultant(f3,a)
poly = r1.resultant(r2,b)
print(poly%p)

0

(I used the curve FRP256V1 for this example) So getting rid of the two variables we obviously obtain a constant polynomial, which has to be null modulo $p$. That means that we recover a multiple of p, and we can recover p by trial and error in the constant polynomial divisors. Once p is recovered, we have 4 polynomials over $GF(p)$ with two unknowns, and finding $(a,b)$ is trivial.

Method 2

The previous method would have been necessary if we had to provide the exact p value of the server. Happily it isn’t the case and we can use Gröbner basis to instantly find a working triplet for us.

Here are a few quote to briefly explain how Gröbner basis work:

First the definition of an ideal:

“In ring theory, a branch of abstract algebra, an ideal of a ring is a special subset of its elements. Ideals generalize certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any other integer results in another even number; these closure and absorption properties are the defining properties of an ideal. An ideal can be used to construct a quotient ring in a way similar to how, in group theory, a normal subgroup can be used to construct a quotient group.”

Then the formal definition of Gröbner basis:

“A Gröbner basis G of an ideal I in a polynomial ring R over a field is a generating set of I characterized by any one of the following properties, stated relatively to some monomial order:

  • the ideal generated by the leading terms of polynomials in I equals the ideal generated by the leading terms of G
  • the leading term of any polynomial in I is divisible by the leading term of some polynomial in G
  • the multivariate division of any polynomial in the polynomial ring R by G gives a unique remainder
  • the multivariate division by G of any polynomial in the ideal I gives the remainder 0”

Gröbner basis computation can be seen as a multivariate, non-linear generalization of both Euclid’s algorithm for computing polynomial greatest common divisors, and Gaussian elimination for linear systems. Basically in the case of solving modular systems of equations, it can be useful to reduce the polynomials we have to others that are easier to work with by untangling the variables.

Now how is that useful in our case? Well this can be used over $\mathbb{Z}$ to find a modulo for which a solution exists, which is especially nice where there is no solution over $\mathbb{Q}$ like in our case.

This wont work all the times as it depends on $a,b,p$ values of the server, but launching my script below will get you the flag!

from pwn import *

o = remote("challenges1.france-cybersecurity-challenge.fr", 6002)

o.recvuntil(b"two points:\n")
o.recvuntil(b"P = (")
Px = int(o.recvuntil(b",")[:-1])
Py = int(o.recvuntil(b")")[:-1])
o.recvuntil(b"Q = (")
Qx = int(o.recvuntil(b",")[:-1])
Qy = int(o.recvuntil(b")")[:-1])

P.<a,b> = PolynomialRing(ZZ,order='lex')

f1 = Px^3 + a * Px + b - Py^2
f2 = Qx^3 + a * Qx + b - Qy^2
f3 = 9 * Px^4 + 6 * a * Px^2 + a^2 - 8*Px*Py^2 - 4*Qx*Py^2
f4 = 3 * Px^3 - 3*Px^2*Qx + a*Px - a*Qx - 2*Py^2 - 2*Py*Qy

G = [f1,f2,f3,f4]
I = Ideal(G)
B = I.groebner_basis()
print(B)

#Check if the Groebner basis is nice, otherwise just restart the script
#It should only take a few trials to grab the flag :)
if len(B[0].coefficients()) == len(B[1].coefficients()) == 2:
	a = int(-B[0].coefficients()[1])
	b = int(-B[1].coefficients()[1])
	p = int(B[2].coefficients()[0])
	o.recvuntil(b"a = ")
	o.sendline(str(a))
	o.recvuntil(b"b = ")
	o.sendline(str(b))
	o.recvuntil(b"p = ")
	o.sendline(str(p))
	print(o.recvline())
	print(o.recvline())

o.close()

$in