VX Elliptique

Auteur : Conceptrice X

Enoncé

Nous avons intercepté 2 fichiers (VX_elliptique.pdf et livres_Friang.pdf) émis par un sous-marin d'Evil Gouv. La référence à Brigitte Friang ne peut être une coïncidence. Nous savons de source sure qu'Eve Descartes a été enlevée par Evil Gouv et est retenue dans un de leurs sous-marins dans l'océan Atlantique. Ce doit être elle qui a envoyé ces fichiers. Grâce à une de ses crises mathématiques, elle aura sûrement caché l'identification du sous-marin dans ces fichiers. Votre mission est de retrouver l'identification du sous-marin.

Le flag est de la forme DGSESIEE{x} avec x le code d'identification

VX_elliptique.pdf (SHA256=7995fc6529494734bae9e2a0b1800632bf9ebd41cbfab19ce23d834eabcf7523) : http://challengecybersec.fr/d3d2bf6b74ec26fdb57f76171c36c8fa/VX_elliptique.pdf livres_Friang.pdf (SHA256=222a463aeb09ef4c0599b9448184e616462459baea327827469bc7b0dd738b75) : http://challengecybersec.fr/d3d2bf6b74ec26fdb57f76171c36c8fa/livres_Friang.pdf

Solution

La courbe utilisée est une courbe de Montgomery particulière. En ayant remarqué que le modulo est 2^255-19, on déduit que la courbe semble être la célèbre courbe 25519 publiée par D.J. Bernstein.

(Bernstein DJ. Curve25519: New Diffie-Hellman speed records in Public Key Cryptography—PKC, Lecture Notes in Computer Science. Vol. 3958. New York, USA: Springer; 2006. pp. 207-228)

On vérifie donc que A = 486662 à l’aide du point donné.

Pour x1, il n’y a aucun calcul à faire a priori puisque y1=n-y donc y1=-y [n] on a donc x1=x comme solution en utilisant les propriétés de symétrie d’une courbe elliptique.

Pour x2, il faut trouver les solutions de l’équation y22-x3-Ax2-x=0 [n] en utilisant par exemple SageMath

sage: n = 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: y2 = 30324056046686065827439799532301040739788176334375034006985657438931650257514
sage: R.<k>=PolynomialRing(GF(n))
sage: L=(y2^2 - (k^3 + a*k^2 + k)).roots();L

[(24592060322915955458376742075654918743307884467086758475495911637571571854426,1)]

Enfin pour trouver z, il suffit d’utiliser le théorème des restes chinois car n étant premier,

n et m=(n-1)/2 sont premiers entre eux. L’isomorphisme entre Znm et Zn x Zm permet de vérifier que x1 et x2 sont corrects

z est le mot de passe pour ouvrir le fichier livres_Friang.pdf

https://illuad.fr/2020/11/08/writeup-dgse-ctf-vx-elliptique.html