This article needs to be updated. The reason given is: It seems that some of these records have been surpassed. Please help update this article to reflect recent events or newly available information.(January 2022)
This article's lead sectionmay be too short to adequately summarize the key points. Please consider expanding the lead to provide an accessible overview of all important aspects of the article. The reason given is: it doesn't describe what the current records for discrete logarithms are.(January 2022)
This list (which may have dates, numbers, etc.) may be better in a sortable table format. Please help improve this list or discuss it on the talk page.(January 2022)
The current[needs update] record for integers modulo prime numbers, set in December 2019, is a discrete logarithm computation modulo a prime with 240 digits. For characteristic 2, the current record for finite fields, set in July 2019, is a discrete logarithm over . When restricted to prime exponents[clarification needed], the current record, set in October 2014, is over . For characteristic 3, the current record, set in July 2016, is over . For Kummer extension fields of "moderate"[clarification needed] characteristic, the current record, set in January 2013, is over . For fields of "moderate" characteristic (which are not necessarily Kummer extensions), the current record, published in 2022, is over .
Integers modulo p
On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240). This computation was performed simultaneously with the factorization of RSA-240, using the Number Field Sieve algorithm and the open-source CADO-NFS software. The discrete logarithm part of the computation took approximately 3100 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz). The researchers estimate that improvements in the algorithms and software made this computation three times faster than would be expected from previous records after accounting for improvements in hardware.[1][2]
Previous records for integers modulo p include:
On 16 June 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, and Colin Stahlke announced the computation of a discrete logarithm modulo a 232-digit (768-bit) safe prime, using the number field sieve. The computation was started in February 2015 and took approximately 6600 core years scaled to an Intel Xeon E5-2660 at 2.2GHz.[3]
On 18 June 2005, Antoine Joux and Reynald Lercier announced the computation of a discrete logarithm modulo a 130-digit (431-bit) strong prime in three weeks, using a 1.15GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.[4]
On 5 February 2007 this was superseded by the announcement by Thorsten Kleinjung of the computation of a discrete logarithm modulo a 160-digit (530-bit) safe prime, again using the number field sieve. Most of the computation was done using idle time on various PCs and on a parallel computing cluster.[5]
On 11 June 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé announced the computation of a discrete logarithm modulo a 180 digit (596-bit) safe prime using the number field sieve algorithm.[6]
Also of note, in July 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome published their discrete logarithm computation on a 1024-bit prime.[7] They generated a prime susceptible to the special number field sieve, using the specialized algorithm on a comparatively small subgroup (160-bits). While this is a small subgroup, it was the standardized subgroup size used with the 1024-bit digital signature algorithm (DSA).
The prime used was RSA-240 + 49204 (the first safe prime above RSA-240). This computation was performed simultaneously[how?] with the factorization of RSA-240, using the Number Field Sieve algorithm and the open-source CADO-NFS software. Improvements in the algorithms and software[which?] made this computation about three times faster than would be expected from previous records after accounting for improvements in hardware.
1024-bit
July 2016
Joshua Fried
Pierrick Gaudry
Nadia Heninger
Emmanuel Thome
special number field sieve
The researchers generated a prime susceptible[why?] to the special number field sieve[how?] using a specialized algorithm[which?] on a comparatively small subgroup (160-bits).
The current record (as of July 2019[update]) in a finite field of characteristic 2 was announced by Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski, and Jens Zumbrägel on 10 July 2019.[8] This team was able to compute discrete logarithms in GF(230750) using 25,481,219 core hours on clusters based on the Intel Xeon architecture. This computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.[9]
Previous records in a finite field of characteristic 2 were announced by:
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel on 31 January 2014. This team was able to compute discrete logarithms in GF(29234) using about 400,000 core hours. New features of this computation include a modified method for obtaining the logarithms of degree two elements and a systematically optimized descent strategy.[10]
Antoine Joux on 21 May 2013. His team was able to compute discrete logarithms in the field with 26168 = (2257)24 elements using less than 550 CPU-hours. This computation was performed using the same index calculus algorithm as in the recent computation in the field with 24080 elements.[11]
Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbrägel on 11 Apr 2013. The new computation concerned the field with 26120 elements and took 749.5 core-hours.
Antoine Joux on Mar 22nd, 2013. This used the same algorithm[12] for small characteristic fields as the previous computation in the field with 21778 elements. The new computation concerned the field with 24080 elements, represented as a degree 255 extension of the field with 216 elements. The computation took less than 14100 core hours.[13]
Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbrägel on 19 Feb 2013. They used a new variant of the medium-sized base field function field sieve, for binary fields, to compute a discrete logarithm in a field of 21971 elements. In order to use a medium-sized base field, they represented the field as a degree 73 extension of the field of 227 elements. The computation took 3132 core hours on an SGI Altix ICE 8200EX cluster using Intel (Westmere) Xeon E5650 hex-core processors.[14]
Antoine Joux on 11 Feb 2013. This used a new algorithm for small characteristic fields. The computation concerned a field of 21778 elements, represented as a degree 127 extension of the field with 214 elements. The computation took less than 220 core hours.[15]
The current record (as of 2014[update]) in a finite field of characteristic 2 of prime degree was announced by Thorsten Kleinjung on 17 October 2014. The calculation was done in a field of 21279 elements and followed essentially the path sketched for in [16] with two main exceptions in the linear algebra computation and the descent phase. The total running time was less than four core years.[17] The previous record in a finite field of characteristic 2 of prime degree was announced by the CARAMEL group on April 6, 2013. They used the function field sieve to compute a discrete logarithm in a field of 2809 elements.[18]
The current record (as of July 2016[update]) for a field of characteristic 3 was announced by Gora Adj, Isaac Canales-Martinez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodriguez-Henriquez, and Luis Rivera-Zamarripa on 18 July 2016. The calculation was done in the 4841-bit finite field with 36·509 elements and was performed on several computers at CINVESTAV and the University of Waterloo. In total, about 200 core years of computing time was expended on the computation.[19]
Previous records in a finite field of characteristic 3 were announced:
in the full version of the Asiacrypt 2014 paper of Joux and Pierrot (December 2014).[20] The DLP is solved in the field GF(35·479), which is a 3796-bit field. This work did not exploit any "special" aspects of the field such as Kummer or twisted-Kummer properties. The total computation took less than 8600 CPU-hours.
by Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez on 26 February 2014, updating a previous announcement on 27 January 2014. The computation solve DLP in the 1551-bit field GF(36·163), taking 1201 CPU hours.[21][22]
in 2012 by a joint Fujitsu, NICT, and Kyushu University team, that computed a discrete logarithm in the field of 36·97 elements and a size of 923 bits,[23] using a variation on the function field sieve and beating the previous record in a field of 36·71 elements and size of 676 bits by a wide margin.[24]
Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 6553725 elements (401 bits) announced on 24 Oct 2005, and in a field of 37080130 elements (556 bits) announced on 9 Nov 2005.[25] The current record (as of 2013) for a Kummer extension finite field of "moderate" characteristic was announced on 6 January 2013. The team used a new variation of the function field sieve for the medium prime case to compute a discrete logarithm in a Kummer extension field of 3334135357 elements (a 1425-bit finite field).[26][27] The same technique had been used a few weeks earlier to compute a discrete logarithm in a Kummer extension field of 3355377147 elements (an 1175-bit finite field).[27][28] The current record (as of 2022) for a finite field of "moderate" characteristic (which is not necessarily a Kummer extension) is the computation of discrete logarithm in a field of 211102350 elements (a 1051-bit finite field);[29] previous record[30] of discrete logarithm computations over such fields was over fields having 29707940 elements (a 728-bit finite field) and 6437337 elements (a 592-bit finite field). These computations were done using new ideas to speed up the function field sieve.
On 25 June 2014, Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain announced a new computation of a discrete logarithm in a finite field whose order has 160 digits and is a degree 2 extension of a prime field.[31] The algorithm used was the number field sieve (NFS), with various modifications. The total computing time was equivalent to 68 days on one core of CPU (sieving) and 30 hours on a GPU (linear algebra).
This computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.[clarification needed]
21279
17 October 2014
Thorsten Kleinjung
<4 core-years
29234
31 January 2014
Robert Granger
Thorsten Kleinjung
Jens Zumbrägel
~400,000 core-hours
New features of this computation include a modified method for obtaining the logarithms of degree two elements and a systematically optimized descent strategy.[clarification needed]
a joint Fujitsu, NICT, and Kyushu University team[who?]
36·71
"moderate"
p2
25 June 2014
Razvan Barbulescu
Pierrick Gaudry
Aurore Guillevic
François Morain
68 CPU-days + 30 GPU-hours
This field is a degree-2 extension of a prime field, where p is a prime with 80 digits.[31]
3334135357
6 January 2013
3355377147
37080130
9 November 2005
6553725
24 October 2005
Elliptic curves
Certicom Corp. has issued a series of Elliptic Curve Cryptography challenges. Level I involves fields of 109-bit and 131-bit sizes. Level II includes 163, 191, 239, 359-bit sizes. All Level II challenges are currently believed to be computationally infeasible.[32]
The Level I challenges which have been met are:[33]
ECC2K-108, involving taking a discrete logarithm on a Koblitz curve over a field of 2108 elements. The prize was awarded on 4 April 2000 to a group of about 1300 people represented by Robert Harley. They used a parallelized Pollard rho method with speedup.
ECC2-109, involving taking a discrete logarithm on a curve over a field of 2109 elements. The prize was awarded on 8 April 2004 to a group of about 2600 people represented by Chris Monico. They also used a version of a parallelized Pollard rho method, taking 17 months of calendar time.
ECCp-109, involving taking a discrete logarithm on a curve modulo a 109-bit prime. The prize was awarded on 15 Apr 2002 to a group of about 10308 people represented by Chris Monico. Once again, they used a version of a parallelized Pollard rho method, taking 549 days of calendar time.
None of the 131-bit (or larger) challenges have been met as of 2019[update].
In July 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery announced that they had carried out a discrete logarithm computation on an elliptic curve (known as secp112r1[34]) modulo a 112-bit prime. The computation was done on a cluster of over 200 PlayStation 3 game consoles over about 6 months. They used the common parallelized version of Pollard rho method.[35]
In April 2014, Erich Wenger and Paul Wolfger from Graz University of Technology solved the discrete logarithm of a 113-bit Koblitz curve in extrapolated[note 1] 24 days using an 18-core Virtex-6FPGA cluster.[36] In January 2015, the same researchers solved the discrete logarithm of an elliptic curve defined over a 113-bit binary field. The average runtime is around 82 days using a 10-core Kintex-7FPGA cluster.[37]
On 23 August 2017, Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai, and Sylvain Duquesne announced that they had solved a discrete logarithm problem on a 114-bit "pairing-friendly" Barreto–Naehrig (BN) curve,[39] using the special sextic twist property of the BN curve to efficiently carry out the random walk of Pollard's rho method. The implementation used 2000 CPU cores and took about 6 months to solve the problem.[40]
On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software[41] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.
1 2 The computation ran for 47 days, but not all of the FPGAs used were active all the time, which meant that it was equivalent to an extrapolated time of 24 days.
Related Research Articles
Diffie–Hellman (DH) key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation in Galois fields, such as the RSA cryptosystem and ElGamal cryptosystem.
In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number.
In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form
In mathematics, for given real numbers a and b, the logarithm logba is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logba is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.
In mathematics, the RSA numbers are a set of large semiprimes that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.
In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.
In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.
In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.
Alfred Menezes is co-author of several books on cryptography, including the Handbook of Applied Cryptography, and is a professor of mathematics at the University of Waterloo in Canada.
Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups to a third group with a mapping to construct or analyze cryptographic systems.
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it is currently very difficult to factorize large semiprimes.
In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman developed it in 1994 and then elaborated it together with M. D. Huang in 1999. Previous work includes the work of D. Coppersmith about the DLP in fields of characteristic two.
Digital signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use will become completely insecure if scientists are ever able to build a moderately sized quantum computer. Post quantum cryptography is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used RSA and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as Ring learning with errors. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes
In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.
Logjam is a security vulnerability in systems that use Diffie–Hellman key exchange with the same prime number. It was discovered by a team of computer scientists and publicly reported on May 20, 2015. The discoverers were able to demonstrate their attack on 512-bit DH systems. They estimated that a state-level attacker could do so for 1024-bit systems, then widely used, thereby allowing decryption of a significant fraction of Internet traffic. They recommended upgrading to at least 2048 bits for shared prime systems.
BLISS is a digital signature scheme proposed by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in their 2013 paper "Lattice Signature and Bimodal Gaussians".
↑ Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in , 2013, http://eprint.iacr.org/2013/074.
↑ Granger, Robert, Thorsten Kleinjung, and Jens Zumbrägel. “Breaking `128-Bit Secure’ Supersingular Binary Curves (or How to Solve Discrete Logarithms in and ).” arXiv:1402.3668 [cs, Math], February 15, 2014. https://arxiv.org/abs/1402.3668.
↑ The CARAMEL group: Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann, “Discrete logarithm in GF(2809) with FFS”, April 6, 2013, http://eprint.iacr.org/2013/197.
↑ Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodríguez-Henríquez, "Computing Discrete Logarithms in F_{3^{6*137}} and F_{3^{6*163}} using Magma", 26 Feb 2014, http://eprint.iacr.org/2014/057.
1 2 Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields, Eprint Archive, http://eprint.iacr.org/2012/720
↑ Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), "Archived copy"(PDF). Archived from the original(PDF) on 22 October 2015. Retrieved 30 December 2010.{{cite web}}: CS1 maint: archived copy as title (link) .
↑ Joppe W. Bos and Marcelo E. Kaihara, “PlayStation 3 computing breaks 2^60 barrier: 112-bit prime ECDLP solved,” EPFL Laboratory for cryptologic algorithms - LACAL, http://lacal.epfl.ch/112bit_prime
1 2 Erich Wenger and Paul Wolfger, “Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster” http://eprint.iacr.org/2014/368
↑ Erich Wenger and Paul Wolfger, “Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs” http://eprint.iacr.org/2015/143/
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
