-1

I have been trying to understand why the Diffie Dellman key exchange algorithm works, specifically why the two exponents can be swapped in it without the result changing.

So my specific question is why:

$$\begin{align} &(g^b \bmod m)^a \bmod m\\ =\ &(g^a \bmod m)^b \bmod m\end{align}\qquad$$

I am interested in the reasoning/proof/explanation behind why it is true.

I am completely aware that it can be proved from common rules of modular arithmetic, but I am asking for a detailed proof/explanation for why it holds true as at least for me the proof isn't immediately obvious.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • Welcome to MSE. For some basic information about writing mathematics at this site see, *e.g.*, [basic help on mathjax notation](/help/notation), [mathjax tutorial and quick reference](//math.meta.stackexchange.com/q/5020), [main meta site math tutorial](//meta.stackexchange.com/a/70559) and [equation editing how-to](//math.meta.stackexchange.com/q/1773). – José Carlos Santos Dec 07 '19 at 11:57
  • 1
    basic exponent rules that's why. –  Dec 07 '19 at 12:10
  • See edited question, to clarify. @roddy macphee – Distributed Bit Dec 07 '19 at 12:15
  • it's literally that most common arithmetic rules don't break in mod, they just get reduced ahead of time $$(g^a)^b=g^{ab}=g^{ba}=(g^b)^a $$ is one such combination of rules. –  Dec 07 '19 at 12:18
  • Yes I am completely aware that it is a common rule, but I am asking for a proof/explanation for why it holds true in modular arithmetic as at least for me the proof isn't immediately obvious. Thank you – Distributed Bit Dec 07 '19 at 12:19
  • because mod is defined as $$y\equiv b\mod m\iff y=mx+b$$ for integer values for all variables. –  Dec 07 '19 at 12:25

3 Answers3

2

Generally, to prove an equality about mod as an operation it is usually easiest to convert it into an equivalent but more flexible congruence relation form, via the following equivalence (cf. here)

$$ (g\bmod m) = (h\bmod m)\color{#c00}\iff g\equiv h\!\!\!\pmod {\!m}\qquad $$

$\begin{align} {\rm so}\ \ \ (g^b\bmod m)^a\bmod m &= (g^a \bmod m)^b\bmod m\\[.2em] \color{#c00}\iff (g^b\bmod m)^a &\equiv (g^a \bmod m)^b \!\!\!\pmod{\!m}\\[.2em] \iff (g^b)^a &\equiv (g^a)^b\!\!\! \pmod{\!m}\ \ {\rm by}\ \ \color{#0a0}{\rm CPR}\ \ \color{#c00}{\&}\ \ g^{n}\bmod m\equiv g^n\!\!\!\!\pmod{\!m} \end{align}$

that's true by $\,(g^b)^a = g^{ab} = (g^a)^b\,$ by integer power laws. Here $\color{#0a0}{\rm CPR} = $ Congruence Power Rule

Key Idea $ $ Generally, as above, using the above equivalence and congruence laws, we can erase all $\!\bmod m$ operations in a polynomial expression (i.e. where mod appears in arguments of sums & products, but not in exponents) to obtain an equivalent congruence, e.g. for the above

$$\begin{align}(\color{#c00}{g^b\color{#bbb}{\bmod m})^a\color{#bbb}{\bmod m}} \,&=\, \color{#0a0}{(g^a \color{#bbb}{\bmod m})^b\color{#bbb}{\bmod m}}\\[.2em] \iff \color{#c00}{(g^b)^a} &\equiv\, \color{#0a0}{(g^a)^b}\!\!\pmod{\!m} \end{align}\qquad$$

Since congruence arithmetic inherits all common (ring) arithmetic laws (commutative, associative, distributive), it is much easier to use our well-honed arithmetical (vs. divisibility) intuition to prove congruence equations than it is to prove the equivalent divisibility statements.

See also this answer.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
1

Short answer: all the usual rules of arithmetic are true for calculations modulo $m$.

That means addition and multiplication are commutative and associative and multiplication distributes over addition. The laws of exponents follow.

You have to be a little more careful trying to think about division.

The proofs are standard material in any elementary number theory text.

Ethan Bolker
  • 86,995
  • 6
  • 100
  • 180
  • Hmm yeah I am self teaching myself this topic and haven't yet seen a proof for why this is true. Could you link to one (a proof) that you know of? As that is what I am interested in, despite knowing that it works. – Distributed Bit Dec 07 '19 at 12:17
  • 2
    https://en.wikipedia.org/wiki/Modular_arithmetic or https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic or https://artofproblemsolving.com/wiki/index.php/Modular_arithmetic/Introduction or https://brilliant.org/wiki/modular-arithmetic/ or http://mathworld.wolfram.com/ModularArithmetic.html etc. –  Dec 07 '19 at 13:09
  • @DistributedBit I just posted a formal proof. If anything is not clear please feel welcome to ask questions. – Bill Dubuque Dec 07 '19 at 18:40
0

To answer my own question: The reason why

(g^b mod m)^a mod m

= (g^a mod m)^b mod m

Is because:

(g^b mod m)^a mod m can be simplified to: (g^b)^a mod = g^(ba)

This is because the mod n in the brackets doesn't change the equivalence class of what is being exponentiated to a and multiplying two numbers of the same equivalence class by themselves a certain number of times will result in the same product.

As a result of this, the equation can be represented as g^(ba) mod m = g^(ab) mod m which is obviously true because the product ab is the same either way so the exponent is the same.