RSA Laboratories

3.1.4 What are strong primes and are they necessary for the RSA system?

In the literature pertaining to the RSA algorithm, it has often been suggested that in choosing a key pair, one should use so-called "strong" primes p and q to generate the modulus n. Strong primes have certain properties that make the product n hard to factor by specific factoring methods; such properties have included, for example, the existence of a large prime factor of p-1 and a large prime factor of p+1. The reason for these concerns is that some factoring methods - for instance, the Pollard p-1 and p+1 methods (see Question 2.3.4) - are especially suited to primes p such that p-1 or p+1 has only small factors; strong primes are resistant to these attacks. Strong primes are required in for example ANSI X9.31 (see Question 5.3.1).

However, advances in factoring over the last ten years appear to have obviated the advantage of strong primes; the elliptic curve factoring algorithm is one such advance. The new factoring methods have as good a chance of success on strong primes as on "weak" primes. Therefore, choosing traditional "strong" primes alone does not significantly increase security. Choosing large enough primes is what matters. However, there is no danger in using strong, large primes, though it may take slightly longer to generate a strong prime than an arbitrary prime.

It is possible that new factoring algorithms may be developed in the future which once again target primes with certain properties. If this happens, choosing strong primes may once again help to increase security.

Top of the page