L’épreuve :
Les fichiers de l’épreuve se trouvent sur le site de GreHack. On y trouve 2 clefs publiques, respectivement celles de John et de Bill, ainsi qu’un même message chiffré avec les 2 clefs (message1 et message2).
L’attaque :
En analysant les clefs, on remarque 2 choses étonnantes pour un chiffrement RSA :
- Le même module n est utilisé pour les 2 clefs ;
- L’exposant public e est différent, on a e_john = 3 et e_bill = 65537.
Le fait que gcd(e_john, e_bill)=1 implique qu’il est possible pour un attaquant de retrouver le message comme démontré ici :
En pratique :
On utilise sage.
Etape 1 : on initialise les variables n, eBill et eJohn avec les données des clefs publiques. On calcule ensuite s1 et s2 tels que eBill*s1 + eJohn*s2 =1 à l’aide de la fonction xgcd(). On obtient s1=-1 et s2=21846.
Etape 2 : on initialise les variables chiffre1 et chiffre2 avec les messages chiffrés fournis dans l’archive de l’epreuve. On retrouve le message clair M à l’aide du produit des puissances modulaires des chiffrés, comme expliqué au dessus. On affiche le résultat à l’aide de la fonction int2Text.
