Question 11. Are Strong Primes Necessary in RSA?

In the literature pertaining to RSA, 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 are those with 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 are especially suited to primes p such that p -1 or p+1 has only small factors; strong primes are resistant to these attacks.

However, advances in factoring over the last ten years (see Question 48) 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 so, choosing strong primes may once again help to increase security.



| Question 12 |
| Back to FAQ INDEX |
|RSA Labs' FAQ Home | RSA Home | What's New? |
| RSA & Partner Products | FTP Server | About ... |
| Contact Sales | Contact Technical Support |



Contact RSA Laboratories:
100 Marine Parkway, Suite 500
Redwood City, CA
94065-1031

phone: 415-595-8782
fax: 415-595-1873
Website: http://www.rsa.com/rsalabs/



Website feedback or comments can be sent to : WEBMAVEN@RSA.COM

Copyright ©1996, RSA Laboratories, Inc. All Rights Reserved.
Last Updated: Friday, May 24, 1996