Abstract | ||
---|---|---|
A major cryptanalytic computation is currently underway on multiple platforms, including standard CPUs, FPGAs, PlayStations and Graphics Processing Units (CPUs), to break the Certicom ECC2K-130 challenge. This challenge is to compute an elliptic-curve discrete logarithm on a Koblitz curve over F-2131. 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 CPU software performs more than 63 million iterations per second, including 320 million F-2131 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-17401-8_23 | PROGRESS IN CRYPTOLOGY - INDOCRYPT 2010 |
Keywords | Field | DocType |
Graphics Processing Unit (GPU), Elliptic Curve Cryptography, Pollard rho, qhasm | Graphics,Computer science,CUDA,Parallel computing,Field-programmable gate array,Theoretical computer science,Elliptic curve cryptography,Discrete logarithm,Computation | Journal |
Volume | ISSN | Citations |
6498 | 0302-9743 | 6 |
PageRank | References | Authors |
0.45 | 5 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniel J. Bernstein | 1 | 1734 | 110.56 |
Hsieh-Chung Chen | 2 | 36 | 4.85 |
Chen-Mou Cheng | 3 | 295 | 28.77 |
Tanja Lange | 4 | 1170 | 71.41 |
Ruben Niederhagen | 5 | 143 | 16.76 |
Peter Schwabe | 6 | 759 | 44.16 |
Bo-Yin Yang | 7 | 9 | 1.32 |