Bibliographie & annexes
Présentation
Auteur(s)
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleINTRODUCTION
Domaine : Cryptographie
Degré de diffusion de la technologie : Émergence | Croissance | Maturité
Technologies impliquées : Théorie des nombres, algorithmique, grid-computing
Domaines d'application : Internet, banque, défense
Principaux acteurs français : INRIA Nancy-Grand Est, École polytechnique
Autres acteurs dans le monde : École polytechnique fédérale de Lausanne, Université de Bonn, Centrum Wiskunde & Informatica, NTT
integer factorization, RSA challenge, cryptography, public key, distributed computing, Number Field Sieve
factorisation d'entier, défi RSA, cryptographie, clé publique, calcul distribué, crible algébrique
Mid-December 2009, a team of Swiss, German, Dutch, Japanese and French researchers has broken a 768-bit RSA key. This article gives a sketch of the algorithm used for this computation and describes the various steps of this record factorization.
Mi-décembre 2009, une équipe de chercheurs suisses, allemands, hollandais, japonais et français a « cassé » une clé RSA de 768 bits. Cet article esquisse l'algorithme utilisé et décrit les différentes étapes de cette factorisation record.
L'expertise technique et scientifique de référence
VERSIONS
- Version courante de janv. 2021 par Fabrice BOUDOT, Pierrick GAUDRY, Aurore GUILLEVIC, Nadia HENINGER, Emmanuel THOMÉ, Paul ZIMMERMANN
DOI (Digital Object Identifier)
CET ARTICLE SE TROUVE ÉGALEMENT DANS :
Accueil > Ressources documentaires > Archives > [Archives] Réseaux et télécommunications > RSA : la fin des clés de 768 bits > Factorisation de RSA-768
Cet article fait partie de l’offre
Sécurité des systèmes d'information
(77 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Conséquences pour les clés RSA3. Factorisation de RSA-768
La factorisation de RSA-768 a été effectuée en collaboration par cinq institutions principalement académiques : l'EPFL (Suisse), le CWI (Pays-Bas), NTT (Japon), l'Université de Bonn (Allemagne) et l'INRIA (France).
La phase de sélection polynomiale a duré environ 40 années – tous les temps de calcul indiqués correspondent au temps qu'aurait pris le calcul si un unique processeur AMD Opteron à 2,2 Ghz avait été utilisé – pour trouver les polynômes suivants :
La phase de crible peut alors commencer. Il s'agit de trouver des paires (a, b ) telles que F (a, b ) et G (a, b ) sont simultanément friables, où F et G sont les versions homogènes des polynômes f et g ci-dessus. La notion de friabilité utilisée est un peu adaptée par rapport à la définition théorique : on garde les paires telles que F (a, b ) est composé de facteurs premiers plus petits que 1 000 milliards avec au plus 5 d'entre eux plus grands que 1 milliard, et telle que G (a, b ) est composé de facteurs premiers plus petits que 1 000 milliards avec au plus 4 d'entre eux plus grands que 200 millions. Ces limitations correspondent aux algorithmes utilisés pour détecter si un nombre est friable : les « petits » nombres premiers sont identifiés à l'aide d'une méthode similaire au crible d'Eratosthène, alors que les nombres premiers de taille intermédiaire et jusqu'à 1 000 milliards sont trouvés avec des algorithmes plus avancés, comme des variantes de l'algorithme de Dixon, ou une méthode utilisant des courbes elliptiques. C'est ainsi que pour environ 1019 paires (a, b ), nous avons testé si F (a, b ) et G (a, b ) sont simultanément friables.
La phase de crible se parallélise trivialement : il suffit que chaque machine cherche des relations dans des domaines distincts. Cette phase, qui est la plus coûteuse, a duré...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Sécurité des systèmes d'information
(77 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Factorisation de RSA-768
BIBLIOGRAPHIE
-
(1) - KLEINJUNG (T.), AOKI (K.), FRANKE (J.), LENSTRA (A.), THOMÉ (E.), BOS (J.), GAUDRY (P.), KRUPPA (A.), MONTGOMERY (P.), OSVIK (D.), TE RIELE (H.), TIMOFEEV (A.), ZIMMERMANN (P.) - Factorization of a 768-bit RSA modulus. - CRYPTO 2010, p. 333-350, Springer Verlag.
-
(2) - CRANDALL (R.), POMERANCE (C.) - Prime numbers – A computational perspective. - Un livre de référence pour les algorithmes de primalité et de factorisation. Springer Verlag, (2000).
-
(3) - POMERANCE (C.) - A tale of two sieves. - Notices of the AMS. Un article sur la génèse du crible quadratique et du crible algébrique, 43(12), p. 1473-1485.
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Sécurité des systèmes d'information
(77 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
