000170537 001__ 170537
000170537 005__ 20180501105956.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_LIB
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$$pIC$$pthesis-bn2018$$pDOI2$$pDOI$$pthesis
000170537 918__ $$aIC$$cIIF$$dEDIC2005-2015
000170537 919__ $$aLACAL
000170537 920__ $$b2012
000170537 970__ $$a5291/THESES
000170537 973__ $$aEPFL$$sPUBLISHED
000170537 980__ $$aTHESIS