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 > Cryptographie, RSA et factorisation
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
Algorithme utilisé1. Cryptographie, RSA et factorisation
L'algorithme RSA a été inventé par Rivest, Shamir et Adleman en 1977. C'est à l'heure actuelle l'un des algorithmes les plus utilisés pour chiffrer des données ou authentifier une transaction électronique (cartes bleues, sites Internet sécurisés en https, etc.). RSA rentre dans la catégorie des systèmes cryptographiques « à clé publique », où la clé qui sert à chiffrer les messages est différente de celle qui sert à les déchiffrer. La clé de chiffrement est rendue publique, et seule la clé de déchiffrement est gardée secrète. Il est donc crucial pour la sécurité du système qu'il soit extrêmement difficile de retrouver la clé secrète à partir de la clé publique. Dans RSA, la clé publique est un entier n, et la clé secrète correspondante est constituée de la décomposition en facteurs premiers de n. Ainsi, la sécurité de RSA repose sur la difficulté de la factorisation d'entier.
Multiplier deux grands entiers est très facile : même s'ils font 155 chiffres chacun, cela pourrait se faire à la main, et pour un ordinateur, cela ne prend qu'un dixième de microseconde. L'entier obtenu a 310 chiffres, ce qui fait environ 1 024 bits. Factoriser un tel nombre est actuellement hors de portée des meilleurs ordinateurs actuels, et 1 024 bits est une taille de clé populaire dans les applications (environ 30 % des clés maîtres utilisées pour authentifier les sites Internet).
Depuis l'invention de RSA, les progrès sur la factorisation d'entier se sont accélérés. À l'époque, on imaginait qu'une clé de 130 chiffres ne pourrait jamais être factorisée, quels que soient les progrès des ordinateurs. Mais durant les décennies qui suivirent furent inventés l'algorithme du crible quadratique, puis le crible algébrique. Ces améliorations algorithmiques, conjuguées aux progrès technologiques font que les records de factorisation d'entier sont sans cesse battus, remettant ainsi en cause la sécurité des clés RSA trop petites. Le précédent record datait de 2005, avec la factorisation d'un nombre de 663 bits (200 chiffres décimaux) par une équipe de chercheurs allemands.
La compagnie RSA qui commercialise le produit éponyme a publié en 1991 une série de défis de factorisation pour encourager la recherche sur ce sujet (voir http://www.rsa.com/ rsalabs/node.asp?id=2093)....
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
Cryptographie, RSA et factorisation
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
