Overview
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
Exclusive to subscribers. 97% yet to be discovered!
Already subscribed? Log in!
KEYWORDS
integer factorization | discrete logarithm | public-key cryptography | Number Field Sieve | CADO-NFS
New factorization and discrete logarithm record computations
State of the art
Article included in this offer
"Networks and Telecommunications"
(
174 articles
)
Updated and enriched with articles validated by our scientific committees
A set of exclusive tools to complement the resources
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).
Exclusive to subscribers. 97% yet to be discovered!
Already subscribed? Log in!
