Paper 2001/007

Are 'Strong' Primes Needed for RSA

Ron Rivest and Robert Silverman

Abstract

We review the arguments in favor of using so-called ``strong primes'' in the RSA public-key cryptosystem. There are two types of such arguments: those that say that strong primes are needed to protect against factoring attacks, and those that say that strong primes are needed to protect against ``cycling'' attacks (based on repeated encryption). We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem. That is, by using strong primes one gains a negligible increase in security over what is obtained merely by using ``random'' primes of the same size. There are two parts to this argument. First, the use of strong primes provides no additional protection against factoring attacks, because Lenstra's method of factoring based on elliptic curves (ECM) circumvents any protection that might have been offered by using strong primes. The methods that 'strong' primes are intended to guard against, as well as ECM, are probabalistic in nature, but ECM succeeds with higher probability. For RSA key sizes being proposed now, the probability of success of these methods is very low. Additionally, the newer Number Field Sieve algorithm can factor RSA keys with certainty in less time than these methods. Second, a simple group-theoretic argument shows that cycling attacks are extremely unlikely to be effective, as long as the primes used are large. Indeed, even probabalistic factoring attacks will succeed much more quickly and with higher probability than cycling attacks.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
rsilverman @ rsasecurity com
History
2001-01-30: received
Short URL
https://ia.cr/2001/007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/007,
      author = {Ron Rivest and Robert Silverman},
      title = {Are 'Strong' Primes Needed for RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2001/007},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/007}},
      url = {https://eprint.iacr.org/2001/007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.