The Diffie-Hellman Key Exchange Made Simple

Posted 1/10/17

To send encrypted messages to one another we need one of two things:

  1. Public/Private Keypairs

  2. 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.

The Necessary Math

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 ax mod n, it is hard to determine what x is

  • axy == ayx

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 axy == ax*y by the power rule, and ax*y == ay*x because multiplication is commutative.

The Exchange

Alice and Bob want to send secret messages back and forth, and must first generate a shared secret. The process is as follows:

  1. Alice and Bob agree on a base g, and a modulus n, where n > g

  2. Alice chooses a secret number x, and A = gx mod n

  3. Bob chooses a secret number y, and B = gy mod n

  4. Alice sends Bob A

  5. Bob sends Alice B

  6. Alice calculates s = Bx mod n

  7. Bob calculates s = Ay mod n

Both sides now have a shared secret s, which is equal to gxy mod n, and is equal to gyx mod n.

From here, s can be used as the key for a number of symmetric ciphers like AES.

Why is it secure?

No one ever sends x or y across the network. Without at least one of these values, an eavesdropper can never learn what gxy mod n is.

This means two people can generate a shared secret even in the presence of a passive attacker, and still remain secure.

When is it not 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 = gz mod n. They send C to Alice and Bob.

Alice and Charlie then generate s1 = gxz mod n, while Bob and Charlie generate s2 = gyz mod n.

Charlie can now intercept all the messages between Alice and Bob, decrypt them with s1, and re-encrypt them with s2.