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,

$\endgroup$
1
  • 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
    Commented Nov 10, 2015 at 18:59

1 Answer 1

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

$\endgroup$
3
  • $\begingroup$ I think you'd also need "and only if" for the latter of those two facts. $\;$ $\endgroup$
    – user991
    Commented Nov 10, 2015 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
    Commented Nov 10, 2015 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
    Commented Nov 10, 2015 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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