Home > On the Cryptanalysis of Public-Key Cryptography > HTML MARC |

000170537 001__ 170537 000170537 005__ 20180128032803.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_ $$iINTERNAL$$uhttps://infoscience.epfl.ch/record/170537/files/EPFL_TH5291.pdf$$xPUBLIC$$zTexte intégral / Full text 000170537 909C0 $$0252286$$pLACAL 000170537 909CO $$ooai:infoscience.tind.io:170537$$pIC$$pthesis-bn2018$$pthesis 000170537 918__ $$aIC$$cIIF$$dEDIC2005-2015 000170537 919__ $$aLACAL 000170537 920__ $$b2012 000170537 970__ $$a5291/THESES 000170537 973__ $$aEPFL$$sPUBLISHED 000170537 980__ $$aTHESIS