Factoriser une clé RSA

Clés RSA, la factorisation P&Q

Suite à un petit challenge, je me suis intéressé aux différents outils qui existent sur la toile permettant de cracker une clé RSA (d’une longueur modeste bien sûr). Je ne vais pas revenir sur les principes fondamentaux de la cryptographie à clé asymétrique, vous trouverez sur Internet bien assez de tutoriels qui vous expliqueront en détails tout ce qu’il faut savoir sur ce type d’échange.

Quelques mots sur RSA

Pour la suite de cet article, il faut juste comprendre que l’algorithme RSA permet de chiffrer des données à l’aide d’une clé publique (donc connue de tout le monde) et qui ne sont déchiffrables que par le détenteur de la clé privée. Le sens inverse marche aussi, vous pouvez chiffrer des données avec la clé privée et elles seront déchiffrables par tout le monde à l’aide de la clé publique. Ce principe est très utilisé dans les certificats pour authentifier l’autorité de certification (AC) émettrice. Lors de la génération du certificat, l’AC émettrice va réaliser un hash du certificat puis chiffrer ce condensat avec sa clé privée. Pour valider que le certificat est bien émis par cet AC, il suffit donc de déchiffrer le condensat avec sa clé publique, et de valider qu’il est bien identique au hash calculé sur ce certificat.
La sécurité des clés RSA est basée sur la difficulté de factorisation des nombres très grands. On prend deux nombres P et Q, premiers entre eux, qui permettent de dériver d’autres données qui sont utilisés pour générer les clés. En trouvant P et Q, il est donc possible de recréer la clé privée, et déchiffrer toutes les données souhaitées. La clé publique ne contient pas directement P et Q, mais elle contient le résultat PxQ appelé le modulo (M).
Pour notre exemple, nous allons générer une clé RSA de 256 bits, l’utiliser pour chiffrer un fichier texte puis supprimer la clé privée et ne conserver que la clé publique. Le but du jeu sera lors de retrouver la clé privée à partir de la clé publique en factorisant M.

Génération de la clé RSA 256 bits

La première étape consiste donc à générer une clé RSA de 256 bits à l’aide d’openssl :

$ openssl genrsa 256 > /tmp/rsa256.key
cat /tmp/rsa256.key
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEA2XulgrHlJrkLT+iTWLPhl0MRPEPLI1mbMnlFrbtjK6UCAwEAAQIh
AKTYZuTAiIuoWN2x0PW8KvHA04ulXOeOJm0aum20f9rBAhEA/NBWSUhdtJjgfKUq
s8680QIRANw5Uf2+kDfNJ8yrw8yUZpUCEDYu+K9QITU5prNQOuy6nGECEGAFQiGw
GDOsaQENl4a44e0CEBCaWZ7FVJgeIZMNKsvwnVk=
-----END RSA PRIVATE KEY-----

Puis on en extrait la clé publique :

$ openssl rsa -pubout -in /tmp/rsa256.key -out /tmp/rsa256.pub
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANl7pYKx5Sa5C0/ok1iz4ZdDETxDyyNZ
mzJ5Ra27YyulAgMBAAE=
-----END PUBLIC KEY-----

Voila, nous avons donc la clé publique dans le fichier rsa256.pub et la clé privée dans le fichier rsa256.key. Supprimons maintenant la clé privée :

$ rm /tmp/rsa256.priv

Puis chiffrons des données à l’aide de la clé publique :

$ echo "File to protect" > /tmp/file.cleartext
openssl rsautl -encrypt -in /tmp/file.cleartext -pubin -inkey /tmp/rsa256.pub -out /tmp/file.enc

Si on regarde le contenu du fichier, on voit bien qu’il n’est plus lisible:

$ base64 /tmp/file.enc

Il ne nous reste plus qu’à retrouver la clé privée pour déchiffrer notre message.

Récupération des informations de la clé publique

Comme nous l’avons vu précédemment, la clé publique contient deux informations, le modulus et l’exposant (qui lui est fixé, très souvent à la valeur 65537). Il nous faut donc extraire ces deux informations :

$ openssl rsa -in /tmp/rsa256.pub -pubin -text -noout | grep Exponent
Exponent: 65537 (0x10001)

L’exposant est donc 65537.

$ openssl rsa -pubin -in /tmp/rsa256.pub –modulus
KEY_HEXA=$(openssl rsa -pubin -in /tmp/rsa256.pub -modulus | grep Modulus | cut -d'=' -f2)
echo "ibase=16;$KEY_HEXA" | bc
98370352643211377708586325303680309663235650081099379820841483799007896742821

Le modulo est donc en base 10 : 983703526432…2821

Factorisation de la clé

Le meilleur outil que j’ai trouvé sur le net est msieve. Il est disponible sous windows (binaire) et sous linux (à compiler). Il utilise l’algorithme « number field sieve » qui semble être le plus efficace aujourd’hui pour factoriser un nombre. Vous pouvez télécharger le programme en suivant ce lien. Si vous possédez une carte graphique Nvidia, je vous conseille d’utiliser la version CUDA qui se basera sur votre GPU pour augmenter considérablement la puissance de calcul (pour ma part, étant équipé d’une ATI, je n’ai pas pu tester).
Une fois installé, il suffit de lancer l’exécutable avec pour paramètre le nombre à factoriser pour obtenir le résultat souhaité :

$ ./msieve -v 98370352643211377708586325303680309663235650081099379820841483799007896742821
Msieve v. 1.50 (SVN exported)
Mon Aug 27 17:11:18 2012
random seeds: f2616da9 ef0a9003
MPI process 0 of 1
factoring 98370352643211377708586325303680309663235650081099379820841483799007896742821 (77 digits)
searching for 15-digit factors
begin with 212805 relations
reduce to 51881 relations in 2 passes
attempting to read 51881 relations
recovered 51881 relations
recovered 39263 polynomials
attempting to build 36577 cycles
found 36577 cycles in 1 passes
distribution of cycle lengths:
length 1 : 19058
length 2 : 17519
largest cycle: 2 relations
matrix is 36471 x 36577 (4.7 MB) with weight 1083013 (29.61/col)
sparse part has weight 1083013 (29.61/col)
filtering completed in 3 passes
matrix is 25524 x 25588 (3.6 MB) with weight 845323 (33.04/col)
sparse part has weight 845323 (33.04/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 25476 x 25588 (2.3 MB) with weight 625083 (24.43/col)
sparse part has weight 444093 (17.36/col)
commencing Lanczos iteration
memory use: 2.3 MB
lanczos halted after 404 iterations (dim = 25474)
recovered 15 nontrivial dependencies
prp39 factor: 292727782972497489806532560966393292437
prp39 factor: 336047202777652025357855832985297665233

En moins de 3 minutes, l’outil a permis de factoriser le modulo en deux sous facteurs (prp39 factor) qui sont en fait P et Q. Avec ces deux données, on peut facilement recalculer la clé privée au format attendu par openssl. Pour cela, Beck (http://b3ck.blogspot.fr/) propose un outil en mode cgi. Pour l’utiliser, il suffit d’aller à l’URL
http://math.co.ro/cgi-bin/genpriv?p=PCALCULE&q=QCALCULE&e=Exposant.
Pour notre cas, cela donne :
http://math.co.ro/cgi-bin/genpriv?p=292727782972497489806532560966393292437&q=336047202777652025357855832985297665233&e=65537
Le résultat nous donne la clé finale, directement utilisable par openssl
—–BEGIN RSA PRIVATE KEY—–
MIGqAgEAAiEA2XulgrHlJrkLT+iTWLPhl0MRPEPLI1mbMnlFrbtjK6UCAwEAAQIh
AKTYZuTAiIuoWN2x0PW8KvHA04ulXOeOJm0aum20f9rBAhEA/NBWSUhdtJjgfKUq
s8680QIRANw5Uf2+kDfNJ8yrw8yUZpUCEDYu+K9QITU5prNQOuy6nGECEGAFQiGw
GDOsaQENl4a44e0CEBCaWZ7FVJgeIZMNKsvwnVk=
—–END RSA PRIVATE KEY—–

 

[EDIT] – Le site ne semble plus fonctionner, mais vous pouvez recréer vous même la clé via un script python disponible à l’adresse suivante :

https://warrenguy.me/blog/regenerating-rsa-private-key-python

Déchiffrement du message initial

Il ne reste plus qu’à déchiffrer notre message initial (en copiant-collant la clé générée par le site web dans le fichier /tmp/key) :

$ openssl rsautl -decrypt -in /tmp/file.enc -inkey /tmp/key
File to protect

Etat des lieux de la factorisation

Les clés RSA de 256 bits est aujourd’hui triviale. En 2003, les chercheurs ont réussi à cracker une clé de 576 bits, puis 768 bits en 2009. L’augmentation de la puissance de calcul pour chaque bit supplémentaire sur la clé est exponentielle. On considère aujourd’hui que la longueur de clé minimale doit être de 1024 bits pour résister aux attaques portant sur RSA.

3 Responses to "Factoriser une clé RSA"

Leave a Comment