Section11.4An Interesting Application: Key Exchange¶ permalink
There is a quite useful application of D-H called key exchange. Here is the basic concept.
Two people trying to pass information (universally called Alice and Bob) want to decide on a secret key for using some encryption routine. Since all we really care about are the numbers, once we've encoded, we should just assume the key is a number.
Unfortunately, Alice and Bob know that someone may be listening in on their decision. Instead of trying to send a secret key only one of them has chosen, they try to create a secret key together using (essentially) public means. Here's how it works.
Algorithm11.4.1Diffie-Hellman key exchange
Here are the steps.
First, Alice and Bob jointly pick a big prime \(p\) and a base for exponentiation \(g\), presumably with \(1<g<p\). This doesn't need to be secret.
Now, they each secretly choose an exponent; maybe Alice chooses \(m\) and Bob chooses \(n\).
The key step: Each of them exponentiates \(g\) to their secret power, modulo \(p\).
Then they pass off these numbers to each other, and once again exponentiate the other person's number to their own secret power, modulo \(p\).
The resulting numbers are the same and give the secret key.
The two numbers are \((g^m)^n=g^{mn}\) and \((g^n)^m = g^{nm}\), which are the same, and certainly are so modulo \(p\).
Example11.4.2
Alice and Bob pick \(p=991\) and \(g=55\), and then (separately) pick \(m=130\) and \(n=123\). Then they compute the powers \(g^m\) and \(g^n\) modulo \(p\).
Alice and Bob have different numbers now, but after doing their powers after the exchange, the numbers should be the same.
Note the code takes one power to the m and the other power to the n.
Thus, now they have a secret key (\(g^{mn}=g^{nm}\)) they can easily compute but which a spy in the middle cannot. Feel free to try this with your own numbers you pick!
This gives an encryption key useful to both Alice and Bob, to protect from any potential Eve who might be listening in. (That's Eve for eavesdropping, believe it or not – also a universal person in these stories.)
On the down side, if Eve not only is listening, but actually has access to Alice and Bob's transmissions and can change them, she can actually add her own exponent \(\ell\) to the game, so that she pretends to have secret key \(g^{m\ell}\) with Alice and secret key \(g^{n\ell}\) with Bob. Both of their keys' security is now compromised. Such a situation is known as a “Man in the Middle” attack. There is no obvious way to stop such an attack with this algorithm, if Eve has that much power. (See Exercise 11.8.5.)
