Cryptology ePrint Archive: Report 2016/382

Faster elliptic-curve discrete logarithms on FPGAs

Daniel J. Bernstein and Susanne Engels and Tanja Lange and Ruben Niederhagen and Christof Paar and 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.

Category / Keywords: implementation / attacks, FPGAs, ECC, binary curves, Pollard rho, negation

Date: received 14 Apr 2016, last revised 28 Dec 2016

Contact author: ruben at polycephaly org

Available format(s): PDF | BibTeX Citation

Version: 20161228:181432 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]