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
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,
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
