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.
Cet article est réservé aux abonnés.
Il vous reste 94 % à découvrir.
Déjà abonné ? Se connecter
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
Présentation
Conséquences pour les clés RSAArticle inclus dans l'offre
"Sécurité des systèmes d'information"
(80 articles)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
3. 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é...
Cet article est réservé aux abonnés.
Il vous reste 95 % à découvrir.
Déjà abonné ? Se connecter
Factorisation de RSA-768
Article inclus dans l'offre
"Sécurité des systèmes d'information"
(80 articles)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
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.
Cet article est réservé aux abonnés.
Il vous reste 93 % à découvrir.
Déjà abonné ? Se connecter
Article inclus dans l'offre
"Sécurité des systèmes d'information"
(80 articles)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
