Paper 2006/235

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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSA cryptosystemContinued fractionsCoppersmith's algorithmElliptic curve methodLLL algorithm
Contact author(s)
nitaj @ math unicaen fr
History
2006-07-13: received
Short URL
https://ia.cr/2006/235
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/235,
      author = {Abderrahmane Nitaj},
      title = {Application of ECM to a Class of RSA keys},
      howpublished = {Cryptology ePrint Archive, Paper 2006/235},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/235}},
      url = {https://eprint.iacr.org/2006/235}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.