home - links - about - rss

FCSC 2021 - Lost Curve [FR]

Il s'agit d'un challenge à 200 points au FCSC 2021.

Lost Curve description

Le contenu de lost_curve.py est le suivant :

from fastecdsa.curve import Curve
from fastecdsa.point import Point
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange

BITS = 80

while True:
    p = getPrime(BITS)
    if p % 4 == 3:
        break

a, b = randrange(1, p), randrange(1, p)
C = Curve("FCSC", p, a, b, 0, 0, 0)

while True:
    xP = randrange(1, p)
    yP = (xP ** 3 + a * xP + b) % p
    if pow(yP, (p - 1) // 2, p) == 1:
        break

yP = pow(yP, (p + 1) // 4, p)
assert (xP ** 3 + a * xP + b - yP ** 2) % p == 0

P = Point(xP, yP, C)
Q = 2 * P

print("Can you find my secret curve equation: y^2 = x^3 + a*x + b (mod p)?")
print("I will give you two points:")
print(f"P = ({P.x}, {P.y})")
print(f"Q = ({Q.x}, {Q.y})")

try:
    a = int(input(">>> a = "))
    b = int(input(">>> b = "))
    p = int(input(">>> p = "))

    C = Curve("Check", p, a, b, 0, 0, 0)
    check  = True
    check &= p.bit_length() >= BITS
    check &= (P.x ** 3 + a * P.x + b - P.y ** 2) % p == 0
    check &= (Q.x ** 3 + a * Q.x + b - Q.y ** 2) % p == 0
    check &= (2 * Point(P.x, P.y, C) == Point(Q.x, Q.y, C))
    if check:
        print("Congratulations!! Here is your flag:")
        print(open("flag.txt", "r").read())
    else:
        print("That's not it!")
except:
    print("That's not it!")

Résolution

Le serveur nous envoie 2 points \(P = (x_p,y_p)\) et \(Q = 2P = (x_q,y_q)\).

Nous savons que cette courbe est sous la forme de Weierstrass, et que les 2 équations suivantes sont donc vraies:

$$y_p^2 = x_p^3 + ax_p + b \mod p \tag{1}$$
$$y_q^2 = x_q^3 + ax_q + b \mod p \tag{2}$$

Comme \(Q = 2P = P + P\), nous avons également obtenir deux équations de plus en utilisant les formules d'additions de 2 points.

$$x_q = (\frac{3x_p^2 + a}{2y_p})^2 - 2x_p \mod p \tag{3}$$
$$y_q = -y_p - (\frac{3x_p^2 + a}{2y_p})(x_q -x_p) \mod p \tag{4}$$

Calcul de \(p\)

Pour commencer, on va se servir uniquement de \((4)\), qu'on peut réecrire en isolant \(a\)

$$2y_p (\frac{y_p + y_q}{x_p - x_q}) - 3x_p^2 = a \mod p \tag{5}$$

Maintenant qu'on a réussi à exprimer \(a\) en fonction de nos 2 points, on va essayer de trouver une équation qui relie seulement les coordonnées de \(P\),\(Q\), et \(a\). Pour ca, on peut soustraire \((1)\) et \((2)\) :

$$y_p^2 - y_q^2 = x_p^3 - x_q^3 + a(x_p - x_q) \mod p \tag{6}$$

Puis on remplace \(a\) dans \((6)\) par l'expression trouvée dans \((5)\)

$$y_p^2 - y_q^2 = x_p^3 - x_q^3 + (2y_p (\frac{y_p + y_q}{x_p - x_q}) - 3x_p^2)(x_p - x_q) \mod p \tag{7}$$

En passant tout à gauche et en simplifiant un peu, on obtient

$$M = y_p^2 - y_q^2 - x_p^3 + x_q^3 - (2y_p (y_p + y_q) - 3x_p^2(x_p - x_q)) = 0 \mod p \tag{8}$$

Cool! On appelera \(M\) le gros \(M\)achin à gauche pour simplifier les choses. Ici, \(M\) est bien pratique car il ne dépends que de nos 2 points, donc on sait calculer sa valeur dans \(\mathbb{Z}\).

En plus, comme \(M = 0 \mod p\), on a l'équation suivante sur \(\mathbb{Z}\):

$$M = kp \text{, avec } k \in \mathbb{Z} \tag{9}$$

Reste juste à calculer \(M\), à le factoriser, et son plus gros facteur devrait être \(p\) :-).

Calcul de \(a\) et \(b\)

Une fois qu'on a \(p\), il est facile de retrouver les autres paramètres car les équations de points sont linéaires en \(a\) et \(b\). Pour écrire le système correspondant, on peut d'abord réecrire

$$ax_p + b = y_p^2 - x_p^3 \mod p \tag{10}$$
$$ax_q + b = y_q^2 - x_q^3 \mod p \tag{11}$$

ce qui donne le système suivant :

$$A = \begin{pmatrix}x_p & 1\\x_q & 1\end{pmatrix}, X = \begin{pmatrix}a\\b\end{pmatrix}, B = \begin{pmatrix}y_p^2 - x_p^3 \\ y_q^2 - x_q^3\end{pmatrix} \tag{12}$$
$$AX = B \mod p \tag{13}$$

Pour trouver \(X\), on multiplie \((13)\) à gauche par \(A^{-1}\) (facile à calculer comme on travaille modulo un premier) et zoum c'est terminé.

Petite implem en sage des familles :

from pwn import remote
import re
from sage.all import *

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

io.recvline()
io.recvline()
(x1,y1) = map(int, re.findall("\d+", io.recvline().decode()))
(x2,y2) = map(int, re.findall("\d+", io.recvline().decode()))

M = (y1**2 - y2**2 - x1**3 + x2**3) - (2*y1*(y1 + y2) - (3*x1**2) * (x1 - x2))
p = factor(M)[-1][0] # Récup le plus grand facteur 

F = GF(p)
A = Matrix(F, [[x1, 1], [x2, 1]])
B = vector(F, [y1**2 - x1**3, y2**2 - x2**3])

a,b = A.solve_right(B)

io.sendline(str(a))
io.sendline(str(b))
io.sendline(str(p))

for _ in range(5):
    print(io.recvline().decode()) # FCSC{3e244ae57e01787c60ef5d3a5c8aa87d3c945855289e40d375aad955da8f8bb4}

Creative Commons License