Daniel J. Bernstein, Hsieh-Chung Chen, Chen-Mou Cheng, Tanja Lange, Ruben Niederhagen, Peter Schwabe, Bo-Yin Yang
Department of Computer Science, University of Illinois as Chicago, 851 S. Morgan Street, Chicago, IL, 60607-7053, USA
Progress in Cryptology – INDOCRYPT 2010, Lecture Notes in Computer Science, 2010, Volume 6498/2010, 328-346


   title={ECC2K-130 on NVIDIA GPUs},

   author={Bernstein, D. and Chen, H.C. and Cheng, C.M. and Lange, T. and Niederhagen, R. and Schwabe, P. and Yang, B.Y.},

   journal={Progress in Cryptology-INDOCRYPT 2010},





Download Download (PDF)   View View   Source Source   



A major cryptanalytic computation is currently underway on multiple platforms, including standard CPUs, FPGAs, PlayStations and Graphics Processing Units (GPUs), to break the Certicom ECC2K-130 challenge. This challenge is to compute an elliptic-curve discrete logarithm on a Koblitz curve over F2131. 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: