10
$\begingroup$

It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?

$\endgroup$
  • 1
    $\begingroup$ "There's no longer a requisite of safe primes", said who? $\endgroup$ – fkraiem May 26 '17 at 11:54
  • 2
    $\begingroup$ Because the probability of randomly picking a non-safe prime is negliglible at current, standard sizes, but the risk was found to be too big back in the day when smaller key sizes were used. $\endgroup$ – SEJPM May 26 '17 at 11:54
  • 1
    $\begingroup$ @fkraiem The HAC said so back in the nineties: "These attacks are described at length in Note 8.8(iii); as noted there, it is now believed that strong primes offer little protection beyond that offered by random primes, since randomly selected primes of the sizes typically used in RSA moduli today will satisfy the constraints with high probability." (section 4.4.2 on page 149) And I think Boran is asking for why we don't explicitely check / search for strong / safe primes anymore. $\endgroup$ – SEJPM May 26 '17 at 11:58
  • $\begingroup$ Boran: Are you asking about safe primes (ie primes $p$ where $(p-1)/2$ is also prime) or strong primes? $\endgroup$ – SEJPM May 26 '17 at 12:00
  • $\begingroup$ the former, your answer was great though, thank you $\endgroup$ – boran May 26 '17 at 12:04
14
$\begingroup$

First we may want RSA primes to be something like a safe prime, ie a prime $p$ where $(p-1)/2$ is prime as well.

Back in 1974 Pollard found an algorithm to factor moduli whereby you can factor $N=pq$ if $p-1$ or $q-1$ are smooth, that is all prime-factors of $p-1$ or $q-1$ are smaller than a bound $B$. The algorithm will then factor $N$ in time $\mathcal O(B\cdot \log B\cdot \log^2N)$. This implies that you want at least one "large" prime factor for both $p-1$ and $q-1$ where large is probably something like $>2^{80}$ or a similar value to match your key strength.

The most "effective" solution is to pick $p,q$ as safe primes of course. In practice however it suffices if they are strong primes because:

  1. you can find those much quicker because the constraints are less severe and;
  2. there are other attacks against which a strong prime will protect you, such as p+1 factoring.

Now the argument is that the Elliptic-Curve Method is a strict generalization / improvement over Pollard's $p-1$ method in finding small factors as it allows one to "retry" if a "bad" group order (that is $p-1$) was encountered, this is the quote from Rivest's paper (see below):

Thus we see that it is useless to protect against factoring attacks by building in large prime factors into $p-1$ or $p+1$, since the enemy cryptanalyst can instead attempt to find an elliptic curve $E_{a,b}$ such that $|E_{a,b}|$ is smooth. The cryptographer has no control over whether $|E_{a,b}|$ is smooth or not, since this is essentially a random number approximately equal to $p$. Only by making $p$ sufficiently large can he adequately protect against such an attack.

If you want to dive further into the history of strong primes, I suggest you read "Are 'Strong' Primes Needed for RSA" by Rivest and Silverman from 1999.

I have used material from section 8.3 of said paper in my above answer. They go on after the above quote and actually list numbers for the probability of breaking random prime factors for 1024 bit moduli and find the chances to be negligible for ECM. As ECM is strictly better than $p-1$ factoring, random primes suffice.

$\endgroup$
  • 1
    $\begingroup$ As far as I know, there has been no recommendation to use safe primes (that is primes $p$ with $(p-1)/2$ also primes) in RSA. Definitely there was no such recommendation in the original RSA article. Safe primes are used in some algorithms of the Discrete-Log family; but if they have been used as secret factors of a public modulus in a factorization-based algorithm, I want to know! $\endgroup$ – fgrieu May 28 '17 at 8:40
  • $\begingroup$ I just re-invented a context where RSA with safe primes makes some beginning of a sense; see the last paragraph of this. $\endgroup$ – fgrieu May 28 '17 at 11:12
  • $\begingroup$ Suppose p is a safe prime. So, p = 2p' + 1, where p' is a prime. Now, p+1 is 2p'+2. How can we guarentee that p+1 is smooth? I am just trying to understand, why safe primes eliminate p+1 factoring attack. $\endgroup$ – satya Dec 17 '18 at 14:27
  • $\begingroup$ @satya you may want to ask this as a new question so it gets more exposure (also I don't think I know the answer to this question right now). $\endgroup$ – SEJPM Dec 17 '18 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.