Welcome to the resource topic for 2006/235
Title:
Application of ECM to a Class of RSA keys
Authors: 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.
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 .