Paper 2016/382

Faster elliptic-curve discrete logarithms on FPGAs

Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann

Abstract

This paper accelerates FPGA computations of discrete logarithms on elliptic curves over binary fields. As a toy example, this paper successfully attacks the SECG standard curve sect113r2, a binary elliptic curve that was not removed from the SECG standard until 2010 and was not disabled in OpenSSL until June 2015. This is a new size record for completed ECDL computations, using a prime order very slightly larger than the previous record holder. More importantly, this paper uses FPGAs much more efficiently, saving a factor close to 3/2 in the size of each high-speed ECDL core. This paper squeezes 3 cores into a low-cost Spartan-6 FPGA and many more cores into larger FPGAs. The paper also benchmarks many smaller-size attacks to demonstrate reliability of the estimates, and covers a much larger curve over a 127-bit field to demonstrate scalability.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
attacksFPGAsECCbinary curvesPollard rhonegation
Contact author(s)
ruben @ polycephaly org
History
2016-12-28: last of 3 revisions
2016-04-15: received
See all versions
Short URL
https://ia.cr/2016/382
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/382,
      author = {Daniel J.  Bernstein and Susanne Engels and Tanja Lange and Ruben Niederhagen and Christof Paar and Peter Schwabe and Ralf Zimmermann},
      title = {Faster elliptic-curve discrete logarithms on FPGAs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/382},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/382}},
      url = {https://eprint.iacr.org/2016/382}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.