Breaking ECC2K-130

Abstract

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