Discussion: The Diffie-Hellman Key-Exchange Algorithm
The Diffie-Hellman algorithm is a key-exchange algorithm for safe communications in networks. The algorithm is as follows:
- the sender sets a prime number $p$, a base number $g$ and a random number $a$
- the sender calculates $A=g^a\%p$
- the sender sends $p$, $g$ and $A$ to the receiver
- the receiver sets a random number $b$
- the receiver calculates $B=g^b\%p$ and $s1=A^b\%p$
- the receiver sends $B$ to the sender
- the sender calculates $s2=B^a\%p$
- $s1 \equiv s2 = s$, and the shared key is set $s$
In the algorithm, $A$ and $B$ are named public keys; $a$ and $b$ are named private keys. In communications, private keys are hidden and unknown to other users; public keys are transmitted through the network. However, with only public keys, $p$ and $g$, $s$ cannot be determined. The sender and the receiver can cooperate to determine a shared key without knowledge of each other’s private key.
Proof of the algorithm:
let $x$ and $y$ be two positive integers that satisfy:
\[g^a = px + A \\ g^b = py + B\]then,
\[A^b = (g^a-px)^b \\ A^b\%p = (g^{ab}-C_b^1\times g^{a(b-1)}px+C_b^2\times g^{a(b-2)}(px)^2+\cdots)\%p = g^{ab}\%p\]Similarly,
\[B^a\%p = g^{ab}\%p\]Therefore, $s1 \equiv s2$.