Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

Question

In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven't mentioned the other requirements taken into consideration for selection of these parameters.

So here is how this works:

1. Alice calculates $A = (g^a)\mod n $.
2. Bob calculates $B = (g^b)\mod n$.
3. Alice sends $A$ to Bob who then computes $(A^b)\mod n$ to get the final key. Vice-versa happens when Bob sends $B$ to Alice.
4. The end resulting keys of both Bob and Alice have to be equal.

Now, my doubt is that how come $(((g^a)\mod n)^b)\mod n = (((g^b)\mod n)^a)\mod n $ holds true?

Answer 1

In general, we have that $a\cdot b \mod n = (a\mod n) \cdot (b\mod n) \mod n$ for any positive integers $a,b,n$. To see this, we write $a= k n +r_a$ and $b=ln+r_b$, where $r_a= a \mod n$ and $r_b = b\mod n$. So, we get \begin{align} a\cdot b \mod n &= (kn +r_a) (ln+r_b) \mod n \\ &= kln^2 +knr_b + ln r_a + r_ar_b \mod n\\ &= n (kln +kr_b + lr_a) + r_ar_b \mod n\\ &= r_ar_b \mod n\\ &= (a\mod n) \cdot (b\mod n) \mod n \end{align}

From this, it follows that $a^b \mod n = (a\mod n)^b \mod n$ for any positive $a,b,n$. Using this equality, we can 'move' exponents through modular reductions, from which your equality follows.