1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – virmis_007 Jan 20 '18 at 10:08
  • $\begingroup$ @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. $\endgroup$ – Discrete lizard Jan 20 '18 at 10:14
  • $\begingroup$ 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 $ ? $\endgroup$ – virmis_007 Jan 20 '18 at 10:24
  • $\begingroup$ @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$. $\endgroup$ – Discrete lizard Jan 20 '18 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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