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,(p²-1)(q²-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

with coprime positive integers x and y. If

and

then p and q can be computed in polynomial time in log(N).