Take the 2-minute tour ×
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 \bmod p)^a \bmod p = (g^a \bmod p)^b \bmod 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 20 hours ago

2 Answers 2

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
1  
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 2 days ago
    
@fgrieu absolutely. I did not answer the question the OP asked, only addressed the problem he turned out to have. –  Camil Staps yesterday

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 2 days ago
    
I'm sorry but I don't understand your question. –  fkraiem 2 days ago
    
@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 2 days ago

Your Answer

 
discard

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.