RSA : Attaque par factorisation

Généralités

La cryptographie symétrique (ou à clef secrète) est connue depuis l’antiquité et existe sous de nombreuses formes (code de César par exemple) : elle consiste à chiffrer un message ou un document ET le déchiffrer avec une même clef qui reste secrète.

A l’inverse, la cryptographie asymétrique attribuée à Diffie et Hellman date de 1976.

Il existe différents algorithmes asymétriques. L’un des plus connus est le RSA (de ses concepteurs Rivest, Shamir et Adleman – 1977). Cet algorithme est très largement utilisé, par exemple dans les navigateurs pour les sites sécurisés, pour chiffrer les emails, de manière générale pour chiffrer des données qui circulent sur la toile. Il est dans le domaine public.

Dans le principe, un utilisateur crée une paire de clefs (clef publique pour chiffrer le contenu, clef privée pour déchiffrer) basées sur des nombres entiers très grands.
Il communique sa clef publique aux expéditeurs/clients qui chiffreront leurs données avec cette clef avant de les envoyer. Seul le destinataire/serveur ayant la clef privée pourra déchiffrer ces données.

Outils employés pour ce tuto

Kali Linux avec :
openssl : outil de cryptographie open source

msieve : tarball à télécharger en version 1.51 (http://sourceforge.net/projects/msieve/) et installer via make all

get_private_key :  compilé à partir du source en C
source : https://github.com/daniellerch/snippets/blob/master/cryptography/get_priv_key.c
sudo apt-get install libssl-dev
sudo gcc -lssl -lcrypto -o get_priv_key get_priv_key.c

Accessoirement :
hextobin (compilé à partir du source)
http://www.factordb.com/ (base de données pour la factorisation)

Etape 1 : Création des clefs et chiffrement d’un fichier

– création d’une clef privée de 256 bits chiffrée avec RSA

# openssl genrsa -out rsa_clef_privee.pem 256

Cette commande renvoie l’exposant :

e is 65537 (0x10001)

On peut voir à quoi ressemble cette clef en faisant un cat

# cat rsa_clef_privee.pem
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEAxg/cLDl2MpcResscFGh7K0125m4cDxDCWeuqZ6WcVGcCAwEAAQIg
AsGVvsfN7UZM5/iLm30YuatAhUufvKNb59mNNBmG6AECEQD0bnTKuENbBYK7kGAO
etgnAhEAz2+WpnfuxU3nnvbCVSoJwQIRAJZuvHZe/SUxuQnSiyueMxUCECNCkJUT
Zd7b8zcuMrJPRwECEQDiDe6LDmCtrKv40TbCJONB
-----END RSA PRIVATE KEY-----

– création d’une clef publique

# openssl rsa -in rsa_clef_privee.pem -pubout -out rsa_clef_publique.pem
# cat rsa_clef_publique.pem
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMYP3Cw5djKXEXrLHBRoeytNduZuHA8Q
wlnrqmelnFRnAgMBAAE=
-----END PUBLIC KEY-----

– création du fichier crypté (ici un fichier texte) chiffré avec la clef publique

# echo "flag is bazinga !">source.txt
# openssl rsautl -encrypt -pubin -inkey rsa_clef_publique.pem -in source.txt -out cipher.txt

– suppression de la clef privée et du fichier source

# rm source.txt rsa_clef_privee.pem

Comme le quidam moyen qui va lancer l’attaque, on ne dispose que des fichiers suivants (le fichier crypté dont on veut connaître le contenu et la clef publique) ! :

# ls -la
-rwxrwxrwx 1 cipher.txt
-rwxrwxrwx 1 rsa_clef_publique.pem

Etape 2 : Capture the Flag !

A ce stade-là, il faut aller se documenter un peu sur la méthode de chiffrement RSA pour comprendre ce que sont les éléments principaux de l’algo : nombres premiers p et q, modulo n et exposant e. La toile regorge d’articles sur ce sujet.

1 – recherche du modulo et de l’exposant

# openssl rsa -in rsa_clef_publique.pem -pubin -text -modulus
Public-Key: (256 bit)
Modulus:
00:c6:0f:dc:2c:39:76:32:97:11:7a:cb:1c:14:68:
7b:2b:4d:76:e6:6e:1c:0f:10:c2:59:eb:aa:67:a5:
9c:54:67
Exponent: 65537 (0x10001)
Modulus=C60FDC2C39763297117ACB1C14687B2B4D76E66E1C0F10C259EBAA67A59C5467
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMYP3Cw5djKXEXrLHBRoeytNduZuHA8Q
wlnrqmelnFRnAgMBAAE=
-----END PUBLIC KEY-----

On trouve donc :

Exposant e = 65537 (0x10001)
Modulo = C60FDC2C39763297117ACB1C14687B2B4D76E66E1C0F10C259EBAA67A59C5467

2 – conversion du module sous forme décimale

# python -c "print int('C60FDC2C39763297117ACB1C14687B2B4D76E66E1C0F10C259EBAA67A59C5467 ', 16)"

ou

# ./hextobin C60FDC2C39763297117ACB1C14687B2B4D76E66E1C0F10C259EBAA67A59C5467

89585966301943792246245230062704302540737672337902783516814655080496080114791

3 – factorisation du modulo

# ./msieve-1.51/msieve -v 89585966301943792246245230062704302540737672337902783516814655080496080114791

…
prp39 factor: 275729595629207848933393391687729547713
prp39 factor: 324905152446587825176878265175782381607

ou avec une base de données si msieve pas suffisant (c’est le cas, en général, dans les challenges de hack) :

http://www.factordb.com/index.php?query=le_modulo_à_factoriser

4 – obtention de la clef privée

./get_priv_key [p] [q] [exp]

# ./get_priv_key 275729595629207848933393391687729547713 324905152446587825176878265175782381607 65537 > clef_privee_hackee.pem

5 – décryptage du fichier

Par factorisation, on a réussi à retrouver la clef privée. Y’a plus qu’à !

# openssl rsautl -decrypt -inkey clef_privee_hackee.pem -in cipher.txt
flag is bazinga !

Applications

– pour avoir un regard averti sur le chiffrement par une clef RSA de faible poids.
– répondre efficacement à des challenges qui proposent ce genre d’exercice.