Publication
Factorization of a 512 bit RSA modulus
Publications associées (20)
The double exponential runtime is tight for 2-stage stochastic ILPs
Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...
SPRINGER HEIDELBERG2022Computation of a 768-Bit Prime Field Discrete Logarithm
Arjen Lenstra, Thorsten Kleinjung
This paper reports on the number field sieve computation of a 768-bit prime field discrete logarithm, describes the different parameter optimizations and resulting algorithmic changes compared to the factorization of a 768-bit RSA modulus, and briefly disc ...
Springer International Publishing Ag2017On the Analysis of Public-Key Cryptologic Algorithms
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 increasin ...
EPFL2015Cofactorization on Graphics Processing Units
Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung, Andrea Miele
We show how the cofactorization step, a compute-intensive part of the relation collection phase of the number field sieve (NFS), can be farmed out to a graphics processing unit. Our implementation on a GTX 580 GPU, which is integrated with a state-of-the-a ...
Springer-Verlag Berlin2014A sieve algorithm based on overlattices
In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...
Cambridge Univ Press2014A heterogeneous computing environment to solve the 768-bit RSA challenge
Arjen Lenstra, Pénélope Leyland, Pascal Jermini, Joppe Willem Bos, Thorsten Kleinjung, Dag Arne Osvik, Michela Thiémard, Heinz Stockinger
In December 2009 the 768-bit, 232-digit number RSA-768 was factored using the number field sieve. Overall, the computational challenge would take more than 1700 years on a single, standard core. In the article we present the heterogeneous computing approac ...
Springer Verlag2012On the Cryptanalysis of Public-Key Cryptography
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 ...
EPFL2012Factorization of a 768-Bit RSA Modulus
Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung, Dag Arne Osvik, Patric Zimmermann
This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA. ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010A kilobit special number field sieve factorization
Arjen Lenstra, Thorsten Kleinjung, 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 ...
2007VSH, an efficient and provable collision-resistant hash function
We introduce VSH, very smooth hash, a new S-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an S-bit composite. By very smooth, we mean that the smoothnes ...
Springer Verlag2006