Diffie-Hellman Explained

Diffie-Hellman / Forward secrecy

Diffie-Hellman is quite an incredible algorithm, it appears to violate common sense and achieve the impossible. It allows a shared secret to be exchanged between parties without having to ever transmit the entire secret

Suppose we have an insecure channel and two parties who have never met (no offline exchange of keys). We want to secure our conversation with a shared secret but we obviously sharing the secret over the insecure line would defeat the purpose.

How do we solve this
Cryptographic explanation of Diffie-Hellman (Wikipedia)
Diffie-Hellman in Plain English (Stack Exchange)

We have our server Alice and our client Bob. Because Alice is a server, she has already come prepared with the parameters p=23 and g=5 where p is a prime, and g is a primitive root modulo p

These parameters define a function that both parties will use to generate a value. So in our case, both sides will have f(a) = na mod 23

Alice and Bob each compute an output of this function and share it with eachother, importantly, they keep secret what input they used.

Alice tells Bob that f(a)=8
Bob tells Alice that f(a)=19

Knowing that the secret value she used was 6,Alice defines the function f(n) = n6 mod 23
Bob does the same thing using his secret key.

When she hears that Bob got a value of 19, she computes 196 mod 23 = 2.
Bob does the same thing and also gets an answer of 2.

Both sides end up with a congruent key that can be used to secure the channel without ever actually transmitting it.

Can you work out what value Bob used? In this example, it's not very hard as the numbers are small. The difficulty of this with large numbers is the basis for the security of DH