International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Application of ECM to a Class of RSA keys

Authors:
Abderrahmane Nitaj
Download:
URL: http://eprint.iacr.org/2006/235
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21728,
  title={Application of ECM to a Class of RSA keys},
  booktitle={IACR Eprint archive},
  keywords={RSA cryptosystem, Continued fractions,  Coppersmith's  algorithm, Elliptic curve method, LLL algorithm},
  url={http://eprint.iacr.org/2006/235},
  note={ nitaj@math.unicaen.fr 13336 received 7 Jul 2006},
  author={Abderrahmane Nitaj},
  year=2006
}