## Diffie-Hellman Key Exchange

**Alan Westrope, 1998**

**T**he
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 people like 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 (*g*^{a} mod *p*) =
*A* and sends *A* to Bob, while Bob calculates
(*g*^{b} mod *p*) =
*B* and sends *B* to Alice. Alice computes her
key as *B*^{a} mod *p*, and it’s
identical to Bob’s key, *A*^{b} mod *p*,
because both are equivalent to *g*^{ab} 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