Welcome to the resource topic for 2001/007
Title:
Are ‘Strong’ Primes Needed for RSA
Authors: Ron Rivest, 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.
ePrint: https://eprint.iacr.org/2001/007
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .