Understanding Diffie-Hellman - Choosing a bad g

Question

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?

Answer 1

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.