Diffie-Hellman Key Exchange
If you've been reading the previous posts on network security, then you've seen several instances where two parties need a shared secret. We've just been assuming that a shared secret is magically known. How can two parties share a secret without having previously arranged confidential information between them? This is the boot-strapping problem of encryption, because it seems like exchanging a secret requires that you've exchanged secrets before. However, it turns out that two parties can build a shared secret even if all of the communication between them can be intercepted.
Diffie-Hellman (DH) is an algorithm that lets two parties collectively create an encryption key. You can't directly use DH to send data from one party to another. DH lets you create an encryption key, and then you can use that key to send the data. In DH, there are two public numbers for the conversation, a shared public key for each side, and a hidden private key for each side.
To start a key exchange, the two sides first share a large prime number p and a base value g that is between 1 and p - 1. These numbers can be agreed on in public, so there's no need to protect the conversation from eavesdroppers. This allows the exchange to start without having a prearranged secret. Each side then picks a secret value that doesn't get shared. Call the two sides and their corresponding numbers A and B. A sends gA mod p over to side B. B sends gB mod p over to side A. The values sent over the wire are still totally public. This relies on the fact that even when g, p, and the result are publicly known, it's still very difficult to compute A or B.
A knows the value A and gB mod p, making it simple for A to calculate gAB mod p. B knows the value B and gA mod p, making it simple for B to calculate gAB mod p. Anyone else would be unable to compute this value, making it possible to use this shared result as an encryption key. How difficult is it to compute gAB mod p given g, p, gA mod p, and gB mod p? That actually isn't known, although all evidence so far points to it being quite challenging.
Next time: Attacks on Diffie-Hellman
