Paper 2012/002

ECC2K-130 on NVIDIA GPUs

Daniel J. Bernstein, Hsieh-Chung Chen, Chen-Mou Cheng, Tanja Lange, Ruben Niederhagen, Peter Schwabe, and Bo-Yin Yang

Abstract

A major cryptanalytic computation is currently underway on multiple platforms, including standard CPUs, FPGAs, PlayStations and GPUs, to break the Certicom ECC2K-130 challenge. This challenge is to compute an elliptic-curve discrete logarithm on a Koblitz curve over F_2^131 . Optimizations have reduced the cost of the computation to approximately 2^77 bit operations in 2^61 iterations. GPUs are not designed for fast binary-field arithmetic; they are designed for highly vectorizable floating-point computations that fit into very small amounts of static RAM. This paper explains how to optimize the ECC2K-130 computation for this unusual platform. The resulting GPU software performs more than 63 million iterations per second, including 320 million F_2^131 multiplications per second, on a $500 NVIDIA GTX 295 graphics card. The same techniques for finite-field arithmetic and elliptic-curve arithmetic can be reused in implementations of larger systems that are secure against similar attacks, making GPUs an interesting option as coprocessors when a busy Internet server has many elliptic-curve operations to perform in parallel.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Updated version of paper at Indocrypt 2010
Keywords
Graphics Processing Unit (GPU)Elliptic Curve CryptographyPollard rhoqhasm
Contact author(s)
tanja @ hyperelliptic org
History
2012-01-02: received
Short URL
https://ia.cr/2012/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/002,
      author = {Daniel J.  Bernstein and Hsieh-Chung Chen and Chen-Mou Cheng and Tanja Lange and Ruben Niederhagen and Peter Schwabe and Bo-Yin Yang},
      title = {ECC2K-130 on NVIDIA GPUs},
      howpublished = {Cryptology ePrint Archive, Paper 2012/002},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/002}},
      url = {https://eprint.iacr.org/2012/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.