000170537 001__ 170537
000170537 005__ 20190118220145.0
000170537 0247_ $$2doi$$a10.5075/epfl-thesis-5291
000170537 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis5291-5
000170537 02471 $$2nebis$$a6725602
000170537 037__ $$aTHESIS
000170537 041__ $$aeng
000170537 088__ $$a5291
000170537 245__ $$aOn the Cryptanalysis of Public-Key Cryptography
000170537 269__ $$a2012
000170537 260__ $$aLausanne$$bEPFL$$c2012
000170537 300__ $$a152
000170537 336__ $$aTheses
000170537 520__ $$aNowadays, the most popular public-key cryptosystems are  based on either the integer factorization or the discrete  logarithm problem. The feasibility of solving these  mathematical problems in practice is studied and techniques  are presented to speed-up the underlying arithmetic on  parallel architectures. The fastest known approach to solve the discrete logarithm  problem in groups of elliptic curves over finite fields is  the Pollard rho method. The negation map can be used to speed  up this calculation by a factor √2. It is well known  that the random walks used by Pollard rho when combined with  the negation map get trapped in fruitless cycles. We show  that previously published approaches to deal with this  problem are plagued by recurring cycles, and we propose  effective alternative countermeasures. Furthermore, fast  modular arithmetic is introduced which can take advantage of  prime moduli of a special form using efficient "sloppy  reduction." The effectiveness of these techniques is  demonstrated by solving a 112-bit elliptic curve discrete  logarithm problem using a cluster of PlayStation 3 game  consoles: breaking a public-key standard and setting a new  world record. The elliptic curve method (ECM) for integer factorization  is the asymptotically fastest method to find relatively small  factors of large integers. From a cryptanalytic point of view  the performance of ECM gives information about secure  parameter choices of some cryptographic protocols. We  optimize ECM by proposing carry-free arithmetic modulo  Mersenne numbers (numbers of the form 2M  – 1) especially suitable for parallel architectures.  Our implementation of these techniques on a cluster of  PlayStation 3 game consoles set a new record by finding a  241-bit prime factor of 21181 – 1. A normal form for elliptic curves introduced by Edwards  results in the fastest elliptic curve arithmetic in practice.  Techniques to reduce the temporary storage and enhance the  performance even further in the setting of ECM are presented.  Our results enable one to run ECM efficiently on  resource-constrained platforms such as graphics processing  units.
000170537 6531_ $$acryptanalysis
000170537 6531_ $$apublic-key cryptography
000170537 6531_ $$ainteger factorization
000170537 6531_ $$aelliptic curve discrete logarithm problem
000170537 6531_ $$aarithmetic
000170537 6531_ $$acryptanalyse
000170537 6531_ $$acryptographie à clef publique
000170537 6531_ $$afactorisation des entiers
000170537 6531_ $$aproblème de logarithme discret sur une courbe elliptique
000170537 6531_ $$aarithmétique
000170537 700__ $$aBos, Joppe Willem
000170537 720_2 $$0244290$$aLenstra, Arjen K.$$edir.$$g171548
000170537 8564_ $$s1239994$$uhttps://infoscience.epfl.ch/record/170537/files/EPFL_TH5291.pdf$$yTexte intégral / Full text$$zTexte intégral / Full text
000170537 909C0 $$0252286$$pLACAL$$xU11265
000170537 909CO $$ooai:infoscience.tind.io:170537$$pthesis-bn2018$$pDOI$$pIC$$pthesis$$qDOI2$$qGLOBAL_SET
000170537 918__ $$aIC$$cIIF$$dEDIC2005-2015
000170537 919__ $$aLACAL
000170537 920__ $$b2012
000170537 970__ $$a5291/THESES
000170537 973__ $$aEPFL$$sPUBLISHED
000170537 980__ $$aTHESIS