Nouveaux records de factorisation et de calcul de logarithme discret : Dossier complet | Techniques de l’Ingénieur

S'inscrire aux newsletters

Article précédent

Blockchain et santé : cas d’utilisation pour l’autogestion de la maladie chronique

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

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

Article suivant

Terres rares : enjeux économiques et principales applications

Cet article fait partie de l’offre

Innovations technologiques (176 articles en ce moment)

Cette offre vous donne accès à :

Une base complète et actualisée d'articles validés par des comités scientifiques

Un service Questions aux experts et des outils pratiques

Des Quiz interactifs pour valider la compréhension et ancrer les connaissances

ABONNEZ-VOUS

Quitter la lecture facile

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

Lire l’article

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

Il existe des versions antérieures de cet article :

Version archivée 1 de févr. 2011 par Pierrick GAUDRY, Emmanuel THOMÉ, Paul ZIMMERMANN

Lire l'article

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

1 Sites Internet

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

Lire l’article

DÉTAIL DE L'ABONNEMENT :

TOUS LES ARTICLES DE VOTRE RESSOURCE DOCUMENTAIRE

Accès aux :

Articles et leurs mises à jour

Nouveautés

Archives

Articles interactifs

Formats :

HTML illimité

Versions PDF

Site responsive (mobile)

Info parution :

Toutes les nouveautés de vos ressources documentaires par email

DES ARTICLES INTERACTIFS

Articles enrichis de quiz :

Expérience de lecture améliorée

Quiz attractifs, stimulants et variés

Compréhension et ancrage mémoriel assurés

DES SERVICES ET OUTILS PRATIQUES

Questions aux experts

Les meilleurs experts techniques
et scientifiques vous répondent

Articles Découverte

La possibilité de consulter des
articles en dehors de votre offre

Dictionnaire technique multilingue

45 000 termes en français, anglais,
espagnol et allemand

Votre site est 100% responsive,
compatible PC, mobiles et tablettes.

FORMULES

	Formule monoposte	Autres formules
Ressources documentaires
Consultation HTML des articles	Illimitée	Illimitée
Quiz d'entraînement	Illimités	Illimités
Téléchargement des versions PDF	5 / jour	Selon devis
Accès aux archives	Oui	Oui
Info parution	Oui	Oui

Services inclus
Questions aux experts (1)	4 / an	Jusqu'à 12 par an
Articles Découverte	5 / an	Jusqu'à 7 par an
Dictionnaire technique multilingue	Oui	Oui
(1) Non disponible pour les lycées, les établissements d’enseignement supérieur et autres organismes de formation.
	Formule 12 mois monoposte 1 220 € HT	Autres formules (Multiposte, pluriannuelle) DEMANDER UN DEVIS

DEMANDER UN DEVIS

Sommaire
Sommaire détaillé

INTRODUCTION

1 - ÉTAT DE L’ART

1.1 - Ron Rivest, Adi Shamir, Leonard Adleman, factorisation d’entier
1.2 - Whitfield Diffie, Martin Hellman, logarithme discret
1.3 - Tailles de clé recommandées
1.4 - Logiciel libre CADO-NFS

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

3.1 - Sélection polynomiale
3.2 - Collecte de relations
3.3 - Algèbre linéaire
3.4 - Calculs finaux

4 - CONCLUSION

5 - GLOSSAIRE

Publicité Devenez annonceur