Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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.
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.
