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 cryptographydiscrete logarithm problemKoblitz curvehardware designFPGAdiscrete 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/368}},
      url = {https://eprint.iacr.org/2014/368}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.