New factorization and discrete logarithm record computations
Research and innovation REF: IN131 V2

New factorization and discrete logarithm record computations

Authors : Fabrice BOUDOT, Pierrick GAUDRY, Aurore GUILLEVIC, Nadia HENINGER, Emmanuel THOMÉ, Paul ZIMMERMANN

Publication date: January 10, 2021 | Lire en français

Logo Techniques de l'Ingenieur You do not have access to this resource.
Request your free trial access! Free trial

Already subscribed?

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 article

AUTHORS

  • 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

You do not have access to this resource.
Logo Techniques de l'Ingenieur

Exclusive to subscribers. 97% yet to be discovered!

You do not have access to this resource. Click here to request your free trial access!

Already subscribed?

KEYWORDS

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

Ongoing reading
New factoring and discrete logarithm calculation records

Article included in this offer

"Security of information systems"

( 86 articles )

Complete knowledge base

Updated and enriched with articles validated by our scientific committees

Services

A set of exclusive tools to complement the resources

View offer details
Contact our team FAQ