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

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?

## 1 Answer

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.

• I still don't understand, because then the left side of the inequality reduces to $((((g\mod n)^a)\mod n)^b)\mod n$. For further simplification I substituted $G = (g\mod n)$ but it turns out that simplification process is turning out to be a loop since now you can see that the only change observable from the original equation is that $g$ has become $G$ ; therefore it's not actually simplifying anything. Symmetric things will happen on the right side too. – virmis_007 Jan 20 '18 at 10:08
• @virmis_007 You need to apply the equality on the other side of the equation: From the final rule given, we get $(g^a \mod n)^b \mod n = g^{ab}\mod n$ and $(g^b \mod n)^a \mod n = g^{ba} \mod n$, so the two expressions are equal. – Discrete lizard Jan 20 '18 at 10:14
• Sorry but I am still unable to understand that on simplifying $(g^a \mod n)^b \mod n$, we get $((g\mod n)^a \mod n )^b\mod n$ by your indicated rule; How could you write this as $(g\mod n)^{ab} \mod n$ ? – virmis_007 Jan 20 '18 at 10:24
• @virmis_007 As I said, apply the formula to the other side: see that the RHS of the rule is equal to $(g^a \mod n )^b \mod n$ where $a \rightarrow g^a$ and $b\rightarrow b$. This yields $(g^a)^b \mod n$. – Discrete lizard Jan 20 '18 at 10:35