Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster

Erich Wenger; Paul Wolfger

Paper 2014/368

Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster

Erich Wenger and Paul Wolfger

Abstract

Using FPGAs to compute the discrete logarithms of elliptic curves is a well-known method. However, until to date only CPU clusters succeeded in computing new elliptic curve discrete logarithm records. This work presents a high-speed FPGA implementation that was used to compute the discrete logarithm of a 113-bit Koblitz curve. The core of the design is a fully unrolled, highly pipelined, self-sufficient Pollard's rho iteration function. An 18-core Virtex-6 FPGA cluster computed the discrete logarithm of a 113-bit Koblitz curve in extrapolated 24 days. Until to date, no attack on such a large Koblitz curve succeeded using as little resources or in such a short time frame.

Note: Camera ready version of paper from Selected Areas in Cryptography 2014

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Selected Areas in Cryptography 2014
Keywords: elliptic curve cryptography discrete logarithm problem Koblitz curve hardware design FPGA discrete logarithm record
Contact author(s): erich wenger @ iaik tugraz at
History: 2014-08-26: last of 5 revisions; 2014-05-27: received; See all versions
Short URL: https://ia.cr/2014/368
License: CC BY

BibTeX

@misc{cryptoeprint:2014/368,
      author = {Erich Wenger and Paul Wolfger},
      title = {Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an {FPGA} Cluster},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/368},
      year = {2014},
      url = {https://eprint.iacr.org/2014/368}
}