Posted 1/10/17
To send encrypted messages to one another we need one of two things:
Public/Private Keypairs
A Shared Secret
The Diffie-Hellman Key Exchange is a technique for generating a shared secret securely, even over an insecure channel where someone may be listening in. I have found many explanations of Diffie-Hellman to be needlessly complex, and so this post will attempt to describe the algorithm simply and succinctly.
Diffie-Hellman is based on two principles. Understanding both is essential to understanding why Diffie-Hellman works, and why it is secure.
Given a, n, and a^{x} mod n, it is hard to determine what x is
a^{xy} == a^{yx}
The first is true because assuming x is reasonably large it will take a long time to discover by brute force, and the modulus prevents any kind of sneaky shortcut like trying big and small numbers to close in on the correct value.
The second is true because a^{xy} == a^{x*y} by the power rule, and a^{x*y} == a^{y*x} because multiplication is commutative.
Alice and Bob want to send secret messages back and forth, and must first generate a shared secret. The process is as follows:
Alice and Bob agree on a base g, and a modulus n, where n > g
Alice chooses a secret number x, and A = g^{x} mod n
Bob chooses a secret number y, and B = g^{y} mod n
Alice sends Bob A
Bob sends Alice B
Alice calculates s = B^{x} mod n
Bob calculates s = A^{y} mod n
Both sides now have a shared secret s, which is equal to g^{xy} mod n, and is equal to g^{yx} mod n.
From here, s can be used as the key for a number of symmetric ciphers like AES.
No one ever sends x or y across the network. Without at least one of these values, an eavesdropper can never learn what g^{xy} mod n is.
This means two people can generate a shared secret even in the presence of a passive attacker, and still remain secure.
Diffie-Hellman key exchanges are vulnerable to active attackers. This means if someone blocks the connection between Alice and Bob, they can introduce their own secret and man-in-the-middle all messages between Alice and Bob.
Charlie generates their own secret number z, and C = g^{z} mod n. They send C to Alice and Bob.
Alice and Charlie then generate s1 = g^{xz} mod n, while Bob and Charlie generate s2 = g^{yz} mod n.
Charlie can now intercept all the messages between Alice and Bob, decrypt them with s1, and re-encrypt them with s2.