Solution de n3ige86 pour Elliptic Addrenaline

Le défi se compose d’un script sage elliptic-addrenaline.sage et d’un fichier output.txt.

À la lecture du script sage, on comprend ce qu’il est attendu pour ce défi. À l’instar de l’épreuve Elliptic Addventure, on nous demande de calculer la moitié d’un point d’une courbe elliptique. En effet, étant donnés deux points $P=A+B$ et $M=A-B$, on a $A = \frac{1}{2} (P+M)$ et $B = P-A$. Les coordonnées des points $P$ et $M$ sont donnés dans le fichier output.txt. Toutefois, contrairement à l’épreuve précédente, la courbe elliptique utilisée ici est d’ordre pair, à savoir $h\cdot n$ avec $h=8$ et $n=\mathtt{0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed}$ (voir par exemple https://neuromancer.sk/std/other/Curve25519 qui affiche la courbe sous la forme de Montgomery, $a_W = 1-A_M^2/3$).

Un point d’une telle courbe a alors pour ordre un diviseur de $h\cdot n$, soit : 1 (uniquement pour le point à l’infini), 2, 4, 8, $n$, $2n$, $4n$ ou $8n$.

Lorsqu’on vérifie l’ordre du point $P+M$, on se rend compte qu’il n’est pas d’ordre $n$ et donc son ordre $x$ est multiple de 2 (le point $P+M$ n’étant pas le point à l’infini). Ainsi, on ne pourra pas calculer l’inverse de $2$ modulo $x$.

On peut tester alors le résultat de $2n\cdot (P+M)$. Soit on obtient le point à l’infini si $x=2n$, soit on obtient $G_2$ (le point non trivial d’ordre 2) si $x=4n$ soit on obtient un point d’ordre 4 si $x=8n$ (il est très improbable d’avoir $x < n$, mais on pourrait tester le cas également, de plus comme $2A=P+M$, on a $x < 8n$.). Comme on obtient $G_2$ (facilement reconnaissable avec $y(G_2)=0$), on en déduit $x=4n$.

Désignons par $G_i$ un point générateur d’ordre $i$, un point $Q$ d’ordre $4n$ peut s’écrire sous la forme $Q=u\cdot G_n+ v\cdot G_4$, avec $0 < u < n$ et $0 < v < 4$. Ainsi, $\frac{1}{2}\cdot Q=\frac{u}{2}\cdot G_n + v\cdot G_8$.

Afin d’obtenir $G_8$, il suffit d’avoir un point $R$ d’ordre $8n$ et de calculer $G_8 = n\cdot R$. Par chance un point d’abscisse 0 convient pour $R$. Afin de résoudre $y(R)^2 = b$, on peut calculer $y(R) = b^{\frac{p+3}{8}}\mod p$ (car $p=5\mod 8$ et $b^{\frac{p-1}{4}}=1\mod p$). On prendra de plus $G_4=2G_8$.

Avec ces définitions, on peut vérifier que $P+M = u\cdot G_n+G_4$ et on a donc une première solution $A’$:

$$A’ = (2^{-1}\mod n)(P+M+3G_4)+G_8$$

Manque de chance ce n’est pas le point qu’on recherche puisqu’il ne contient pas le flag recherché. La solution est:

$$A = (2^{-1}\mod n)(P+M+3G_4)+G_8+G_2$$