Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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 at 15:49

3 Answers 3

up vote 2 down vote accepted

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).

share|improve this answer
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 at 10:59
@fgrieu absolutely. I did not answer the question the OP asked, only addressed the problem he turned out to have. – Camil Staps Mar 1 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.

share|improve this answer
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 at 13:00
I'm sorry but I don't understand your question. – fkraiem Feb 28 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. – Robert NACIRI Feb 28 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.