3
$\begingroup$

I am taking a class on Cryptology, and I'm having a hard time understanding the potential pitfalls of Diffie-Hellman. Specifically, the professor gave the following problem:

Alice and Bob want to use Diffie-Hellman for key agreement and choose p = 982734982635928741927391824619283719654192837198273923771, however, they do not know how to calculate a relative prime, and hire Evan (Eve in disguise) to generate one for them. Evan gives them g = 584451952932889263219289637911613296416146180021897568955.

Explain what Evan did, and how this makes it easy for him to find the secret key that Alice and Bob agreed to, and find that secret key.

I understand that the value of choosing a g that has a large sub group of possible keys (i.e. you wouldn't want to choose g = 1, because then all keys would be = 1, no matter the other numbers) but I'm not understanding how that would impact this case with such a large g. Could anybody explain how I'd go about this question?

$\endgroup$
  • 4
    $\begingroup$ $p-1 = 2 \cdot 3 \cdot 5 \cdot 2130539309 \cdot 18762343373377 \cdot 819480323143485822893214401388863$ -- factored using wolfram alpha $\endgroup$ – CodesInChaos Feb 17 '16 at 17:22
3
$\begingroup$

There are two tricks that Evan could have played in selecting the $g$:

  • She could have selected a $g$ that has a small order; that is, $g^x$ could take on a small number of possible values.

  • She could have selected a $g$ that has a large but smooth order; that is, $g^x$ could take on a number of possible values, but that total number is a product of small primes.

Here's why Evan could take advantage of this second point: if the order $g$ has a prime factor $r$, then given $g^x$, it's possible to determine $x \bmod r$ in $O(\sqrt{r})$ time. Hence, if the order of $g$ consists only of small factors, then Eve can compute $x \bmod r$ for all the small prime factors, and from that, reconstruct $x$.

In either case, the question is: what's the order of the value $g$ that Evan picked? Well, one important thing that helps us determine that value; the order is always a factor of $p-1$. So, the very first step is factoring $p-1$. Then, you can go through all the prime factors of $p-1$, and use this fact: if $r$ is a factor of $p-1$, the order of $g$ is a multiple of $r$ if $g^{(p-1)/r} \ne 1$. That should let you determine the order of $g$ without a huge amount of pain.

$\endgroup$

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.