NTIC An Interesting Application: Key Exchange

Section 11.4 An Interesting Application: Key Exchange

There is a quite useful application of Diffie-Hellman called key exchange. In fact, this is the original application they had in mind.

🔗

Remark 11.4.1.

There is a little controversy over exactly whom to credit for originating the concept of public-key cryptography. Researchers at the British intelligence unit GCHQ published a number of internal papers on methods similar to those in this chapter, and Ralph Merkle previously published a paper introducing the notion. However, the specific mathematics are due to Diffie and Hellman, who were the first to publish in a public venue, so it seems reasonable to keep the traditional name.

🔗

Subsection 11.4.1 Diffie-Hellman Key Exchange

🔗

Here is the basic concept of key exchange. 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.

🔗

Algorithm 11.4.2. Diffie-Hellman key exchange.

Here are the steps.

First, Alice and Bob jointly pick a big prime $p$ and a base for exponentiation $g\text{,}$ presumably with $1<g<p\text{.}$ This doesn't need to be secret.
Now, they each secretly choose an exponent; maybe Alice chooses $m$ and Bob chooses $n\text{.}$
The key step: Each of them exponentiates $g$ to their secret power, modulo $p\text{.}$
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\text{.}$

The resulting numbers are the same and give the secret key.

🔗

Proof.

The two numbers are $(g^m)^n=g^{mn}$ and $(g^n)^m = g^{nm}\text{,}$ which are the same, and certainly are so modulo $p\text{.}$

🔗

Example 11.4.3.

Alice and Bob pick $p=991$ and $g=55\text{,}$ and then (separately) pick $m=130$ and $n=123\text{.}$ Then they compute the powers $g^m$ and $g^n$ modulo $p\text{.}$

xxxxxxxxxx
 
p=991
g=mod(55,p)
m=130
n=123
Alice_does=g^m
Bob_does=g^n
print("Alice does", Alice_does)
print("Bob does", Bob_does)

Alice and Bob have different numbers now, but after doing their powers after the exchange, the numbers should be the same.

xxxxxxxxxx
 
Bob_does^m,Alice_does^n

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!

xxxxxxxxxx
 
@interact
def _(p=(991,prime_range(1000)),g=55,m=130,n=123):
    g=mod(g,p)
    pretty_print(html("If you jointly picked $p=%s$ and base $g=%s$"%(p,g)))
    pretty_print(html("Then separately picked secret powers $m=%s$ and $n=%s$"%(m,n)))
    pretty_print(html(r"Your publicly traded info would be $%s^{%s}\equiv %s$ and $%s^{%s}\equiv %s$"%(g,m,g^m,g,n,g^n)))
    pretty_print(html(r"But the secret joint key would be $%s^{%s\cdot %s}\equiv %s$"%(g,m,n,g^(m*n))))

🔗

This number

$g^{mn}$ can now be used in some symmetric encryption system as a key for both Alice and Bob.

🔗

Subsection 11.4.2 In the Middle

🔗

Having a key that isn't directly communicated should help 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.) That is good news.

🔗

On the down side, if Eve is not only listening, but actually has access to Alice and Bob's transmissions and can change them, she can still cause trouble. Eve can in this situation add her own exponent,

$\ell\text{,}$ 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 historically 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.)