**Application of ECM to a Class of RSA keys**

*Abderrahmane Nitaj*

**Abstract: **Let $N=pq$ be an RSA modulus where $p$, $q$ are large
primes of the same bitsize and
$\phi(N)=(p-1)(q-1)$. We study
the class of the public exponents $e$ for which there exist
integers $X$, $Y$, $Z$ satisfying
$$eX+\phi(N)Y=NZ,$$
with $\vert
XY\vert <{\sqrt{2}\over 6}N^{1\over 2}$ and all
prime
factors
of
$\vert Y\vert$ are less than $10^{40}$. We
show that these
exponents are of improper use in RSA cryptosystems and that their
number
is at least
$O\left(N^{{1\over
2}-\e}\right)$ where $\e$ is a small positive constant. Our method
combines
continued
fractions, Coppersmith's lattice-based technique for finding small
roots
of bivariate polynomials and H. W. Lenstra's elliptic curve
method
(ECM) for factoring.

**Category / Keywords: **RSA cryptosystem, Continued fractions, Coppersmith's algorithm, Elliptic curve method, LLL algorithm

**Date: **received 7 Jul 2006

**Contact author: **nitaj at math unicaen fr

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20060713:072032 (All versions of this report)

**Short URL: **ia.cr/2006/235

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]