Faster elliptic-curve discrete logarithms on FPGAs

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

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: attacks FPGAs ECC binary curves Pollard rho negation
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: 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},
      url = {https://eprint.iacr.org/2016/382}
}