On the Use of the Negation Map in the Pollard Rho Method

Joppe Willem Bos, Thorsten Kleinjung, Arjen Lenstra
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa, 2010
Article de conférence

Résumé

The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. 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. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of root 2 generally reported in the literature, it is supported by practical evidence.

Official source

https://infoscience.epfl.ch/record/164553?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

On the Cryptanalysis of Public-Key Cryptography

Joppe Willem Bos

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.

EPFL2012

Chargement

On the Analysis of Public-Key Cryptologic Algorithms

Andrea Miele

The RSA cryptosystem introduced in 1977 by Ron Rivest, Adi Shamir and Len Adleman is the most commonly deployed public-key cryptosystem. Elliptic curve cryptography (ECC) introduced in the mid 80's by Neal Koblitz and Victor Miller is becoming an increasingly popular alternative to RSA offering competitive performance due the use of smaller key sizes. Most recently hyperelliptic curve cryptography (HECC) has been demonstrated to have comparable and in some cases better performance than ECC. The security of RSA relies on the integer factorization problem whereas the security of (H)ECC is based on the (hyper)elliptic curve discrete logarithm problem ((H)ECDLP). In this thesis the practical performance of the best methods to solve these problems is analyzed and a method to generate secure ephemeral ECC parameters is presented. The best publicly known algorithm to solve the integer factorization problem is the number field sieve (NFS). Its most time consuming step is the relation collection step. We investigate the use of graphics processing units (GPUs) as accelerators for this step. In this context, methods to efficiently implement modular arithmetic and several factoring algorithms on GPUs are presented and their performance is analyzed in practice. In conclusion, it is shown that integrating state-of-the-art NFS software packages with our GPU software can lead to a speed-up of 50%. In the case of elliptic and hyperelliptic curves for cryptographic use, the best published method to solve the (H)ECDLP is the Pollard rho algorithm. This method can be made faster using classes of equivalence induced by curve automorphisms like the negation map. We present a practical analysis of their use to speed up Pollard rho for elliptic curves and genus 2 hyperelliptic curves defined over prime fields. As a case study, 4 curves at the 128-bit theoretical security level are analyzed in our software framework for Pollard rho to estimate their practical security level. In addition, we present a novel many-core architecture to solve the ECDLP using the Pollard rho algorithm with the negation map on FPGAs. This architecture is used to estimate the cost of solving the Certicom ECCp-131 challenge with a cluster of FPGAs. Our design achieves a speed-up factor of about 4 compared to the state-of-the-art. Finally, we present an efficient method to generate unique, secure and unpredictable ephemeral ECC parameters to be shared by a pair of authenticated users for a single communication. It provides an alternative to the customary use of fixed ECC parameters obtained from publicly available standards designed by untrusted third parties. The effectiveness of our method is demonstrated with a portable implementation for regular PCs and Android smartphones. On a Samsung Galaxy S4 smartphone our implementation generates unique 128-bit secure ECC parameters in 50 milliseconds on average.

EPFL2015

Chargement

We explore a few algebraic and geometric structures, through certain questions posed by modern cryptography. We focus on the cases of discrete logarithms in finite fields of small characteristic, the structure of isogeny graphs of ordinary abelian varieties, and the geometry of ideals in cyclotomic rings. The presumed difficulty of computing discrete logarithms in certain groups is essential for the security of a number of communication protocols deployed today. One of the most classic choices for the underlying group is the multiplicative group of a finite field. Yet this choice is showing its age, and particularly when the characteristic of the field is small: recent algorithms allow to compute logarithms efficiently in these groups. However, these methods are only heuristic: they seem to always work, yet we do not know how to prove it. In the first part, we propose to study these methods in the hope to get a better understanding, notably by revealing the geometric structures at play. A more modern choice is the group of rational points of an elliptic curve defined over a finite field. There, the difficulty of the discrete logarithm problem seems at its peak. More generally, the group of rational points of an abelian variety (notably the Jacobian of a curve of small genus) could be appropriate. One of the main tools for studying discrete logarithms on such objects is the notion of isogeny: a morphism from a variety to another one, which allows, among other things, to transfer the computation of a logarithm. Whereas the theory for elliptic curves is already mature, little is known about the structures formed by these isogenies (the isogeny graphs) for varieties of higher dimension. In the second part, we study the structure of isogeny graphs of absolutely simple, ordinary abelian varieties, with a few consequences regarding discrete logarithms on Jacobians of hyperelliptic curves of genus 2, the main object of concern of so-called hyperelliptic cryptography. The security of quite a few protocols, notably those relying on discrete logarithms, would collapse in front of an adversary equipped with a large-scale quantum computer. This perspective motivates cryptographers to study problems that would resist this technological feat. One of the major directions is cryptography based on Euclidean lattices, relying on the difficulty to find short vectors in a given lattice. For efficiency, one benefits from considering lattices endowed with more structure, such as the ideals of a cyclotomic field. In the third part, we study the geometry of these ideals, and show that a quantum computer allows to efficiently find much shorter vectors in these ideals than is currently possible in generic lattices.

EPFL2018

Chargement

On the Analysis of Public-Key Cryptologic Algorithms

Andrea Miele

EPFL2015

EPFL2018

On the Cryptanalysis of Public-Key Cryptography

Joppe Willem Bos

EPFL2012