Cryptology ePrint Archive: Report 2009/541
Breaking ECC2K-130
Daniel V. Bailey and Lejla Batina and Daniel J. Bernstein and Peter Birkner and Joppe W. Bos and Hsieh-Chung Chen and Chen-Mou Cheng and Gauthier van Damme and Giacomo de Meulenaer and Luis Julian Dominguez Perez and Junfeng Fan and Tim Güneysu and Frank Gurkaynak and Thorsten Kleinjung and Tanja Lange and Nele Mentens and Ruben Niederhagen and Christof Paar and Francesco Regazzoni and Peter Schwabe and Leif Uhsadel and Anthony Van Herrewege and Bo-Yin Yang
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 cryptographic
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
/preseestimates 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; * details about running the attack.
Category / Keywords: implementation / Attacks, ECC, binary fields, DLP, Koblitz curves, automorphisms, parallelized Pollard rho, Certicom challenges.
Date: received 5 Nov 2009, last revised 18 Nov 2009
Contact author: tanja at hyperelliptic org
Available format(s): PDF | BibTeX Citation
Version: 20091118:131804 (All versions of this report)
Short URL: ia.cr/2009/541
[ Cryptology ePrint archive ]