L’autre jour, j’ai écrit mon implémentation de l’algorithme de chiffrement à clé publique RSA. J’ai également fait un simple hack de cet algorithme, j’ai donc voulu écrire une courte note sur ce sujet. La résistance à la falsification de RSA repose sur un problème de factorisation. Factorisation… Quel mot terrible…
Ce n’est pas si effrayant que ça
En fait, lors de la première étape de création des clés, nous prenons deux nombres aléatoires, mais les nombres ne doivent être divisibles que par eux-mêmes et un – Nombres premiers.
Appelons-les p et q. Ensuite, nous devrions obtenir le nombre n = p *q. Il sera utilisé pour la génération ultérieure de clés, les clés seront à leur tour utilisées pour crypter et déchiffrer les messages. Dans la version finale de la clé privée et publique, le numéro n sera transféré sans modification.
Disons que nous avons entre nos mains l’une des clés RSA et un message crypté. Nous retirons le numéro n de la clé et commençons le piratage.
Factoriser n
Factorisation – décomposition d’un nombre en facteurs premiers. Tout d’abord, nous extrayons le nombre n de la clé (sur les vraies clés, vous pouvez le faire en utilisant openssl), disons n = 35. Ensuite, nous le prenons en compte en facteurs simples n = 35 = 5 * 7, c’est et il y a nos p et q. Vous pouvez désormais régénérer les clés en utilisant les p, q reçus, décrypter le message et le chiffrer tout en assurant la visibilité de l’auteur d’origine.
Les qubits ne sont pas si simples
Est-il vraiment possible de briser un RSA aussi facilement ? En fait non, les nombres p, q sont délibérément grands, de sorte que la tâche de factorisation sur les ordinateurs classiques prend très longtemps (10 ans dans une certaine mesure)< br/>Cependant, grâce à l’algorithme quantique de Shor, il est possible de factoriser un nombre en très peu de temps. À l’heure actuelle, des articles sur ce sujet indiquent le temps nécessaire pour multiplier un nombre donné, c’est-à-dire pratiquement instantanément. Pour que l’algorithme de Shor fonctionne, il est nécessaire de mettre en œuvre des ordinateurs quantiques dotés d’un grand nombre de qubits. En 2001, IBM a factorisé le nombre 15 en utilisant 7 qubits. Il faudra donc attendre longtemps pour ce moment, date à laquelle nous serons passés aux algorithmes de chiffrement post-quantique.
Touchez brièvement
Peter Shore parle de son algorithme de factorisation
Pour tester l’algorithme de Shor sur un simulateur quantique, vous pouvez installer ProjectQ, ses exemples incluent une implémentation de shor.py qui vous permet de factoriser un nombre saisi par l’utilisateur. Sur le simulateur, le temps d’exécution est déprimant, mais il semble s’agir d’une simulation amusante et ludique du fonctionnement d’un ordinateur quantique.
Articles :
http://www.pagedon.com/rsa-explained-simply/my_programming/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
Implémentation Python de RSA :
https://github.com/demensdeum/RSA-Python
