Application of ECM to a Class of RSA keys

Abderrahmane Nitaj

Paper 2006/235

Application of ECM to a Class of RSA keys

Abderrahmane Nitaj

Abstract

Let $N = p q$ be an RSA modulus where $p$ , $q$ are large primes of the same bitsize and $ϕ (N) = (p - 1) (q - 1)$ . We study the class of the public exponents $e$ for which there exist integers $X$ , $Y$ , $Z$ satisfying with and all prime factors of are less than . We show that these exponents are of improper use in RSA cryptosystems and that their number is at least where 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 cryptosystem Continued fractions Coppersmith's algorithm Elliptic curve method LLL algorithm
Contact author(s): nitaj @ math unicaen fr
History: 2006-07-13: received
Short URL: https://ia.cr/2006/235
License: 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},
      url = {https://eprint.iacr.org/2006/235}
}