Special number field sieve | EPFL Graph Search

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it. The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer n is of the form: :\exp\left(\left(1+o(1)\right)\left(\tfrac{32}{9}\log n\right)^{1/3}\left(\log\log n\right)^{2/3}\right)=L_n\left[1/3,(32/9)^{1/3}\right] in O and L-notations. The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorization have been numbers factored by SNFS. Overview of method The SNFS is based on an idea similar to the much simpler rational sieve; in

A kilobit special number field sieve factorization

Thorsten Kleinjung, Arjen Lenstra, Dag Arne Osvik

We describe how we reached a new factoring milestone by completing the first special number field sieve factorization of a number having more than 1024 bits, namely the Mersenne number 21039 -1. Although this factorization is orders of magnitude 'easier' than a factorization of a 1024-bit RSA modulus is believed to be, the methods we used to obtain our result shed new light on the feasibility of the latter computation. © International Association for Cryptology Research 2007.

2007

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

Factorization of RSA-140 using the number field sieve

Arjen Lenstra, Pénélope Leyland, Patric Zimmermann

On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper.

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa1999

On the Analysis of Public-Key Cryptologic Algorithms

Andrea Miele

EPFL2015