ECC2K-130 on NVIDIA GPUs
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
@article{bernstein2010ecc2k,
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},
pages={328–346},
year={2010},
publisher={Springer}
}
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.
March 2, 2011 by hgpu
