170537
20180501105956.0
10.5075/epfl-thesis-5291
doi
urn:nbn:ch:bel-epfl-thesis5291-5
urn
6725602
nebis
THESIS_LIB
eng
5291
On the Cryptanalysis of Public-Key Cryptography
Lausanne
2012
EPFL
2012
152
Theses
Nowadays, 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.
cryptanalysis
public-key cryptography
integer factorization
elliptic curve discrete logarithm problem
arithmetic
cryptanalyse
cryptographie à clef publique
factorisation des entiers
problème de logarithme discret sur une courbe elliptique
arithmétique
Bos, Joppe Willem
Lenstra, Arjen K.
dir.
171548
244290
Texte intégral / Full text
1239994
Texte intégral / Full text
http://infoscience.epfl.ch/record/170537/files/EPFL_TH5291.pdf
LACAL
252286
U11265
oai:infoscience.tind.io:170537
IC
DOI
DOI2
thesis-bn2018
thesis
IC
IIF
EDIC2005-2015
LACAL
2012
5291/THESES
EPFL
PUBLISHED
THESIS