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(F_p)$ d’équation $y^2 = x^3 + ax+b$ (Forme de Weierstrass). Nous devons retrouver les points initiaux $A$ et $B$ dont les coordonnées $x$ constituent le flag.
Nous possédons les points $P_1 = A + B$ et $P_2 = A - B$. On obtient immédiatement que $2A = 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 :
- L’ensemble des points d’une courbe elliptique est un groupe cyclique fini d’ordre $l$ avec $l$ l’ordre la courbe. L’ordre de la courbe étant le nombre points sur cette courbe elliptique.
Alors toute multiplication par un scalaire se calcule modulo $l$.
Ici, pour obtenir A il faut alors calculer $k$ tel que $2k\equiv 1 \pmod l$. Puis $k2A = k*(P_1+P_2) = A$. De manière analogue pour $B$ : $B = k’(P_1-P_2)$ 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}