ECC2K-130 on NVIDIA GPUs

D.J. Bernstein, H.-C. Chen, C.M. Cheng, T. Lange, R.F. Niederhagen, P. Schwabe, B.Y. Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)
322 Downloads (Pure)

Abstract

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 $\rm F_{2^{131}}$ . Optimizations have reduced the cost of the computation to approximately 277 bit operations in 261 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 $\rm 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.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2010 (11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings)
EditorsG. Gong, K.C. Gupta
Place of PublicationBerlin
PublisherSpringer
Pages328-346
ISBN (Print)978-3-642-17400-1
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
Volume6498
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'ECC2K-130 on NVIDIA GPUs'. Together they form a unique fingerprint.

Cite this