0
$\begingroup$

In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is

$(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

$\endgroup$
  • $\begingroup$ Because the question as it stands now uses $\equiv$, a strict Vulcan can only read it as asking to prove $(g^{k_1} \bmod n)^{k_2} \bmod n\equiv (g^{k_2}\bmod n)^{k_1} \pmod n$ rather than $(g^{k_1} \bmod n)^{k_2} \bmod n\ =\ (g^{k_2}\bmod n)^{k_1} \bmod n$, which is not quite the same thing. A different question is there, where I replaced the original == by $=$ rather than by $\equiv$, in hope to simplify. $\endgroup$ – fgrieu Nov 15 '18 at 15:08
1
$\begingroup$

let $a=g^{k_1} \pmod n$ and $b=g^{k_2} \pmod n$. We want to prove that $a^{k_2} \equiv b^{k_1} \pmod n$. By congruence definition, $\exists t_1 \in \mathbb{Z}/\,a=nt_1+g^{k_1}$ and $\exists t_2 \in \mathbb{Z}/\,b=nt_2+g^{k_2}$. We want to prove that $(nt_1+g^{k_1})^{k_2} \equiv (nt_2+g^{k_2})^{k_1} \pmod n$. By binomial theorem, we have $(nt_1+g^{k_1})^{k_2} = \sum _{i=0}^{k_2} \binom{k_2}{i}\times(nt_1)^i\times(g^{k_1})^{k_2-i}$ and $(nt_2+g^{k_2})^{k_1} = \sum _{j=0}^{k_1} \binom{k_1}{j}\times(nt_2)^j\times(g^{k_2})^{k_1-j}$. The only time where $nt_1$ and $nt_2$ disapear is when $i=0$ and $j=0$, otherwise the two sums are $\equiv 0 \pmod n$. Thus, $(nt_1+g^{k_1})^{k_2} \equiv \binom{k_2}{0}\times(nt_1)^0\times(g^k_1)^{k_2-0} \equiv g^{k_1k_2} \pmod n$ and $(nt_2+g^{k_2})^{k_1} \equiv \binom{k_1}{0}\times(nt_2)^0\times(g^k_2)^{k_1-0} \equiv g^{k_2k_1} \pmod n$. Hence, $g^{k_1k_2} \equiv g^{k_2k_1} \pmod n$.

$\endgroup$
1
$\begingroup$

It's a standard fact in abstract algebra:

The statement is just $(g^{k_1})^{k_2} =(g^{k_2})^{k_1}$ in the ring $R=\mathbb{Z}/n\mathbb{Z}$, with $k_1, k_2 \in \mathbb{N}$. This statement is valid in any commutative unitary ring and can be shown by induction (on the $k_i$), e.g. Both terms equal $g^{(k_1 k_2)}$ in that same ring.

$\endgroup$
0
$\begingroup$

Simply

$(g^{k_1} \bmod n )^{k2} \bmod n \equiv (g^{k_1})^{k_2} \bmod n \equiv g^{k_1 k_2} \bmod n$

In the same way, calculate the right side, and use the commutativity of multiplication.

$\endgroup$
  • $\begingroup$ Good answer but I think what I don't understand is, why is (g^k1 mod n)^k2 mod n == (g^k1)^k2 mod n? Since g^k1 mod n != g^k1 unless g^k1 < n $\endgroup$ – dhk Nov 13 '18 at 8:47
  • $\begingroup$ So the question is perhaps better asked as: Why is (g^k1 mod n)^k2 mod n == (g^k1)^k2 mod n? $\endgroup$ – dhk Nov 13 '18 at 8:51
  • $\begingroup$ $g^{k_1} \bmod n \equiv x$ than $g^{k_1} = x+ n \cdot l$, now take $k_2$ power of both sides than take $\bmod n$ again. And use latex please $\endgroup$ – kelalaka Nov 13 '18 at 8:52
  • $\begingroup$ what is l in gk1=x+n⋅l? $\endgroup$ – dhk Nov 13 '18 at 9:05
  • $\begingroup$ $l$ is just an integer, we have the representative in modulus $x$ and all the numbers belong to $[x]$ can be represented as $x+ n \cdot l$. You should definitely read chapter 2 of the Menezes, at least. $\endgroup$ – kelalaka Nov 13 '18 at 9:07
0
$\begingroup$

I'll be answering the question:

In modular arithmetic, why is $\left(g^{k_1}\bmod n\right)^{k_2}\bmod n\,=\,\left(g^{k_1}\right)^{k_2}\bmod n$ ?

because the OP vehemently commented that it is what's not understood, and that the present question could be deleted.

Definition of $a \bmod n$

Assuming $a\in\Bbb Z$ (the signed integers) and $n\in\Bbb N^*$ (the strictly positive integers), by definition of $a\bmod n$, that is the integer $x$ such that $0\le x<n$ and $a-x$ is a multiple of $n$.

That $x$ is uniquely defined. When $a\ge 0$, that $x$ is the remainder of the Euclidean division of $a$ by $n$. When $a<0$, that $x$ is $n-1-((1-a)\bmod n)$. We write $x=(a\bmod n)$, or just $x=a\bmod n$.

This usage of $\bmod$ coincides with % in most computer languages, when $a\ge 0$ at least. However that $\bmod$ operator is conventionally evaluated after evaluation of any combination of $+$, $-$, $\cdot$ (where $\cdot$ stands for multiplication) at least on the left of $\bmod$ (sometime on its right when the context makes in unambiguous), unless otherwise specified by parenthesis. That's contrary to operator % in most programming languages, which is typically evaluated before + or -, or before any * on its right, unless otherwise specified by parenthesis.

This is not to be confused with $x\equiv a\pmod n$, which means that $a-x$ is a multiple of $n$ but does not specify an interval for $x$, thus does not uniquely define $x$. That other notation is recognizable by an opening parenthesis immediately on the left of $\bmod$, or/and by the use of $\equiv$ rather than $=$. The present question as it stands now use that other notation.

Properties

It holds that $\forall a\in\Bbb Z$, $\forall b\in\Bbb Z$, $\forall n\in\Bbb N^*$ $$\begin{align} a+b\bmod n&=(a+b)\bmod n\\ &=((a\bmod n)+b)\bmod n\\ &=(a+(b\bmod n))\bmod n\\ &=((a\bmod n)+(b\bmod n))\bmod n \end{align}$$ $$\begin{align} a-b\bmod n&=(a-b)\bmod n\\ &=((a\bmod n)-b)\bmod n\\ &=(a-(b\bmod n))\bmod n\\ &=((a\bmod n)-(b\bmod n))\bmod n \end{align}$$ $$\begin{align} a\cdot b\bmod n&=(a\cdot b)\bmod n\\ &=((a\bmod n)\cdot b)\bmod n\\ &=(a\cdot(b\bmod n))\bmod n\\ &=((a\bmod n)\cdot(b\bmod n))\bmod n \end{align}$$ Of course, the simple expression on the left is usual.

In each of the three group of equalities, the first line is notational only, and the rest can be proven rigorously using properties of divisibility; in particular that if $n$ divides two integers, then $n$ divides their sum.

We'll establish that $((a\bmod n)\cdot b)\bmod n$ equals $(a\cdot b)\bmod n$, the other demonstrations are similar:

  • $a\bmod n$ is (by definition of $\bmod$) the $x$ such that $0\le x<n$ and $a-x$ is divisible by $n$.
  • $((a\bmod n)\cdot b)\bmod n$ is $(x\cdot b)\bmod n$ for the above $x$, thus is (by definition of $\bmod$) the $y$ such that $0\le y<n$ and $(x\cdot b)-y$ is divisible by $n$.
  • $n$ divides $a-x$, thus divides the sum of $|b|$ term(s) $a-x$ (proof is by examination for $b=0$ and $|b|=1$, then by induction). Thus $n$ divides $|b|\cdot(a-x)$. Thus $n$ divides $b\cdot(a-x)$.
  • $n$ divides $b\cdot(a-x)$ and $(x\cdot b)-y$, thus divides their sum $b\cdot(a-x)+((x\cdot b)-y)$.
  • Per elementary algebra, the term $x\cdot b$ disappears and it follows that $n$ divides $(a\cdot b)-y$.
  • $y$ is such that $0\le y<n$ and $n$ divides $(a\cdot b)-y$, therefore (by definition of $\bmod$) $y$ is $(a\cdot b)\bmod n$, Q.E.D.

It also holds that $\forall a\in\Bbb Z$, $\forall n\in\Bbb N^*$, $\forall k\in\Bbb N^*$ $$\begin{align} a^k\bmod n&=\left(a^k\right)\bmod n\\ &=\left(\left(a\bmod n\right)^k\right)\bmod n\\ &=\left(a\bmod n\right)^k\bmod n \end{align}$$ The first and last lines are notational only. The second line is proven for $k=1$, using that if $n$ divides $x-y$ with $0\le x<n$ and $0\le y<n$, then $x=y$; and proof for higher $k$ uses induction and the property that we derived in detail.

The desired $\left(g^{k_1}\bmod n\right)^{k_2}\bmod n=\left(g^{k_1}\right)^{k_2}\bmod n$ is merely an application of the above property, replacing $a$ by $g^{k_1}$ and $k$ by $k_2$.

$\endgroup$

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.