"Diffie-Hellman Key Exchange" in plain English

Diffie-Hellman is a way of generating a shared secret between two people in such a way that the secret can't be seen by observing the communication. That's an important distinction: You're not sharing information during the key exchange, you're creating a key together.

This is particularly useful because you can use this technique to create an encryption key with someone, and then start encrypting your traffic with that key. And even if the traffic is recorded and later analyzed, there's absolutely no way to figure out what the key was, even though the exchanges that created it may have been visible. This is where perfect forward secrecy comes from. Nobody analyzing the traffic at a later date can break in because the key was never saved, never transmitted, and never made visible anywhere.

The way it works is reasonably simple. A lot of the math is the same as you see in public key crypto in that a trapdoor function is used. And while the discrete logarithm problem is traditionally used (the x^y mod p business), the general process can be modified to use elliptic curve cryptography as well.

But even though it uses the same underlying principles as public key cryptography, this is not asymmetric cryptography because nothing is ever encrypted or decrypted during the exchange. It is, however, an essential building-block, and was in fact the base upon which asymmetric crypto was later built.

The basic idea works like this:

1. I come up with a prime number p and a number g which is coprime to p-1 and tell you what they are.
2. You then pick a secret number (a), but you don't tell anyone. Instead you compute g^a mod p and send that result back to me. (We'll call that A since it came from a).
3. I do the same thing, but we'll call my secret number b and the computed number B. So I compute g^b mod p and send you the result (called "B")
4. Now, you take the number I sent you and do the exact same operation with it. So that's B^a mod p.
5. I do the same operation with the result you sent me, so: A^b mod p.

The "magic" here is that the answer I get at step 5 is the same number you got at step 4. Now it's not really magic, it's just math, and it comes down to a fancy property of modulo exponents. Specifically:

(g^a mod p)^b mod p = g^ab mod p
(g^b mod p)^a mod p = g^ba mod p

Which, if you examine closer, means that you'll get the same answer no matter which order you do the exponentiation in. So I do it in one order, and you do it in the other. I never know what secret number you used to get to the result and you never know what number I used, but we still arrive at the same result.

That result, that number we both stumbled upon in step 4 and 5, is our shared secret key. We can use that as our password for AES or Blowfish, or any other algorithm that uses shared secrets. And we can be certain that nobody else, nobody but us, knows the key that we created together.

The other answers do an excellent job explaining the maths behind the key exchange. If you'd like a more pictorial representation, nothing beats the excellent paint analogy shown on the Diffie–Hellman key exchange Wikipedia entry:

_{Image is in the public domain}

Diffie-Hellman is an algorithm used to establish a shared secret between two parties. It is primarily used as a method of exchanging cryptography keys for use in symmetric encryption algorithms like AES.

The algorithm in itself is very simple. Let's assume that Alice wants to establish a shared secret with Bob.

1. Alice and Bob agree on a prime number, p, and a base, g, in advance. For our example, let's assume that p=23 and g=5.
2. Alice chooses a secret integer a whose value is 6 and computes A = g^a mod p. In this example, A has the value of 8.
3. Bob chooses a secret integer b whose value is 15 and computes B = g^b mod p. In this example, B has the value of 19.
4. Alice sends A to Bob and Bob sends B to Alice.
5. To obtain the shared secret, Alice computes s = B^a mod p. In this example, Alice obtains the value of s=2
6. To obtain the shared secret, Bob computes s = A^b mod p. In this example, Bob obtains the value of s=2.

The algorithm is secure because the values of a and b, which are required to derive s are not transmitted across the wire at all.