## CryptoDB

### Emmanuel Thomé

#### Affiliation: Inria

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
Abstract

We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.
The last page of this paper also reports on the factorization of RSA-250.

2014

EUROCRYPT

2010

EPRINT

Factorization of a 768-bit RSA modulus
Abstract

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.

2008

EPRINT

Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms
Abstract

This paper extends Joux-Naccache-Thom\'e's $e$-th root algorithm to the static Diffie-Hellman problem ({\sc sdhp}).
The new algorithm can be adapted to diverse finite fields by customizing it with an {\sc nfs}-like core or an {\sc ffs}-like
core.
In both cases, after a number of {\sc sdhp} oracle queries, the attacker builds-up the ability to solve new {\sc sdhp} instances {\sl unknown before the query phase}.
While sub-exponential, the algorithm is still significantly faster than all currently known {\sc dlp} and {\sc sdhp} resolution methods.
We explore the applicability of the technique to various cryptosystems.
The attacks were implemented in ${\mathbb F}_{2^{1025}}$ and also in ${\mathbb F}_{p}$, for a $516$-bit $p$.

2007

EPRINT

When e-th Roots Become Easier Than Factoring
Abstract

We show that computing $e$-th roots modulo $n$ is easier than
factoring $n$ with currently known methods, given subexponential
access to an oracle outputting the roots of numbers of the form
$x_i + c$.
Here $c$ is fixed and $x_i$ denotes small integers of the
attacker's choosing.
Several variants of the attack are presented, with varying
assumptions on the oracle, and goals ranging from selective to
universal forgeries. The computational complexity of the attack
is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant
situations, which matches the {\sl
special} number field sieve's ({\sc snfs}) complexity.
This sheds additional light on {\sc rsa}'s malleability in
general and on {\sc rsa}'s resistance to affine forgeries in
particular -- a problem known to be polynomial for $x_i >
\sqrt[3]{n}$, but for which no algorithm faster than factoring
was known before this work.

2004

EPRINT

A double large prime variation for small genus hyperelliptic index calculus
Abstract

In this article, we examine how the index calculus approach for computing
discrete logarithms in small genus hyperelliptic curves can be improved
by introducing a double large prime variation. Two algorithms are
presented. The first algorithm is a rather natural adaptation of the
double large prime variation to the intended context. On heuristic and
experimental grounds, it seems to perform quite well but lacks a
complete and precise analysis. Our second algorithm is a considerably
simplified variant, which can be analyzed easily. The resulting
complexity improves on the fastest known algorithms. Computer experiments
show that for hyperelliptic curves of genus three, our first algorithm
surpasses Pollard's Rho method even for rather small field sizes.

#### Program Committees

- Eurocrypt 2016

#### Coauthors

- Kazumaro Aoki (2)
- Razvan Barbulescu (2)
- Joppe W. Bos (2)
- Fabrice Boudot (1)
- Cyril Bouvier (1)
- Jérémie Detrey (1)
- Claus Diem (2)
- Andreas Enge (1)
- Jens Franke (2)
- Joshua Fried (1)
- Pierrick Gaudry (8)
- Aurore Guillevic (1)
- Nadia Heninger (2)
- Sorina Ionica (1)
- Hamza Jeljeli (1)
- Antoine Joux (4)
- Thorsten Kleinjung (2)
- Alexander Kruppa (2)
- Arjen K. Lenstra (2)
- Reynald Lercier (1)
- Peter L. Montgomery (2)
- David Naccache (3)
- Dag Arne Osvik (2)
- Herman J. J. te Riele (2)
- Nicolas Thériault (1)
- Andrey Timofeev (2)
- Marion Videau (1)
- Paul Zimmermann (4)