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

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

Already subscribed? Log in!


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

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? Log in!


The Ultimate Scientific and Technical Reference

A Comprehensive Knowledge Base, with over 1,200 authors and 100 scientific advisors
+ More than 10,000 articles and 1,000 how-to sheets, over 800 new or updated articles every year
From design to prototyping, right through to industrialization, the reference for securing the development of your industrial projects

KEYWORDS

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


This article is included in

Networks and Telecommunications

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

Subscribe now!

Ongoing reading
New factoring and discrete logarithm calculation records