Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2010 

Breaking ECC2K-130

Peter Schwabe (Eindhoven University of Technology )

Thursday 20 May 2010, 15.00, b-it  1.25 (cosec meeting room)


How long does it take to break the elliptic-curve discrete-logarithm problem? This question is often answered with "O(\sqrt(n))", the asymptotic running time of the Pollard rho algorithm. However, to estimate how much money or machine years it takes to break a given ECDLP we have to look beyond this asymptotic answer, optimize the Pollard rho algorithm for the specific ECDLP and finally implement it. Currently a group of 12 research institutes is attempting to break the Certicom challenge ECC2K-130, an ECDLP on a 131-bit Koblitz curve. This talk will describe how exactly the parallelized Pollard rho algorithm is used to attack this challenge and explain platform-specific optimization techniques for two different architectures used to carry out the attack: The Cell Broadband Engine and NVIDIA GPUs.

Imprint, webmaster & more