# How does $g$ being a generator imply Diffie-Hellman's correctness?

In the Diffie-Hellman protocol for key exchange over an unsecured channel, we choose $p$ and $g$, where $g$ is a generator of $\mathbf{Z}_p^*$. However I want to know why this assumption makes the equation below true, assuming Alice and Bob choose $a$ and $b$ as secret keys:

$$(g^b)^a \equiv (g^a)^b \pmod p.$$

In other words, how does the assumption that $g$ is generator of $\mathbf{Z}_p^*$ make the above equation true?

• You can remove 3 of your 4 'mod $p$' expressions. One at the end of the line is enough. And it is not necessary that $g$ is a generator for correctness. It is necessary to have all of $\mathbb{Z}_p^*$ as range of the algorithm.
– tylo
Mar 2, 2015 at 15:49

Fkraiem's answer is correct: this is not necessary. From your comment on his answer it seems however you don't understand why Alice and Bob retrieve the same key. This, again, doesn't rely on $g$ being a generator.

Recall from your high school math classes that $(g^a)^b = g^{ab} = g^{ba} = (g^b)^a$. This is basically the trick that is being used here. Since Alice knows $a$ and $g^b$ she can compute the rightmost term in that equation, and since Bob knows $b$ and $g^a$ he can compute the leftmost term. They then have the same number that they can use as a secret key. Since only $g^a$ and $g^b$ but not $a$ or $b$ are communicated over an untrusted line, no eavesdropper can compute that same number.

The only difference here is that we work modulo $p$. We thus also need to show that $(g^a \bmod{p})^b\bmod{p} = (g^a)^b\bmod{p}$. We first look at multiplication with a modulus.

Fix $a,b,m\in\mathbb{Z}$ and look at $ab\bmod m$. We can write $a=km+r$ for some $k,r\in\mathbb{Z}$ and similarly $b=lm+s$ for some $l,s\in\mathbb{Z}$. Then we have $$ab\bmod m = (km+r)(lm+s)\bmod m = klm^2+rlm+kms+rs\bmod m = rs.$$

We know since $a=km+r$ that $a\bmod m=r$ and similarly $b\bmod m=s$. Hence, $rs=(a\bmod m)(b\bmod m)$ and thus also $ab\bmod m=(a\bmod m)(b\bmod m)$.

Now look at $(g^a)^b \bmod p$. We can write this as

$$(g^a)^b \bmod p = (g\cdot g \cdot \dots \cdot g)^b = (g\cdot g \cdot \dots \cdot g) \cdot \dots \cdot (g\cdot g \cdot \dots \cdot g) \bmod p.$$

Now we can apply the rule for multiplication with a modulus we just found, and we get

$$\ldots = (g\cdot g \cdot \dots \cdot g \bmod p) \cdot \dots \cdot (g\cdot g \cdot \dots \cdot g \bmod p) \bmod p = (g^a\bmod p)^b \bmod p.$$

As you see, we didn't use the that $g$ is a generator of $\mathbb{Z}_p^*$, so this is a basic rule you can apply to any formula using exponentiation and a modulus. You can read more about it: Modular Exponenetiation (wiki).

• Right: the choice of $g$ is immaterial to Alice and Bob obtaining the same shared key. However the choice of $g$ matters to the diversity of that key, thus its security. For example, $g=1$ would imply that the shared key is always $1$, and that's not at all secure. $g$ being a generator ensures that the shared key can take any value in $[1\dots p]$, as (somewhat tersely) explained in that other answer.
– fgrieu
Mar 1, 2015 at 10:59
• @fgrieu absolutely. I did not answer the question the OP asked, only addressed the problem he turned out to have.
– user4686
Mar 1, 2015 at 19:49

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.

• May be i Should be more specific, (whitout considering Diffie–Hellman),why Allice and Bob retried the same key and about equation is held if g is generator of Zp*.
– VSB
Feb 28, 2015 at 13:00
• I'm sorry but I don't understand your question. Feb 28, 2015 at 13:10
• @VSB it can be deduced from the "Exponential" mathematical function. When you reduce modulo p, Computation are in the finite field $\mathbb{F}_p \equiv (\mathbb{Z}/n\mathbb{Z})^{*}$. To a straitforward calculation experiment with $g^x mod\; p=X\;+k_x \times p$ recursively with x=a,b. Then the shared key for ALice and Bob is $g^{ab}$ and an attacker can't deduce it by observing the exchange of $g^a$ and $g^b$ throught the public channel. Feb 28, 2015 at 15:07

The fact that $g$ is a generator (or not) of the group of inverse elements $G={\bf F}_p^{*}$, indeed does not affect the relation you wrote. But, if you want to apply Diffie-Hellman in a secure way, the order of $g$ has to be large. Say you choose a large prime $p$ (at least $1024$ bits). If $g$ is not a generator of $G$ then the order of $g$ shall divide $|G|=p-1$ and in this case you may allow some attacks. For instance if $|\langle g\rangle|$ is small you may apply baby steps giant steps in time $O(\sqrt{|\langle g\rangle|})$ in order to find the discrete log.