Pour les calculs sur la courbe elliptique, j’ai utilisé https://cocalc.com/features/sage afin de travailler en ligne, sans rien installer. L’idée est de retrouver A et B, et en particulier leurs abscisses, connaissant A+B et A-B. J’ai d’abord cherché les demi-sommes et demi-différences des abscisses, utilisant le fait que si $S=A+B$ et $D=A-B$, alors $A=(S+D)/2$ et $B=(S-D)/2$. C’est un peu plus compliqué dans $\mathbb{Z}/p\mathbb{Z}$ mais ça reste simple.
Problème : en appliquant la fonction long_to_bytes (réciproque de bytes_to_long qui transforme flag.txt en entier avant de le chiffrer) aux résultats obtenus, on n’obtient pas de résultat transformable en chaîne de caractère lisible.
Puis je me suis rendu compte que les points obtenus ainsi n’étaient pas sur la courbe.
Révélation ! $A+B$ est la somme des points $A$ et $B$ sur la courbe elliptique, au sens vu ici ! Ce que je vérifie en testant que $A+B$ et $A-B$ sont sur la courbe. Il s’agit maintenant d’en calculer la demi-somme et la demi-différence sur la courbe elliptique. Ajouter et soustraire sont des opérations simples à effectuer avec sage mais diviser par 2 l’est moins.
1ère piste : dans $\mathbb{Z}/p\mathbb{Z}$, diviser par 2 c’est multiplier par $(p+1)/2$. Problème : les résultats ne vont pas : leur somme n’est pas $A+B$ et leur différence n’est pas $A-B$.
Puis je comprends que chaque point $P$ a un ordre sur la courbe, i.e., le plus petit nombre $q$ tel que $qP = 0$ (point à l’infini et élément neutre). On a alors $(q+1)P = P$.
sage donne cet ordre avec la méthode order(). Pour “diviser par 2” il suffit de multiplier par $(q+1)/2$.
Mes calculs sur sage :
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
K=GF(p)
E = EllipticCurve([K(-3),K(41058363725152142129326129780047268409114441015993725554835256314039467401291)])
somme = E([65355407912556110148433442581541116153096561277895556722873533689053268966181,105815222725531774810979264207056456440531378690488283731984033593201027022521])
diff = E([103762781993230069010083485164887172361256204634523864861966420595029658052179,76878428888684998206116229633819067250185142636730603625369142867437006615111])
q = (somme+diff).order()
a = (somme+diff) * ((q+1)//2)
b = (somme-diff) * ((q+1)//2)
print(a)
print(b)
Affichage :
(31780852818425402368588723596238022144324172071966766096317883677429500227940 : 74569787321104582225996912753355563908026849218458228201487958481976032452135 : 1)
(23621324903648026841506078943077513175226970476813184636881033351763458273661 : 3657659247253564334277014898432377210451558255976172146041222221013624703251 : 1)
puis, avec Python :
from Crypto.Util.number import long_to_bytes
long_to_bytes(31780852818425402368588723596238022144324172071966766096317883677429500227940)
donne
b'FCSC{a0c43dbbfaac7a84b5ce7feb81d'
et
long_to_bytes(23621324903648026841506078943077513175226970476813184636881033351763458273661)
donne
b'492431a69a214d768aa4383aabfd241}'
À ma grande surprise, c’est gagné ! Même pas besoin de transformer ces bytes en string.