Bibliographie & annexes
Présentation
En anglais
RÉSUMÉ
Cet article décrit deux nouveaux records établis fin 2019 : un record de factorisation d’entier avec la factorisation du nombre RSA-240, et un record de calcul de logarithme discret de même taille. Ces deux records correspondent à des nombres de 795 bits, soit 240 chiffres décimaux, et ont été établis avec le même logiciel libre (CADO-NFS), sur le même type de processeurs. Ces records servent de référence pour les recommandations en termes de taille de clé pour les protocoles cryptographiques.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
This article describes two new records established at the end of 2019: an integer factorization record for the factorization of RSA-240, and a discrete logarithm record of the same size. These two records correspond to 795-bit numbers, or 240 decimal digits, and were established with the same open-source CADO-NFS software, on the same type of processors. These records serve as a reference for key size recommendations for cryptographic protocols.
Auteur(s)
-
Fabrice BOUDOT : Professeur de l’Éducation nationale - Université de Limoges, XLIM, UMR 7252, Limoges, France
-
Pierrick GAUDRY : Directeur de recherche CNRS - Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Aurore GUILLEVIC : Chargée de recherche Inria - Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Nadia HENINGER : Associate Professor - University of California, San Diego, États-Unis
-
Emmanuel THOMÉ : Directeur de recherche Inria - Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Paul ZIMMERMANN : Directeur de recherche Inria - Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
INTRODUCTION
La cryptographie à clé publique a connu un essor notable depuis son introduction en 1976-1977. Elle repose sur des fonctions mathématiques qui se calculent rapidement dans un sens mais dont l’inverse est extrêmement difficile à calculer. La multiplication de deux grands entiers premiers est simple sur un ordinateur, mais factoriser un tel produit est bien plus difficile et fait l’objet d’une compétition internationale. Cet article présente l’état de l’art pour le chiffrement RSA (Rivest-Shamir-Adleman) basé sur la difficulté de la factorisation de très grands entiers, et pour le chiffrement Diffie-Hellman basé sur la difficulté d’inverser une exponentiation dans certains groupes mathématiques. En 2019 le record de factorisation d’un produit de 240 chiffres décimaux a été obtenu en près de mille années-cœurs sur plusieurs grappes de calcul. L’intérêt de ces records est d’extrapoler les tailles de clés cryptographiques pour différents besoins de chiffrement et durées de protection.
Points clés
Domaine : Cryptographie, informatique, mathématiques
Technologies impliquées : algorithmique, calcul haute performance
Domaines d'application : informatique
Principaux acteurs français :
– recherche : Inria, CNRS (INS2I), plusieurs universités
– gouvernemental : ANSSI
– industriels : plusieurs
L'expertise technique et scientifique de référence
MOTS-CLÉS
factorisation d’entier logarithme discret cryptographie à clé publique crible algébrique CADO-NFS
KEYWORDS
integer factorization | discrete logarithm | public-key cryptography | Number Field Sieve | CADO-NFS
VERSIONS
- Version archivée 1 de févr. 2011 par Pierrick GAUDRY, Emmanuel THOMÉ, Paul ZIMMERMANN
DOI (Digital Object Identifier)
CET ARTICLE SE TROUVE ÉGALEMENT DANS :
Accueil > Ressources documentaires > Technologies de l'information > Réseaux Télécommunications > Réseaux et télécoms : innovations et tendances technologiques > Nouveaux records de factorisation et de calcul de logarithme discret > État de l’art
Accueil > Ressources documentaires > Technologies de l'information > Sécurité des systèmes d'information > Cryptographie, authentification, protocoles de sécurité, VPN > Nouveaux records de factorisation et de calcul de logarithme discret > État de l’art
Cet article fait partie de l’offre
Innovations technologiques
(177 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-240
En anglais
1. État de l’art
1.1 Ron Rivest, Adi Shamir, Leonard Adleman, factorisation d’entier
L’algorithme de chiffrement RSA a été inventé par Ron Rivest, Adi Shamir et Leonard Adleman en 1977. Il fut l’un des premiers algorithmes de chiffrement dit « à clé publique », c’est-à-dire que le chiffrement d’un message ne requiert pas que l’expéditeur partage un secret avec le destinataire. Il est devenu, depuis, l’un des algorithmes de chiffrement et d’authentification les plus utilisés au monde : on le retrouve ainsi dans le protocole HTTPS qui sécurise les sites internet ou dans le logiciel de chiffrement de messages PGP.
Lorsque Alice souhaite envoyer un message secret m à Bob, le fonctionnement de cet algorithme de chiffrement est le suivant :
-
Bob choisit deux très grands nombres premiers p et q, et calcule leur produit n = p·q. Il choisit également un nombre e premier avec p − 1 et q − 1, et calcule son inverse d modulo (p − 1)(q − 1). Il envoie les deux nombres n et e à Alice ;
-
pour chiffrer le message m, Alice calcule c = me mod n, et envoie le message chiffré c à Bob ;
-
pour déchiffrer le message c, Bob calcule cd mod n et retrouve ainsi le message original m.
La sécurité de cet algorithme repose sur le fait qu'un attaquant qui observerait les communications entre Alice et Bob connaîtrait les valeurs de n, e et c mais ne pourrait retrouver la valeur du message m. En effet, ce qui permet à Bob de retrouver le message clair est de connaître la valeur de d, qui a elle-même été calculée en utilisant les deux nombres premiers p et q.
Cet attaquant devrait donc, à partir du nombre n, retrouver les deux facteurs premiers p et q qui le composent.
Problème de la factorisation d'entier. Étant donné un entier naturel n = p·q, avec p et q premiers, retrouver p et q.
Résoudre ce problème est simple lorsque le nombre n est petit. Il s'agit simplement d'écrire, par exemple, le nombre 91 sous la forme 91 = 7·13 ou encore le nombre 2 701 sous la forme 2 701 = 37·73. Néanmoins, il n'existe pas,...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Innovations technologiques
(177 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
État de l’art
BIBLIOGRAPHIE
-
(1) - AGENCE NATIONALE DE LA SÉCURITÉ DES SYSTÈMES D’INFORMATION - Référentiel général de sécurité, v2.03, Annexe B1. - Téléchargeable via https://www.ssi.gouv.fr/uploads/2014/11/RGS_v-2-0_B1.pdf (2014).
-
(2) - KLEINJUNG (T.) et al - Factorization of a 768-Bit RSA Modulus. - In : CRYPTO 2010. Sous la dir. de Tal Rabin. LNCS 6223. Springer, Heidelberg, p. 333-350. doi :10.1007/978-3-642-14623-7_18 (2010).
-
(3) - KLEINJUNG (T.) et al - Computation of a 768-Bit Prime Field Discrete Logarithm. In : EUROCRYPT 2017, Part I. - Sous la dir. de Jean-Sébastien Coron et Jesper Buus Nielsen. LNCS 10210. Springer, Heidelberg, p. 185-201. doi :10.1007/978-3-319-56620-7_7 (2017).
-
(4) - BOUDOT (F.) et al - Comparing the difficulty of factorization and discrete logarithm : a 240-digit experiment. In : Proceedings of Advances in Cryptology (CRYPTO). - Sous la dir. de D. Micciancio et T. Ristenpart. LNCS 12171. p. 62-91 (2020).
-
...
ANNEXES
Computations of discrete logarithms, Laurent Grémy :
Wikipedia Integer factorization records :
https://en.wikipedia.org/wiki/Integer_factorization_records
Wikipedia RSA numbers :
https://en.wikipedia.org/wiki/RSA_numbers
(pages consultées le 4 août 2020)
Glossaire de l’ANSSI :
https://www.ssi.gouv.fr/particulier/glossaire/
(page consultée le 16 septembre 2020)
HAUT DE PAGE
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Innovations technologiques
(177 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
