The Diffie-Hellman-Merkle key exchange scheme solved the obstacles mentioned in the previous page using modular equations.
|
The Diffie-Hellman-Merkle (DHM) Key Exchange Scheme Two people for simplicity let's call them Alice and Bob can establish a key (a number) that they both will know, but a third person Eve cannot find out, even if Eve observes the communications between Bob and Alice as they set up their key. Alice and Bob can agree to use the function \(C = M^k \pmod{n}\) with specific values for M and n. It does not matter if Eve finds out the values for M and n.
|
Alice and Bob will arrive at the same key value K in the DHM Key Exchange because
\begin{align} \beta^a &= \left(M^b\right)^a & \qquad \beta = M^b \\ &= M^{ba} & \qquad Rule\, of\, exponents\quad \left(a^m\right)^n = a^{mn} \\ &= M^{ab} & \qquad Commutative\, property\quad ab = ba \\ &= \left(M^a\right)^b & \qquad Rule\, of\, exponents\quad \left(a^m\right)^n = a^{mn} \\ &= \alpha^b. &\qquad \alpha = M^a \end{align}
Establish a common key for Alice and Bob by using specific values for M, n, a, and b, and completing the steps outlined above. Let's choose the values \(M=7\) and \(n=11\).
|
Alice's Actions Step 1 Choose a value of a, say 5. (Alice keeps this value secret.) Step 2 \begin{align} \alpha &=M^a \pmod{n} \\ &= 7^5 \pmod{11} \\ &= 16,807 \pmod{11} \\ &= 10 \end{align} Step 3 Send \(\alpha = 10 \) to Bob. Step 4 Receive \(\beta = 9 \). Step 5 Compute the key: \begin{align} K &=\beta^a \pmod{n} \\ &= 9^5 \pmod{11} \\ &= 59,049 \pmod{11} \\ &= 1 \end{align} |
Bob's Actions Step 1 Choose a value of b, say 8. (Bob keeps this value secret.) Step 2 \begin{align} \beta &=M^b \pmod{n} \\ &= 7^8 \pmod{11} \\ &= 5,764,801 \pmod{11} \\ &= 9\end{align} Step 3 Send \(\beta = 9 \) to Alice. Step 4 Receive \(\alpha = 10 \). Step 5 Compute the key: \begin{align} K &=\alpha^b \pmod{n} \\ &= 10^8 \pmod{11} \\ &= 100,000,000 \pmod{11} \\ &= 1 \end{align} |
Both Alice and Bob arrived at the same key value, K = 9, which they can use for encrypting future communications to one another. Even if Eve intercepts Alice's transmission \(\alpha = 10 \) to Bob. This will not help her, because Even cannot deduce Alice's value of a that generated \(\alpha\). That value of a could an infinite amount of solutions as we saw in the solving modular equations section.
