0
$\begingroup$

Studying the basics of Diffie-Hellman key exchange, I'm stuck at a basic operation used in the end of the key exchange (where you show that both computations actually are the same). Can someone explain this step in detail?

(g^a mod p)^b mod p = (g^a)^b mod p

Where p is a prime and g is the primitive root to p

Thanks,

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Actually, that holds for arbitrary $g, p$. That is, that's true even if $p$ isn't a prime, and/or $g$ is not a primitive root. $\endgroup$ – poncho Nov 10 '15 at 18:59
1
$\begingroup$

This can be derived from two simple facts about the $mod$ operation:

$a \bmod b = a + bi$ for some integer $i$ (for any $a, b$)

$a \bmod c = b \bmod c$ if $a - b = ci$ for some integer $i$

With these two facts, we can look at $(g^a \bmod p)^b$; that can be simplified to $(g^a + pi)^b$ (for some integer $i$), and by the binomial expansion, this is $g^{ab} + p(\textit{Other terms})$ (for some integer value of Other terms).

When we look at the difference between that and $(g^a)^b$, we get the value $g^{ab} + p(\textit{Other terms}) - (g^a)^b = p(\textit{Other terms})$, which is $p$ times some integer.

Hence, by our second fact, we immediate get $(g^a \bmod p)^b \bmod p = (g^a)^b \bmod p$, which is what we set out to prove

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think you'd also need "and only if" for the latter of those two facts. $\;$ $\endgroup$ – user991 Nov 10 '15 at 19:24
  • $\begingroup$ @RickyDemer: actually, we don't need it; the proof would be valid even if there were cases that $a \bmod c = b \bmod c$ even if there was no such $i$. Of course, that doesn't happen; however we don't need to assume it :-) $\endgroup$ – poncho Nov 10 '15 at 19:27
  • $\begingroup$ (In fact, as I now notice, the "and only if" part follows from the former of those two facts.) $\;$ $\endgroup$ – user991 Nov 10 '15 at 19:29

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.