# Factors of the group order to secure against Pohlig-Hellman

I am looking into the security of Diffie-Hellman and the discrete log in general.

To make sure an attacker can not use Pohlig-Hellman to solve the discrete log quickly we need to make sure that the order of the group, $n$, has a large prime factor.

For Diffie-Hellman in $F_p$ this would mean that we should factorize $p-1$. Since we should take $p$ to be at least $1024$ bits, how are we supposed to factor $p-1$? is this not just as hard as the RSA problem?

• – user991 Aug 9 '15 at 21:34
• Primality testing is not equivalent to factoring. – fkraiem Aug 10 '15 at 9:24

[Isn't this] just as hard as the RSA problem?

Oddly enough, no. If we were given a random $p$, and were asked to see if there's a large prime factor $q$ of $p-1$, yes, that would be, on average, a hard problem. However, that's not what we actually do.

Instead, we get to pick $p$, and so that gives us a lot of flexibility.

One way is to pick $q$ first (for example, a 256 bit prime), and then search for 1024 bit values $kq + 1$ that happen to be prime; if we call the value we find $p$, then we know that $p-1$ has a large prime factor $q$.

Alternatively, we can search for values $p$ where both $p$ and $(p-1)/2$ are both prime; this takes longer, but is still quite feasible. And, in this case, we know that $p-1$ has a large prime factor, namely $(p-1)/2$.

You can find both these strategies being applied in practice.

• It looks like "no" should be replaced with "yes". $\:$ (See the "not" in the question you quoted.) $\hspace{.92 in}$ – user991 Aug 10 '15 at 17:29
• @RickyDemer: good catch; I was focusing in on what Controlk obviously meant, and forgot to read the actual words he used. – poncho Aug 10 '15 at 18:09