Le 2 décembre 2019, la liste de diffusion de la théorie des nombres
nmbrthry@listserv.nodak.edu a signalé la
factorisation du nombre RSA-240 (240 décimales, 795 bits). Il s'agit d'une nouvelle réalisation en cryptographie et en théorie des nombres et la prochaine tâche terminée de la liste
RSA Factoring Challenge .
Voici le nombre et ses facteurs:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
Sur la base de la tendance actuelle, vous pouvez à peu près imaginer quand RSA-1024 (309 chiffres décimaux) et RSA-2048 (617 chiffres) seront piratés.
Les réalisations précédentes ont été la
factorisation d'un nombre de 768 bits (232 décimales) en 2009 et le
logarithme discret d'un nombre de 768 bits en 2016 .
De nombreux algorithmes de chiffrement à clé publique reposent sur des nombres extrêmement grands, qui sont le produit de deux nombres premiers. D'autres s'appuient sur la difficulté de résoudre certains problèmes logarithmiques discrets. Avec des tailles de clé suffisamment grandes, il n'existe aucun moyen connu de casser un tel cryptage. La factorisation de grands nombres et le calcul du logarithme discret détruisent les garanties cryptographiques pour une taille de clé donnée et obligent les utilisateurs à augmenter le nombre de bits d'entropie lors de la génération d'un secret.
Des chiffres de plus en plus sophistiqués se fissurent progressivement à mesure que les performances du processeur augmentent et que les algorithmes s'améliorent.
Après l'invention de
l' algorithme général de tamisage de champ de nombres (GNFS) au début des années 90, rien de révolutionnaire n'est apparu dans le domaine de la factorisation entière, bien que quelques optimisations significatives aient été faites. Par exemple, au cours des dernières années, les chercheurs ont pu accélérer considérablement la phase de recherche d'un polynôme approprié.
La factorisation du RSA-240 est également hors du commun, car elle a été réalisée non seulement en augmentant la puissance de calcul, mais aussi en raison de l'optimisation des logiciels et des algorithmes. Pour prouver l'efficacité des modifications apportées, les chercheurs ont lancé le programme sur le même équipement qui a été utilisé pour calculer le logarithme discret de 768 bits en 2016. Ils ont découvert que le tamisage d'une matrice de 795 bits était 25% plus rapide que le tamisage d'une matrice de 768 bits sans optimisation.
Le même groupe de chercheurs a calculé un logarithme discret de la même taille. Pour la première fois dans l'histoire, des enregistrements pour le logarming discret et la factorisation de nombres de même taille sont définis en même temps, et même sur le même matériel et logiciel.
Grâce à l'optimisation des algorithmes et des logiciels, le logarithme discret d'un nombre 795 bits a été accéléré de 33% par rapport au logarithme d'un nombre 768 bits sans optimisation sur le même matériel.
Selon la théorie, le logarithme d'un nombre de 795 bits est 2,25 fois plus compliqué qu'un nombre de 768 bits. Cela signifie que l'effet d'optimisation est en fait trois fois (2,25 × 1,33 = 3).
Les deux types de calculs ont été effectués à l'aide de l'algorithme de champ de numéro de tamis dans le programme open source
CADO-NFS . Parmi les optimisations - amélioration de la parallélisation et de l'utilisation de la mémoire, ainsi que beaucoup de travail pour trouver des paramètres de calcul plus optimaux (un logiciel spécial a été développé pour tester et classer les différents paramètres de calcul).
La somme du temps de calcul pour les deux nouveaux enregistrements est d'environ 4000 ans de fonctionnement des cœurs physiques des processeurs Intel Xeon Gold 6130 (à une fréquence de 2,1 GHz), si ce processeur est pris comme référence.
Une décomposition approximative du temps en factorisation et logarithme:
- Dépistage RSA-240: 800 années-cœur
- Matrice RSA-240: 100 années-cœur
- Dépistage DLP-240: 2400 années-cœur
- Matrice DLP-240: 700 années-cœur
Cette réussite a été décernée par une équipe de recherche dirigée par Emmanuel Thomé, chercheur de premier plan à l'
Institut national français d'informatique et de mathématiques appliquées .
Les inventeurs du chiffrement RSA ont publié des
numéros RSA
de toutes tailles jusqu'au RSA-2048. Tout le monde peut essayer de les pirater.
En fonction de la tendance actuelle, vous pouvez calculer quand RSA-1024 (309 caractères) et RSA-2048 (617 caractères) seront piratés. Si vous extrapolez le programme, vous obtenez respectivement 2031 et 2073. Mais nous voyons que l'optimisation des logiciels et des algorithmes peut considérablement rapprocher ce terme. Peut-être que RSA-2048 sera piraté au cours de notre vie.
En pratique, le RSA recommande d'utiliser la taille de clé RSA minimale de 2048 ou 4096 bits.
À en juger par le développement des ordinateurs quantiques, ils ne seront pas près de briser des clés de cette taille, bien qu'il soit difficile de prédire quelque chose ici. En 2012,
l'algorithme de Shore a géré la
factorisation de 21 (3 × 7), cinq bits d'entropie. Ce nombre est resté longtemps un record de factorisation quantique, mais en 2018, la factorisation du produit des nombres premiers
4088459 a été démontrée sur les processeurs IBM 5 et 16 qubits, ce qui fait déjà 22 bits.
