Diffie-Hellman Key Exchange


The 1976 publication of “New Directions in Cryptography,” by Whitfield Diffie and Martin Hellman, was epochal in cryptographic history. Many regard it as the beginning of public-key cryptography, analogous to a first shot in what has become an ongoing battle over privacy, civil liberties, and the meaning of sovereignty in cyberspace. When Public Key Partners’ patent on the Diffie-Hellman algorithm expired on April 29, 1997, crypto-cognoscenti worldwide held parties, then began incorporating the protocol, along with extensions by such people as Taher ElGamal, into their programs.

The protocol is based on modular exponentiation using a public base g, a public modulus p, and private exponents secretly chosen by each participant. For Alice and Bob to agree on a secret key, Alice first chooses a large integer a and Bob chooses a large integer b. Alice then calculates (ga mod p) = A and sends A to Bob, while Bob calculates (gb mod p) = B and sends B to Alice. Alice computes her key as Ba mod p, and it’s identical to Bob’s key, Ab mod p, because both are equivalent to gab mod p. Alice and Bob can now use the shared key with a cipher of their choice for secure communication, as you can see from my simple demonstration.

You can enter exponents from 2 to 999 for Alice and Bob, then click “Go!” to see the calculations and verify that both participants wind up with identical keys. (If you choose exponents no greater than 256, you’ll be able to see the intermediate results in the modular exponentiation. Displaying larger results would require a very wide screen!)

An adversary will find it extremely difficult to determine a, b, or the shared key from the publicly available information (g, p, A, and B). Even Alice and Bob can’t deduce each other’s exponent. (In this simple demo, it might be feasible to reconstruct the private exponents because my program won’t allow exponents larger than 3 digits, but a real-world implementation would use exponents perhaps 300 digits in length. I kept the exponents small not because of any computational difficulties with large numbers, but simply to facilitate displaying the exponents onscreen.)

With more than 2 people, everyone passes the intermediate results to the person on their right until the keys have been determined, requiring n - 1 exchanges for n people. I’ve included demos for 3 and 4 people, illustrating again that the final keys will be identical.

References:
Diffie, W., and Hellman, M.E., New Directions in Cryptography, IEEE Transactions on Information Theory, vol. 22, no. 6, November 1976, pp. 644-654.
RFC 2631—Diffie-Hellman Key Agreement Method
Cisco document by Jennifer Wesp explains using Diffie-Hellman for secure communication between routers.