Breaking ECC2K-130
Peter Schwabe (Eindhoven University of Technology )
Thursday 20 May 2010, 15.00, b-it 1.25 (cosec meeting room)
Contents
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.