# How to protect from Silver–Pohlig–Hellman algorithm

I read that Silver–Pohlig–Hellman algorithm solves the discrete logarithm with prime module $p$ in $O(\log^2(p))$ if $p-1$ is a smooth number. This seems pretty fatal for cryptography, since it is a polynomial over the key length, right?

So my questions are:

1. How probable is this to happen?
2. (How) can it be prevented?
-
"if $p−1$ is a smooth number", but if you choose a $p-1$ with large factors (e.g. twice a prime) then it's not smooth and the algo doesn't break it. –  CodesInChaos Sep 16 '13 at 13:14

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently.

However, the solution is pretty simple: Choose a safe prime as modulus: $p=2q+1$ (with $q$ prime), or a prime $p$ where $p-1$ contains at least one large factor, so that the BS-GS algorithm for this factor is too large (It has $\mathcal{O}(\sqrt{q})$ memory and time complexity for prime $q$).

For example this is done in DSA: Choose prime $q$ first, then calculate a prime $p$, where $p-1$ is a multiple of $q$. Examples for suggested key lengths $(|q|,|p|)$: (160,1024), (224,2048), (256,2048),...

edit:

To answer your first question: If you choose $p$ randomly, chances are high that your security is MUCH lower than you would expect:

For random $p$ , the chance of $p-1$ being divisible by a low prime $a$ is $\frac{1}{a-1}$. A random $p$ means that $(p-1)$ mod $a$ is uniform distributed in $[0,a-2]$.

Now, if $a$ is small, we can ignore the costs of the BS-GS algorithm for $a$, and you "loose" $\log_2{a}$ bits of security: The remaining problem doesn't have to be solved for group order $(p-1)$ but for $(p-1)/a$.

Since there are quite a lot of small prime numbers, you have a problem. Best to avoid this problem by choosing $p$ not totally random, but with $q$ large enough. (Choose q, calculate some $p$ and test them for primality).

-
Gaining $\log_2 a$ bits for all small prime factors $a$ is not a problem, as long as a big enough prime factor remains. For a 1024-bit random prime $p$, largest prime factor of $p-1$ will have, on average, about 300 bits, and it is extremely improbable that it would be smaller than 160 bits. So a random prime is safe. You still want to generate the modulus as $p = qr + 1$ for a given smaller prime $q$ because for some algorithms (in particular DSA) it is convenient to have a known relatively small subgroup order. But that's not a security measure. –  Thomas Pornin Sep 16 '13 at 22:41
While gaining knowledge of the small prime factors of the group order might not be a problem in average, this is a gamble with unknown odds. The estimation of an average max-prime factor size of 300 seems good enough, but it does not estimate the risk of getting a smooth number without addressing this estimation's variance (or even the actual distribution). So unless you use an efficient factoring algorithm on $p-1$ yourself, you don't know how good your choice of $p$ is. But yeah, knowing a smaller subgroup can be very beneficial as well, esp. for DSA –  tylo Sep 17 '13 at 12:18
Actually the probably of smoothness for a random integer (like $p-1$, for a random prime $p$) is well known through the Dickman-de Bruijn function. Also, if smooth numbers were not exceedingly rare, the elliptic curve factoring method would break RSA, since that method relies on hitting a smooth number (ok, that's a bit handwaving, but there's only so much math that can be crammed in a 500-character comment). –  Thomas Pornin Sep 17 '13 at 12:31