2
$\begingroup$

The Diffie–Hellman key exchange protocol relies on the fact that one person, Alice, can perform $(g^a \bmod n)^b $ and another person, Bob, can perform $(g^b \bmod n)^a $ and they will both arrive at the same number: $g^{ab} \bmod n $. This allows Alice and Bob to create a private, yet symmetric, key. Why is this identity true?

$\endgroup$
2
  • 1
    $\begingroup$ Because the exponent laws descend from $\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$? That in turn is true because the quotient map reduction mod $n$ is a ring homomorphism. $\endgroup$ Dec 21, 2017 at 23:02
  • $\begingroup$ What is your definition of $(g^a \pmod n)^b$? If you can answer this precisely, you'll be almost at the answer. $\endgroup$
    – D_S
    Dec 21, 2017 at 23:08

3 Answers 3

3
$\begingroup$

I'm going to nitpick and point out that $\mod{}$ is not an operator. It is not the case that $8 \mod 5$ is the number $3$. Instead the sentence $8\equiv 3 \mod 5$ is a statement about $8$ and $3$. Namely, that it is a true statement that $8 = 3 + 5m$ for some integer $m$. Or equivalently, that $5|(8-3)$ or equivalently that $8$ and $3$ have the same remainder when divided by $5$.

Now by the division algorithm for any integer $b$ there is a unique integer $k$ between $0$ (inclusive) and $n$ (exclusive) so that $b \equiv k \mod n$. If you like we can define an operator $\%$ so that $b \% n = k$ if and only if $b \equiv k \mod n$ and $0 \le k < n$ (and $b,k,n$ are all integers.

So alice can do $(g^a \% n)^b\% n)$ and bob can do $(g^b \%n)^a \% n$ and you want to know why is it a fact that

$(g^a\%n)^b\% n = (g^b\%n)^a\%n = g^{ab} \%n$

And to prove that here are some basic facts about $\mod {}$.

1) It carries over addition. THat is if $a \equiv a' \mod n$ and $b \equiv b' \mod n$ then $a + b \equiv a' + b' \mod n$

Prove $a\equiv a' \mod n \implies a = a' + mn$ for some integer $n$ and $b\equiv b'\mod n \implies b = b' + jn$ for some integer $j$. This mean $a+b = (a'+b') + (m+j) n$ so $a+b \equiv a'+b' \mod n$.

This means, using our operation that $(a+b)\%n = (a\% n + a\%n)\%n$.

2) It carries over multiplication. That is, if $a \equiv a' \mod n$ and $b \equiv b' \mod n$ then $ab \equiv a'b' \mod n$.

Proof: if $a = a' + mn$ and $b = b' + jn$ then $ab = (a'+mn)(b'+jn) = a'b' + a'jn + b'mk + mjn^2 = a'b' + (a'j + b'm + mjn)*n$. SO $ab \equiv a'b' \mod n$.

This means $(ab)\%n = [(a\%n)(b\%)]\% n$.

3) It carries over exponents. That is if $a \equiv a' \mod n$ then $a^k \equiv a'^k \mod n$>

Pf: Well, that is just applying multiplication $k$ times.

Or if $a = a' + mn$ then $a^k = (a' + mn)^k = \sum_{i=0}^k {k \choose i}a'^i*(mn)^{k-i}= a'^k + \sum_{i=1}^k{k \choose i}a'^i*m^{k-i}n^{k-i} = a'^k + m(\sum_{i=1}^k{k \choose i}a'^i*m^{k-i}n^{k-i-1})$.

So $a^k \equiv a'^k \mod n$.

And that means $((g^a)\% n)^b\%n = (g^a)^b\% n = g^{ab}\% n$. and $((g^b)\% n)^a\%n = (g^b)^a\% n = g^{ab}\% n$.

And that is that.

$\endgroup$
2
$\begingroup$

It seems that you are thinking of 'mod' as an operation, such as might be found in a programming language. If, instead, you restate the above identity in terms of congruences, it might be clearer:

$$(g^a)^b \equiv g^{ab} \equiv (g^b)^a \pmod n$$

$\endgroup$
0
$\begingroup$

Because gb mod n=(g mod n)b mod n
Here is its proof by induction.
Base Case: g1 mod n=(g mod n)1 mod n { Because 0<=(g mod n)<n }
lets show for g2 mod n= (g . g ) mod n =((g mod n).(g mod n) )mod n=(g mod n)2 mod n { Because of Multiplicative Property}
Lets prove for gk+1 mod n=(g . gk)mod n=(g mod n . gk mod n)mod n
=((g mod n). ( g mod n )k mod n) mod n=((g mod n) mod n. ( g mod n )k mod n) mod n=
(g mod n)k+1 mod n.
Hence Proved.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .