Il s'agit d'un challenge à 200 points au FCSC 2021.
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:
Comme \(Q = 2P = P + P\), nous avons également obtenir deux équations de plus en utilisant les formules d'additions de 2 points.
Calcul de \(p\)
Pour commencer, on va se servir uniquement de \((4)\), qu'on peut réecrire en isolant \(a\)
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)\) :
Puis on remplace \(a\) dans \((6)\) par l'expression trouvée dans \((5)\)
En passant tout à gauche et en simplifiant un peu, on obtient
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}\):
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
ce qui donne le système suivant :
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}