Présentation

Article

1 - ÉTAT DE L’ART

2 - FACTORISATION DE RSA-240

  • 2.1 - Sélection polynomiale
  • 2.2 - Collecte de relations
  • 2.3 - Algèbre linéaire
  • 2.4 - Calculs finaux

3 - CALCUL D’UN LOGARITHME DISCRET SUR 240 CHIFFRES

4 - CONCLUSION

5 - GLOSSAIRE

Article de référence | Réf : IN131 v2

Conclusion
Nouveaux records de factorisation et de calcul de logarithme discret

Auteur(s) : Fabrice BOUDOT, Pierrick GAUDRY, Aurore GUILLEVIC, Nadia HENINGER, Emmanuel THOMÉ, Paul ZIMMERMANN

Date de publication : 10 janv. 2021

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

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’article

ABSTRACT

New factorization and discrete logarithm record computations

 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

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

integer factorization   |   discrete logarithm   |   public-key cryptography   |   Number Field Sieve   |   CADO-NFS

VERSIONS

Il existe d'autres versions de cet article :

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v2-in131


Cet article fait partie de l’offre

Innovations technologiques

(183 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

ABONNEZ-VOUS

Lecture en cours
Présentation

4. Conclusion

Les algorithmes RSA et Diffie-Hellman sont au cœur des protocoles modernes de communication. D’après le ICSI Certificate Notary ( https://notary.icsi.berkeley.edu/), 90 % des certificats mis en œuvre pour des échanges chiffrés sur Internet en juillet 2020 ont utilisé des clés RSA, et l’échange de clé Diffie-Hellman est requis pour SSH (secure shell), pour TLS 1.3 (la dernière version du protocole SSL/TLS permettant de chiffrer les échanges par mail ou sur Internet), et pour IPsec (pour les réseaux virtuels privés).

Établir de nouveaux records de factorisation et de calcul de logarithme discret est le meilleur moyen d’encourager les utilisateurs de ces protocoles à mettre à jour les tailles de clé en faveur de valeurs plus sûres. Alors que les recommandations officielles sont depuis 2010 d’au moins 2 048 bits pour les clés RSA et Diffie-Hellman, de nombreux sites utilisent encore des clés plus petites : le SSL Pulse de Qualys indique qu’en juillet 2020, 9 % des sites web couramment visités prennent en charge des clés Diffie-Hellman de 1 024 bits, et environ 1 % des clés de 512 ou 768 bits.

Les records que nous avons établis constituent un pas décisif vers la factorisation d’une clé de 1 024 bits dans un futur proche. Grâce aux améliorations logicielles que nous avons effectuées, et à notre procédé algorithmique d’estimation de temps de calcul, nous pouvons affirmer qu’aucune barrière technologique ne s’oppose plus à un record de 1 024 bits. La principale difficulté réside dans l’accès à suffisamment de ressources de calcul. Un rapide calcul montre que la factorisation de RSA-896 (896 bits) nécessitera entre 6 et 7 fois plus de temps de calcul que celle de RSA-250 (829 bits). Ensuite, la factorisation de RSA-1024 (1 024 bits) demandera environ 30 fois plus de temps de calcul que RSA-896, soit de l’ordre de 500 000 années-cœurs.

Cette quantité de ressources est actuellement inaccessible pour nous. Cependant, la combinaison de plusieurs facteurs (des améliorations algorithmiques, de plus grandes capacités de calcul via la loi de Moore, et des partenariats avec des organismes ayant accès à de gros moyens de calcul) devrait permettre la factorisation de RSA-1024 d’ici quelques années.

En 1994, Peter Shor a inventé un algorithme permettant de factoriser un entier plus rapidement sur un ordinateur quantique. Pour factoriser un entier...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Innovations technologiques

(183 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

ABONNEZ-VOUS

Lecture en cours
Conclusion
Sommaire
Sommaire

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).

  • ...

1 Sites Internet

Computations of discrete logarithms, Laurent Grémy :

https://dldb.loria.fr

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

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Innovations technologiques

(183 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

ABONNEZ-VOUS