Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
2  
"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
add comment

1 Answer

up vote 3 down vote accepted

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).

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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