Overview
Français
ABSTRACT
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.
Read this article from a comprehensive knowledge base, updated and supplemented with articles reviewed by scientific committees.
Read the articleAUTHORS
-
Fabrice BOUDOT: National education teacher - University of Limoges, XLIM, UMR 7252, Limoges, France
-
Pierrick GAUDRY: CNRS Research Director - University of Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Aurore GUILLEVIC: Inria Research Manager - University of Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Nadia HENINGER: Associate Professor - University of California, San Diego, United States
-
Emmanuel THOMÉ: Inria Research Director - University of Lorraine, CNRS, Inria, LORIA, Nancy, France
-
Paul ZIMMERMANN: Inria Research Director - University of Lorraine, CNRS, Inria, LORIA, Nancy, France
INTRODUCTION
Public-key cryptography has enjoyed considerable growth since its introduction in 1976-1977. It relies on mathematical functions that can be rapidly calculated in one direction, but whose inverse is extremely difficult to calculate. Multiplying two large prime integers is straightforward on a computer, but factoring such a product is far more difficult, and is the subject of international competition. This article presents the state of the art for RSA (Rivest-Shamir-Adleman) encryption based on the difficulty of factoring very large integers, and for Diffie-Hellman encryption based on the difficulty of inverting an exponentiation in certain mathematical groups. In 2019, the record for factoring a product of 240 decimal digits was achieved in almost a thousand core-years on several computational clusters. The point of these records is to extrapolate cryptographic key sizes for different encryption needs and protection times.
Key points
Field: Cryptography, computer science, mathematics
Technologies involved: algorithms, high-performance computing
Applications: IT
Main French players :
– research: Inria, CNRS (INS2I), several universities
– governmental: ANSSI
– manufacturers: several
The Ultimate Scientific and Technical Reference
KEYWORDS
integer factorization | discrete logarithm | public-key cryptography | Number Field Sieve | CADO-NFS
This article is included in
Technological innovations
This offer includes:
Knowledge Base
Updated and enriched with articles validated by our scientific committees
Services
A set of exclusive tools to complement the resources
Practical Path
Operational and didactic, to guarantee the acquisition of transversal skills
Doc & Quiz
Interactive articles with quizzes, for constructive reading
New factoring and discrete logarithm calculation records
State of the art
Bibliography
- (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).
Websites
Computations of discrete logarithms, Laurent Grémy :
Wikipedia Integer factorization records :
https://en.wikipedia.org/wiki/Integer_factorization_records
Wikipedia RSA numbers...
The Ultimate Scientific and Technical Reference
