ECC2K-130 on NVIDIA GPUs

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

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 Cryptography Pollard rho qhasm
Contact author(s): tanja @ hyperelliptic org
History: 2012-01-02: received
Short URL: https://ia.cr/2012/002
License: 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}
}