Solution de GarlicHorse pour Elliptic Addventure

crypto courbe elliptique

30 juillet 2024

Ce challenge est une belle opportunité pour s’intéresser aux différentes propriétés des courbes elliptiques. Nous disposons de deux points d’une courbe elliptique E(Fp)E(F_p) d’équation y2=x3+ax+by^2 = x^3 + ax+b (Forme de Weierstrass). Nous devons retrouver les points initiaux AA et BB dont les coordonnées xx constituent le flag.

Nous possédons les points P1=A+BP_1 = A + B et P2=ABP_2 = A - B. On obtient immédiatement que 2A=P1+P22A = P_1 + P_2. Nous devons maintenant nous intéresser à la multiplication par un scalaire de points de courbes elliptiques.

Pour résoudre ce challenge il faut étudier les courbes elliptiques et connaître quelques propriétés dont celle-ci :

Alors toute multiplication par un scalaire se calcule modulo ll.

Ici, pour obtenir A il faut alors calculer kk tel que 2k1(modl)2k\equiv 1 \pmod l. Puis $k2A = k*(P_1+P_2) = A.Demanieˋreanaloguepour. De manière analogue pour B: : B = k’(P_1-P_2)avec avec 2k’\equiv 1 \pmod l$.

Nous devons alors calculer l’ordre de la courbe elliptique. Sagemath nous donne une méthode toute faite pour calculer l’ordre.

On obtient alors le code Sagemath suivant:

from Crypto.Util.number import *

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

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

ApB = E(65355407912556110148433442581541116153096561277895556722873533689053268966181 , 105815222725531774810979264207056456440531378690488283731984033593201027022521)
AmB = E(103762781993230069010083485164887172361256204634523864861966420595029658052179 , 76878428888684998206116229633819067250185142636730603625369142867437006615111)

l = E.order()

flag_partie_1 = inverse_mod(2,l)*(ApB+AmB)
flag_partie_2 = inverse_mod(2,l)*(ApB-AmB)

print(f"Le flag est : {(long_to_bytes(int(flag_partie_1[0])) + long_to_bytes(int(flag_partie_2[0]))).decode()}")

Le flag est :

FCSC{a0c43dbbfaac7a84b5ce7feb81d492431a69a214d768aa4383aabfd241}