Diffie Hellman

The diffie hellman key exchange is a neat communication protocol that allows two parties to arrive at a shared secret number over a public channel (i.e. all messages that are exchanged are observable).

At the end of the protocol, two players, Alice and Bob, can be confident that the number each of them arrived at is (a) the same as the other and (b) only known to both of them.

It relies on two interesting mathematical observations:

1. (g ^ a) ^ b = (g ^ b) ^ a
2. given g [1] and g ^ a [2], it is really hard to compute a [3].

[1] special kinds of g, [2] a is a natural number and [3] this is known as the discrete logarithm problem

The protocol works in the following order:

1. Alice and Bob agree on a large prime p = (typically fixed) and
2. Alice and Bob agree on a primitive root g = (typically fixed).
3. Alice picks a number a = (between 1 and p - 1) and sends Bob A = g ^ a % p = 5 ^ 4 % 23 = 4.
4. Bob picks a secret number b = (between 1 and p - 1) and sends Alice B= g ^ b % p = 5 ^ 3 % 23 = 10.
5. Alice takes B = 10 and computes B ^ a % p = 10 ^ 4 % 23 = 18.
6. Bob takes A = 4 and computes A ^ b % p = 4 ^ 3 % 23 = 18.
7. Alice and Bob have arrived at the same number 18 = 18.

They both arrive at the same number because they make computations that use the observation made before that (g ^ a) ^ b = (g ^ b) ^ a.

Specifically:

18 =

B ^ a % p = (g ^ b) ^ a % p = (g ^ (b * a)) % p = (g ^ a) ^ b % p = A ^ b % p

= 18

Observers of the open channel cannot compute the shared secret number because:

1. they only observe p, g, g ^ a % p (A) and g ^ b % p (B) and
2. given g ^ a and g ^ b they cannot figure out a and b to compute g ^ a ^ b % p (note that (g ^ a) * (g ^ b) = g ^ (a + b) rather than g ^ a ^ b).

So there, next time you want to agree on a secret number, run diffie hellman!