[Resource Topic] 2006/235: Application of ECM to a Class of RSA keys

Welcome to the resource topic for 2006/235

Application of ECM to a Class of RSA keys

Authors: Abderrahmane Nitaj


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.

ePrint: https://eprint.iacr.org/2006/235

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .