Discrete logarithm records

Discrete logarithm records

Discrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G. The difficulty of this problem is the basis for the security of several cryptographic systems, including Diffie–Hellman key agreement, ElGamal encryption, the ElGamal signature scheme, the Digital Signature Algorithm, and the elliptic curve cryptography analogs of these. Common choices for G used in these algorithms include the multiplicative group of integers modulo p, the multiplicative group of a finite field, and the group of points on an elliptic curve modulo p or over a finite field.

Contents

Integers modulo p

On 18 Jun 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.15 GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.[1]

On 5 Feb 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.[2]

Finite fields

The current record (as of 2010) in a finite field of characteristic 2 was announced by Antoine Joux and Reynald Lercier on 23 Sep 2005. They used the function field sieve to compute a discrete logarithm in a field of 2613 elements. The computation took 17 days on four 16-processor (1.3 GHz) nodes of the Itanium 2-based Bull computer Teranova.[3]

The current record (as of 2010) for a field of characteristic 3 was announced by Takuya Hayashi et al., who computed a discrete logarithm in the field of 36 · 71 elements, using a variation on the function field sieve. [4] This also holds the record for the computation over the largest field (676 bits) of any type.

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.[5]

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.[6]

The Level I challenges which have been met are:[7]

  • 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 method, taking 549 days of calendar time.

None of the 131-bit (or larger) challenges have been met as of 2010.

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 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.[8]

References

  1. ^ Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=20.
  2. ^ Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0.
  3. ^ Antoine Joux, “Discrete logarithms in GF(2607) and GF(2613),” September 23, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0.
  4. ^ Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(36n), 2010, http://eprint.iacr.org/2010/090.
  5. ^ A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf.
  6. ^ Certicom Corp., “The Certicom ECC Challenge,” http://www.certicom.com/index.php/the-certicom-ecc-challenge.
  7. ^ Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), http://www.certicom.com/images/pdfs/challenge-2009.pdf.
  8. ^ 1. 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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… …   Wikipedia

  • Digital credential — Digital credentials are the digital equivalent of paper based credentials. Just as a paper based credential could be a passport, a Driver s license, a membership certificate or some kind of ticket to obtain some service, such as a cinema ticket… …   Wikipedia

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • Cunningham chain — In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes. A Cunningham chain of the first kind of length n …   Wikipedia

  • computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… …   Universalium

  • Analog sound vs. digital sound — Analog sound versus digital sound compares the two ways in which sound is recorded and stored. Actual sound waves consist of continuous variations in air pressure. Representations of these signals can be recorded in either digital or analog… …   Wikipedia

  • Parity of zero — Zero objects, divided into two equal groups Zero is an even number. In other words, its parity the quality of an integer being even or odd is even. Zero fits the definition of even number : it is an integer multiple of 2, namely 0 × 2. As a… …   Wikipedia

  • History of computing hardware — Computing hardware is a platform for information processing (block diagram) The history of computing hardware is the record of the ongoing effort to make computer hardware faster, cheaper, and capable of storing more data. Computing hardware… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”