I've been learning about Diffie-Hellman key exchange.

One of the main tricks comes down to a commutativity property of exponentiation in the relevant modular arithmetic, it seems.

Something like:

(EDIT: As noted by @Ted, I got the formula wrong, hence my confusion.)

$$r^{A^B} \equiv r^{AB} \equiv \; ... \; \equiv r^{B^A} \pmod p$$

I know that this is not true in general, so presumably derives from the particular choices of r, A, B, and p.

I've done a fair amount of searching around, but cannot find a proof, or even a reasonable explanation of where this property arises from.

Can anyone here help?

  • $\begingroup$ It is true for all integers r,A,B and p $\endgroup$ – Mayank Deora Dec 18 '15 at 2:45
  • $\begingroup$ @MayankDeora: How about r=2, A=2, B=3, p=1000? I get $2^{2^3} \equiv 2^8 \equiv 256 \pmod {1000} \ne 2^{3^2} \equiv 2^9 \equiv 512 \pmod {1000} \ne 2^{3*2} \equiv 2^6 \equiv 64 \pmod {1000}$ $\endgroup$ – jwd Dec 18 '15 at 3:40
  • $\begingroup$ @jwd You have the order of operations wrong. The relevant identity for Diffie-Helman is $(r^A)^B = (r^B)^A$, not $r^{(A^B)} = r^{(B^A)}$. $\endgroup$ – Ted Dec 18 '15 at 3:43
  • $\begingroup$ @Ted: Ohhhhh (: Thank you. $\endgroup$ – jwd Dec 18 '15 at 3:46
  • $\begingroup$ @jwd i have proved the identity as told by Ted $\endgroup$ – Mayank Deora Dec 18 '15 at 5:00

We have to prove that$$({r^A}modp)^B mod(p)=(r^Bmodp)^A mod(p)=(r)^{BA} modp$$ We would use binomial expansion for it.
Let $r=xp+y $ then $(r)modp=y$
As we know that:-$$ r^A=(xp+y)^A=nC_0(y)^A+nC_1(xp)(y)^{A-1}+........+nC_n(xp)^A$$ If we calculate mod p of the above term we would get $(y^A)modp+0$

so,$(r^A)modp=(y^A)modp$ now let $y^A=\alpha p+\beta$ then $(y^A)modp=\beta$ ,now we have:-
$$((r^A)modp)^Bmodp=((y^A)modp)^Bmodp=(\beta)^Bmodp$$ Now we would calculate$(r^{AB}modp)$ $$r^{AB}modp=(xp+y)^{AB}modp=y^{AB}modp=(y^A)^Bmodp=(\alpha p+\beta)^Bmodp=(\beta)^Bmodp$$ i.e.$$((r^A)modp)^Bmodp=(r^{AB})modp=((r^B)modp)^Amodp$$ -Hence proved

  • $\begingroup$ This is fine and all, but wouldn't it be simpler to note that (${r^A})^B = {r^A}\cdot{r^A}\cdot{r^A}\ldots = r^{A+A+A\ldots} = r^{A\cdot B}$ ? $\endgroup$ – jwd Dec 18 '15 at 17:13
  • $\begingroup$ I think that you should edit your question. $\endgroup$ – Mayank Deora Dec 19 '15 at 2:42
  • $\begingroup$ Good point; edited. $\endgroup$ – jwd Dec 21 '15 at 19:34

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.