In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack. Suppose $N = p \cdot q$, where $p$, $q$, $(p-1)/2$ and $(q-1)/2$ are primes. In this case, certainly $p-1$ and $q-1$ are not smooth. They have a very large prime factor. But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Poncho saw a mistake in the way you formulated the question with regards to the smoothness, changing "smooth" to "not smooth". However, feel free to revert or edit your question if this changes it in a significant way. Poncho, if you're reading this, please leave a comment instead of changing the question significantly, even if you consider the question itself to be incorrect. $\endgroup$– Maarten Bodewes ♦Dec 20, 2018 at 1:31
-
1$\begingroup$ @MaartenBodewes Yup. Your are right. It should be "not smooth" $\endgroup$– satyaDec 20, 2018 at 2:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack. But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors?
Actually, you're tripping over the various notions of "safe primes" vs "strong primes".
"Safe primes" are generally defined as you said, primes $p$ where $(p-1)/2$ is also prime. As you note, it guarantees that $p-1$ has a large prime factor; however it gives no guarantee of $p+1$
"Strong primes" are more variously defined; one common one is a prime $p$ where $p-1$ and $p+1$ both have a known large (for example, > 100 bit) prime factor (and sometimes there are more conditions). With this definition, both $p-1$ and $p+1$ are not smooth.
The ones arguing for more complex RSA key generation methods (the reasoning apparently being that adding complexity always adds to security) generally argue for "strong primes".
On the other hand, it's not at all clear that it adds any real security at all; if your primes $p$ and $q$ are small enough that a random prime has a nontrivial probability to be vulnerable to William's method, then with strong primes of the same size, you have a nontrivial probability of being vulnerable to ECM (and so the sizes of prime you picked as too small).
Here's how it works: William's method works this way: the attacker takes guesses at prime factors; if he guesses all the prime factors of $p+1$ or $q+1$, he can factor (and, other than time, there's no downside to incorrect guesses). (And, Pollard's method works the same with $p-1$ and $q-1$).
ECM works this way: the attacker picks a pseudocurve, which fixes "small" values $\epsilon_p$ and $\epsilon_q$; then, he takes guesses at prime factors, and if he guesses all the prime factors of $p + \epsilon_p$ or $q + \epsilon_q$, he can factor (and, again, other than time, there's no downside to incorrect guesses). [1]
Each iteration of ECM (that is, a guess at a prime factor) does take more time than the corresponding iteration of William's, but only by a small constant factor; as we rarely have that precise an estimate on the attacker's capability, we can generally ignore this constant factor.
What does this mean? We can certainly select $p$ to be a strong prime, where $p+1$ has a large prime factor (which is essentially unguessable), and so William's factoring method has no hope. However, we cannot do the same for $p + \epsilon_p$, as that covers a range around $p$, and we cannot control which pseudocurve the attacker selects.
Hence, selecting strong primes doesn't, in practice, make the factoring any more difficult.
[1]: Real ECM implementations will select a number of pseudocurves, and run them in parallel. They do this to take advantage of the possibility that one of the curves might have a $p + \epsilon_p$ which is exceptionally smooth; however the above argument holds even if the attacker doesn't do that.
-
$\begingroup$ Great explanation! Is there any known way to sample N such that, it avoids ECM attack? It seems like primes p for which a range of numbers around it being not smooth are very rare. $\endgroup$– satyaDec 20, 2018 at 14:01
-
$\begingroup$ How to sample a strong prime? A simple way I could think of: Pick a random k-bit number x. Go through x, x+1, x+2, ... and factor each value to see if they have small factors. This is not efficient. $\endgroup$– satyaDec 20, 2018 at 14:02
-
1$\begingroup$ @satya: easy; pick moderate size (perhaps 200 bit) primes $p_1, p_2$, compute $z$ with $z \equiv 1 \pmod {p_1}$, and $z \equiv -1 \pmod {p_2}$, and then search for a large prime of the form $kp_1p_2 + z$ $\endgroup$– ponchoDec 20, 2018 at 14:41
-
$\begingroup$ That's awesome. So you are directly searching numbers of the form $z = k_1 p_1 + 1 = k_2 p_2 - 1$. $\endgroup$– satyaDec 20, 2018 at 15:10
-
$\begingroup$ For enough moduli generated with random primes, the event that at least one is practically vulnerable to Pollard's p-1 factoring has sizable probability (I'm too lazy to evaluate how many moduli as a function of the modulus size). And then an adversary has a markedly better chance to factor one of these many moduli by trying Pollard's p-1 on each moduli, than by spending as much computing power trying ECM. Same (to a lesser degree) for p+1. That's a rational reason to use strong primes when generating extremely many RSA moduli and adversaries would benefit from factoring any one of these. $\endgroup$– fgrieu ♦Dec 20, 2018 at 15:51