2
$\begingroup$

I watched a video on Khan Academy explaining the Diffe-Hellman exchange. When I try to do an example problem, I get 1 all the time. Does the generator and prime modulus (or base on Wikipedia) have to somehow be related for the key exchange to work?

Here is my example:

Generator: 47
Prime modulus: 23
Alice's private number: 6
Bob's private number: 19

Alice's public number: 47^6 mod23 = 1 
Bob's public number: 47^19 mod23 = 1

Shared number: 1^6 mod23 = 1
Shared number: 1^19 mod23 = 1
$\endgroup$
  • 3
    $\begingroup$ $47 \equiv 1 \pmod{23}$ $\endgroup$ – user991 Jul 7 '15 at 2:06
  • $\begingroup$ Try a generator of 5. $\endgroup$ – J.D. Jul 7 '15 at 2:12
  • $\begingroup$ @J.D. 5 works. Why does 5 work and 47 doesn't? $\endgroup$ – Jake Jul 7 '15 at 2:19
  • $\begingroup$ @Jake : $47 \equiv 1\not\equiv 5 \pmod{23}$ $\endgroup$ – user991 Jul 7 '15 at 2:23
  • $\begingroup$ @RickyDemer sorry for how uneducated I am on this but would you mind explaining to me what that means? How do you get 5 and how are the prime modulus and the generator related? $\endgroup$ – Jake Jul 7 '15 at 2:41
3
$\begingroup$

For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, g^2 \bmod p, g^3 \bmod p, \ldots, g^{p-1} \bmod p\}$ is equal to the set of elements $\{1,2,\ldots,p-1\}$.

You happened to pick $g = 47 = 2 \times 23 + 1$, thus $g \equiv 1 \pmod{p}$. The set of powers of $1$ is just $\{1\}$, so it's about as far from a generator as it gets (the only way this could be “worse” would be a number like $46 \equiv 0 \pmod{p}$ which is not in the multiplicative group at all).

With large prime numbers, there's no efficient way to find a primitive root directly, but it's easy to test whether a candidate $g$ is a generator if the factorization of $p-1$ is known. This is because if $g$ is not a generator, its order (the smallest number $k \ge 1$ such that $g^k=1$) will be a multiple of one of the prime factors of $p-1$. The Wikipedia article on primitive roots modulo (“primitive root modulo $n$” is another way to say “generator of $(\mathbb{Z}/p\mathbb{Z})^*$”) and some results on the proportion of candidates that are generators.

In fact, the $g$ parameter in Diffie-Hellman does not have to be a generator of the whole group in order for the protocol to work, in the sense that Alice and Bob end up with the same shared key. In fact, even in your example with $g=1$, the protocol “works”, but it has no security. For security, what matters is that $g$ generates a “large” enough subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$, where “large” means that the order of $g$ (i.e. the smallest $k \ge 1$ such that $g^k \equiv 1 \pmod{p}$) is a multiple of a large prime.

There are several techniques for generating Diffie-Hellman parameters. Typically $p$ is chosen in such a way that a good generator can be chosen easily. A small generator is prefered for a minor performance improvement. There are bad values of $g$ that can lead to practical attacks but it is easy to avoid them. An additional subtlety is that if the order of $g$ has a small prime factor (which is the case if $g$ generates the whole of $(\mathbb{Z}/p\mathbb{Z})^*$, since its order $p-1$ is then a multiple of $2$), there is a practical attack to find one bit of the shared secret, so choosing $g$ such that its order is a large prime is recommended.

Usually, $p$ and $g$ are chosen long in advance; many protocols or applications use built-in constants for $p$ and $g$, or have just a few of them to span different key sizes. There's no need to vary $p$ or $g$ for security, they can be reused.

$\endgroup$
  • $\begingroup$ Actually, one can argue that $g$ should generate a large prime order subgroup, as using a generator for the entire group leaks information. $\endgroup$ – poncho Jul 8 '15 at 22:05
  • $\begingroup$ @poncho That's interesting. What information is leaked? How does it help that $g$ isn't a generator? $\endgroup$ – Gilles Jul 8 '15 at 22:41
  • $\begingroup$ If the order of $g$ has a factor $q$, then the attacker can, given $g^x$, derive $x \bmod q$ in $O(\sqrt{q})$ work. If the order of $g$ is a large prime, then observation doesn't leak anything. $\endgroup$ – poncho Jul 9 '15 at 1:11

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.