Publications by Arjen Lenstra | EPFL Graph Search

Computation Of A 30750-Bit Binary Field Discrete Logarithm

Arjen Lenstra, Thorsten Kleinjung, Benjamin Pierre Charles Wesolowski, Robert Granger

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimina ...

AMER MATHEMATICAL SOC2021

STEP-Archival: Storage Integrity and Tamper Resistance Using Data Entanglement

Maxime Augier, Arjen Lenstra

2018

Computation 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 Ag2017

Efficient Ephemeral Elliptic Curve Cryptographic Keys

Arjen Lenstra, Andrea Miele

We show how any pair of authenticated users can on-the-fly agree on an elliptic curve group that is unique to their communication session, unpredictable to outside observers, and secure against known attacks. Our proposal is suitable for deployment on cons ...

Springer-Verlag Berlin2015

Cofactorization 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 Berlin2014

A heterogeneous computing environment to solve the 768-bit RSA challenge

Michela Thiémard, Pénélope Leyland, Pascal Jermini, Arjen Lenstra, Heinz Stockinger, Dag Arne Osvik, Joppe Willem Bos, Thorsten Kleinjung

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 Verlag2012

Chosen-prefix collisions for MD5 and applications

Arjen Lenstra

Springer Verlag2012

Solving 112-bit prime ECDLP on game consoles using sloppy reduction

Arjen Lenstra, Marcelo Kaihara, Joppe Willem Bos, Thorsten Kleinjung

We describe a cell processor implementation of Pollard’s rho method to solve discrete logarithms in groups of elliptic curves over prime fields. The implementation was used on a cluster of PlayStation 3 game consoles to set a new record. We present in deta ...

2012

Efficient SIMD arithmetic modulo a Mersenne number

Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung

This paper describes carry-less arithmetic operations modulo an integer 2^M − 1 in the thousand-bit range, targeted at single instruction multiple data platforms and applications where overall throughput is the main performance criterion. Using an implemen ...

IEEE Computer Soc Press2011

Factorization of a 768-Bit RSA Modulus

Arjen Lenstra, Dag Arne Osvik, Joppe Willem Bos, Thorsten Kleinjung, 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 Usa2010

Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate

Arjen Lenstra, Dag Arne Osvik

We present a refined chosen-prefix collision construction for MD5 that allowed creation of a rogue Certification Authority (CA) certificate, based on a collision with a regular end-user website certificate provided by a commercial CA. Compared to the previ ...

Springer Verlag2009

Improving the boneh-franklin traitor tracing scheme

Pascal Junod, Alexandre Karlov, Arjen Lenstra

Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by k traitors out of a static set of l legitimate users, then all traitors can be identified given the pirate key ...

Springer Verlag2009

Security observance throughout the life-cycle of embedded systems

Arjen Lenstra

Embedded systems are an established part of life. Their security requirements underline the importance of properly formulated, implemented, and enforced security policies throughout their life-cycle. Currently, security is just an afterthought, and most so ...

2008

MD5 considered harmful today, creating a rogue CA certificate

Arjen Lenstra, Dag Arne Osvik

2008

Information Security. Proceedings 10th International Conference, ISC 2007

Arjen Lenstra

The following topics were dealt with: intrusion detection; digital rights management; symmetric-key cryptography; cryptographic protocols; identify-based cryptography; cryptanalysis; network security; software obfuscation; public-key cryptosystems; ellipti ...

Springer2007

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

Arjen Lenstra

We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 2 50 calls to the MD5 compression function, for any two chosen message prefixes P and P′, suffixe ...

2007

A kilobit special number field sieve factorization

Arjen Lenstra, Dag Arne Osvik, Thorsten Kleinjung

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 ...

2007

Arjen Lenstra

Graph Chatbot

L Notation

Birthday Paradox

Integer Factoring

Computation Of A 30750-Bit Binary Field Discrete Logarithm

STEP-Archival: Storage Integrity and Tamper Resistance Using Data Entanglement

Computation of a 768-Bit Prime Field Discrete Logarithm

Efficient Ephemeral Elliptic Curve Cryptographic Keys

Cofactorization on Graphics Processing Units

A heterogeneous computing environment to solve the 768-bit RSA challenge

Chosen-prefix collisions for MD5 and applications

Solving 112-bit prime ECDLP on game consoles using sloppy reduction

Efficient SIMD arithmetic modulo a Mersenne number

Factorization of a 768-Bit RSA Modulus

Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate

Improving the boneh-franklin traitor tracing scheme

Security observance throughout the life-cycle of embedded systems

MD5 considered harmful today, creating a rogue CA certificate

Information Security. Proceedings 10th International Conference, ISC 2007

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

A kilobit special number field sieve factorization