Breaking ECC2K-130
DV Bailey, Lejla Batina, DJ Daniel Bernstein, Peter Birkner, JW Joppe Bos, Hsiang‐Cheng Chen, CM Cheng, Damme, van, D.A., Giacomo de Meulenaer, LJ Dominguez Perez, JingCun Fan, Tim E. Güneysu, Frank K. Gürkaynak, Tanja Lange, Nele Mentens, RF Ruben Niederhagen, Christof Paar, F. Regazzoni, Peter Schwabe, Leif Uhsadel · IACR Cryptology ePrint Archive · 2009
Elliptic-curve cryptography is becoming the standard public-key primitive not only for mobile devices but also for high-security applications. Advantages are the higher crypto- graphic strength per bit in comparison with RSA and the higher speed in implementations. To improve understanding of the exact strength of the elliptic-curve discrete-logarithm problem, Certicom has published a series of challenges. This paper describes breaking the ECC2K-130 challenge using a parallelized version of Pollard's rho method. This is a major computation bringing together the contributions of several clusters of conventional computers, PlayStation 3 clusters, computers with powerful graphics cards and FPGAs. We also give estimates for an ASIC design. In particular we present - our choice and analysis of the iteration function for the rho method; - our choice of finite field arithmetic and representation; - detailed descriptions of the implementations on a multitude of platforms: CPUs, Cells, GPUs, FPGAs, and ASICs; - timings for CPUs, Cells, GPUs, and FPGAs; and