Modular Numbers and Cryptography

The Diffie-Hellman-Merkle Key Exchange Scheme

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's Actions Step 1 Choose a value of a. (Keep this value secret.) Step 2 Compute $$\alpha = M^b \pmod{n}$$. Step 3 Send the value of $$\alpha$$ to Bob. Step 4 Receive the value of $$\beta$$ from Bob. Step 5 Compute the key: $$K = \beta^a \pmod{n}$$ Bob's Actions Step 1 Choose a value of b. (Keep this value secret.) Step 2 Compute $$\beta = M^b \pmod{n}$$. Step 3 Send the value of $$\beta$$ to Alice. Step 4 Receive the value of $$\alpha$$ from Alice. Step 5 Compute the key: $$K = \alpha^b \pmod{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}

Example

Establish a common key for Alice and Bob by using specific values for Mna, 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^a \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.

Practice Questions

1. Alice and Bob are establishing a common key.  Using the DHM scheme, Alice chooses a = 6 and Bob chooses b = 15.  They agree to use M = 5 and n = 23. Find the exchange key.

1. Alice and Bob are establishing a common key.  Using the DHM scheme, Alice chooses a = 8 and Bob chooses b = 11.  They agree to use M = 7 and n = 17. What does Alice send to Bob? What does Bob send to Alice?