Paper 2015/143

Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs

Erich Wenger and Paul Wolfger

Abstract

Computing discrete logarithms takes time. It takes time to develop new algorithms, choose the best algorithms, implement these algorithms correctly and efficiently, keep the system running for several months, and, finally, publish the results. In this paper, we present a highly performant architecture that can be used to compute discrete logarithms of Weierstrass curves defined over binary fields and Koblitz curves using FPGAs. We used the architecture to compute for the first time a discrete logarithm of the elliptic curve \texttt{sect113r1}, a previously standardized binary curve, using 10 Kintex-7 FPGAs. To achieve this result, we investigated different iteration functions, used a negation map, dealt with the fruitless cycle problem, built an efficient FPGA design that processes 900 million iterations per second, and we tended for several months the optimized implementations running on the FPGAs.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. MINOR revision.Journal of Cryptographic Engineering
Keywords
elliptic curve cryptographydiscrete logarithm problemhardware designFPGAnegation map
Contact author(s)
wenger erich @ gmail com
History
2015-08-17: revised
2015-02-27: received
See all versions
Short URL
https://ia.cr/2015/143
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/143,
      author = {Erich Wenger and Paul Wolfger},
      title = {Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs},
      howpublished = {Cryptology ePrint Archive, Paper 2015/143},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/143}},
      url = {https://eprint.iacr.org/2015/143}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.