Paper 2009/541
Breaking ECC2K-130
Daniel V. Bailey, Lejla Batina, Daniel J. Bernstein, Peter Birkner, Joppe W. Bos, Hsieh-Chung Chen, Chen-Mou Cheng, Gauthier van Damme, Giacomo de Meulenaer, Luis Julian Dominguez Perez, Junfeng Fan, Tim Güneysu, Frank Gurkaynak, Thorsten Kleinjung, Tanja Lange, Nele Mentens, Ruben Niederhagen, Christof Paar, Francesco Regazzoni, Peter Schwabe, Leif Uhsadel, Anthony Van Herrewege, and Bo-Yin Yang
Abstract
Elliptic-curve cryptography is becoming the standard public-keyprimitive not only for mobile devices but also for high-securityapplications.Advantages are the higher cryptographicstrength per bit in comparison with RSA and the higher speed inimplementations.To improve understanding of the exact strength of the elliptic-curvediscrete-logarithm problem, Certicom has published a series ofchallenges. This paper describes breaking the ECC2K-130 challengeusing a parallelized version of Pollard's rho method.This is a major computation bringing together the contributions ofseveral 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 ofplatforms: CPUs, Cells, GPUs, FPGAs, and ASICs; * details about running the attack.
Metadata
- Available format(s)
PDF- Category
- Implementation
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- AttacksECCbinary fieldsDLPKoblitz curvesautomorphismsparallelized Pollard rhoCerticom challenges.
- Contact author(s)
- tanja @hyperelliptic org
- History
- 2009-11-18: last of 4 revisions
- 2009-11-08: received
- See all versions
- Short URL
- https://ia.cr/2009/541
- License
CC BY
BibTeX
@misc{cryptoeprint:2009/541, author = {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}, title = {Breaking {ECC2K}-130}, howpublished = {Cryptology {ePrint} Archive, Paper 2009/541}, year = {2009}, url = {https://eprint.iacr.org/2009/541}}