Dans ce write-up du challenge Crypto 500 – Wiener de GreHack, nous utilisons Sage et OpenSSL. Il est possible d’utiliser ses propres outils comme Pari/GP mais si vous n’avez pas d’outils de prédilection et / ou que RSA ne vous est pas familier, nous vous conseillons de lire l’article précédent afin de comprendre la démarche et l’utilisation des outils.

Fichiers fournis par GreHack

Clef publique : Michael-Wiener.pub

Fichier chiffré : flag.enc

On a donc, a priori, un fichier chiffré avec un chiffrement asymétrique (RSA ?!). L’indice nous donne le nom du cryptanalyste Michael J. Wiener, dont une rapide recherche Google nous amène sur la page Wikipedia Wiener’s attack. Cela confirme nos soupçons sur RSA et il ne nous reste plus qu’a extraire les paramètres RSA, puis d’implémenter en Sage l’attaque de Wiener !

Extraction des paramètres et attaque de Wiener

$> openssl asn1parse -in Michael-Wiener.pub  -i -strparse 19   //obtention de n et e

    0:d=0  hl=4 l=1034 cons: SEQUENCE          
    4:d=1  hl=4 l= 513 prim:  INTEGER           :0331702C5FE01F2401C9E44EC0BA79E4[...]
  521:d=1  hl=4 l= 513 prim:  INTEGER           :02C398BE3121D210E2F54DBA688A0F16[...]

$> sage

sage: n = 0x0331702C5FE01F2401C9E44EC0BA79E4[...]  // copié / collé depuis openssl

sage: e = 0x02C398BE3121D210E2F54DBA688A0F16[...]  // idem

sage: c_fracs = continued_fraction(e/n).convergents()  // calcul des fractions continues comme ici

sage: test_message = 42  //  message qui nous servira à vérifier que l'on a bien trouvé la clef privée

sage: test_message_encryted = pow(test_message,e,n)

Grâce à Wiener, on sait que la clef privée (d) est présente parmi les dénominateurs des fractions continues (c_fracs). On va donc parcourir l’ensemble des fractions continues et tenter de déchiffrer notre test_message avec le dénominateur actuel. Si le déchiffrement est bon, c’est que l’on a trouvé la clef.

sage: for i in xrange(len(c_fracs)):

if pow(test_message_encryted,c_fracs[i].denom(),n) == test_message:

d = c_fracs[i].denom()

break

sage: file_flag = open("flag.enc", 'r').read()  // on lit le fichier chiffré contenant le flag

sage: flag_encrypted = text2Int(file_flag)  // binaire -> entier (voir Crypto 300 2.3.1)

sage: flag = pow(flag_encrypted,d,n) // déchiffrement 

sage: int2Text(int(flag),45)  // flag !