The safety of the well-known RSA cryptosystem is based on the fact that, in general, it is computationally very hard to factorize large integers. Given two large prime numbers p and q, the public key is the pair (N,e), where N=pq and e is called the exponent and satisfies gcd (e,(p-1)(q-1)) = 1. The private key is the pair (N,d) where d is the inverse of e modulo (p-1)(q-1). In general, to compute d from e, knowledge of both p and q is required, and so it is in general very hard to compute the private key from the public key, if p and q are large enough.
Quite a number of theoretical results are known on the factorization of large integers. In some cases--when p and q satisfy particular number-theoretic conditions--it might be feasible to compute p and q from a given N. So far, these results do not affect the general safety of the RSA cryptosystem, as it remains sufficient to choose the prime numbers p and q in such a way that particular attacks are not possible.
This paper describes such a particular attack in the case that gcd (e,(p2-1)(q2-1))=1. This attack is based on the following theorem, which is proved in the paper:
Let p,q be primes and q < p < 2q, and e be an exponent satisfying an equation
ex - (p2-1)(q2-1) y = zwith coprime positive integers x and y. If
xy < 2N - 4N3⁄4and
|z| < (p - q)N1⁄4y,then p and q can be computed in polynomial time in log(N).