Maths for the Diffie Hellman

Question

With respect to the maths behind the Diffie Hellman Key exchange algorithm.

Why does:

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

It might be fairly obvious, but what basic maths guarantees this? Why does the first modulo p expression disappear from the LHS in the expression on the RHS.

Apologies if it's not the right forum to ask it in. Maybe I should try the Stack Exchange Mathematics forum instead.

Answer 1

First, observe that for any a real, b real:

$((a \mod p) + b) \mod p = (a + b) \mod p$

Multiplication is just repeated addition. Therefore, you see for any a real,b integer:

$((a \mod p) \cdot b) mod p = (a \cdot b) \mod p$

Because:

$(\underbrace{(a \mod p) + ... + (a \mod p)}_{\text{b many times}}) \mod p = (\underbrace{a + ... + a }_{\text{b many times}}) \mod p$

With the same trick you show this for exponentiation, for all a real and b integer:

$((a \mod p) ^b) \mod p = (a ^b) \mod p$

Note that this trick only works for b being an integer, but that is given for DHE's case.

Now it should be obvious.

Answer 2

Expand and plug in.

Let $g$, $p$, $a$, $b$ be nonzero integers. (We may extend the proof to other cases easily.) By definition,

$\forall j,k \in \mathbb{Z}, k \neq 0, \exists n_0 \in \mathbb{Z} \textrm{ s.t. } (j \mod k) = j-k n_0$

Therefore there exists $n_1 \in \mathbb{Z}$ such that

$g^a \mod{p} = g^a - p n_1$.

Similarly, there exists integers $n_1$, $n_2$, $n_3$ such that

$$ (g^a \mod p) ^ b \mod p = (g^a - p n_1)^b - p n_2 \\ \phantom{aaaaaaaaaaaaaa}= g^{ab} - p n_3 \\ \phantom{aaaaaaaaaa----}= g^{ab} \mod p. $$

The second equality is arrived at by noticing only the $g^{ab}$ term has no factor of $p$. The last equality comes from noting that the result of a $\mod p$ operation results in a unique non-negative integer less than $p$.