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 > Algorithme utilisé
Cet article fait partie de l’offre
Sécurité des systèmes d'information
(76 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
Factorisation de RSA-7682. Algorithme utilisé
Un entier RSA est de la forme n = pq où p et q sont deux nombres premiers de même taille. Les nombres de cette forme sont les plus difficiles à factoriser ; c'est pourquoi on les choisit comme clé publique dans l'algorithme RSA. Le meilleur algorithme actuellement connu pour factoriser un entier RSA est le crible algébrique (Number Field Sieve ou NFS en anglais), inventé par Pollard en 1988. L'algorithme NFS étant relativement complexe, nous commençons par décrire, sur un exemple, l'algorithme de Dixon (1981) qui est similaire. Soit n = 5 105 929 à factoriser. L'algorithme de Dixon cherche des entiers
tels que
modulo n soit friable, c'est-à-dire se décompose en petits facteurs premiers. Si on se limite aux facteurs premiers inférieurs à 50, on trouve par exemple les huit relations suivantes (modulo n = 5 105 929) :
En multipliant la seconde relation et les trois dernières, on obtient (toujours modulo n ) :
ce qui s'écrit encore :
avec x = 30 213 678 314 547 et y = 62 171 366 400. En calculant le pgcd de x – y avec n, on obtient le facteur 2 011. L'autre facteur premier de n s'obtient simplement par division, et l'on conclut n = 2 011 × 2 539.
Cet exemple met en évidence les deux phases principales de l'algorithme de Dixon :
-
la phase de crible, où l'on cherche des relations – ici
![]()
...
...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Sécurité des systèmes d'information
(76 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
Algorithme utilisé
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
(76 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
