2
$\begingroup$

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?

$\endgroup$
2
1
$\begingroup$

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

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

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.