Back to Search Start Over

Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment

Authors :
Pierrick Gaudry
Emmanuel Thomé
Fabrice Boudot
Aurore Guillevic
Nadia Heninger
Paul Zimmermann
XLIM (XLIM)
Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)
Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA)
Inria Nancy - Grand Est
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO)
Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
University of California [San Diego] (UC San Diego)
University of California (UC)
This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French 'Ministère de l'Enseignement Supérieur et de la Recherche', by the 'Conseil Régional de Lorraine', by theEuropean Union, through the 'Cyber-Entreprises' project, and by the US National Science Foundation under grant no. 1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco.
Daniele Micciancio
Thomas Ristenpart
Grid5000
University of California
Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French ``Ministère de l'Enseignement Supérieur et de la Recherche', by the ``Conseil Régional de Lorraine', by theEuropean Union, through the ``Cyber-Entreprises' project, and by the US National Science Foundation under grant no.~1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco.
Daniele Micciancio, Thomas Ristenpart
Source :
Advances in Cryptology – CRYPTO 2020 ISBN: 9783030568795, CRYPTO (2), Annual International Cryptology Conference, Advances in Cryptology – CRYPTO 2020, Advances in Cryptology – CRYPTO 2020, Aug 2020, Santa Barbara CA, United States. pp.62-91, ⟨10.1007/978-3-030-56880-1_3⟩, The 40th Annual International Cryptology Conference (Crypto 2020), The 40th Annual International Cryptology Conference (Crypto 2020), Aug 2020, Santa Barbara, USA, United States
Publication Year :
2020
Publisher :
Springer International Publishing, 2020.

Abstract

International audience; We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.The last page of this paper also reports on the factorization of RSA-250.

Subjects

Subjects :
FOS: Computer and information sciences
Computer Science - Cryptography and Security
Computer science
discrete logarithm
Computation
number field sieve
02 engineering and technology
law.invention
General number field sieve
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Software
cryptanalysis
Factorization
law
020204 information systems
0202 electrical engineering, electronic engineering, information engineering
Hardware_ARITHMETICANDLOGICSTRUCTURES
Arithmetic
factoring
business.industry
Numerical digit
Factoring
Discrete logarithm
020201 artificial intelligence & image processing
Cryptanalysis
business
Cryptography and Security (cs.CR)

Details

ISBN :
978-3-030-56879-5
ISBNs :
9783030568795
Database :
OpenAIRE
Journal :
Advances in Cryptology – CRYPTO 2020 ISBN: 9783030568795, CRYPTO (2), Annual International Cryptology Conference, Advances in Cryptology – CRYPTO 2020, Advances in Cryptology – CRYPTO 2020, Aug 2020, Santa Barbara CA, United States. pp.62-91, ⟨10.1007/978-3-030-56880-1_3⟩, The 40th Annual International Cryptology Conference (Crypto 2020), The 40th Annual International Cryptology Conference (Crypto 2020), Aug 2020, Santa Barbara, USA, United States
Accession number :
edsair.doi.dedup.....56ac19b7f4d2138e6afdd641309de86d
Full Text :
https://doi.org/10.1007/978-3-030-56880-1_3
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details