Diffie-Hellman key exchange is a way for two parties to set up a shared secret despite everything being monitored in both directions between them. Diffie and Hellman wrote the original paper in 1976, but in 2002 Hellman suggested Merkel should also get credit, since Merkel suggested the underlying math, which is used for a wide swath of modern crypto.

The basic operation is "modular exponentiation" on large numbers: raising a number to a power, modulo a big prime.

- Pick a big prime number P. All arithmetic from here is modulo this number, we're "operating in the finite field of prime order, GF(P)". You can publish this prime.
- Pick a generator G, which we'll raise to various powers. The below algorithm will work if powers of G cycle quickly in the field, but won't be as secure, so ideally the generator doesn't repeat. You publish this too.
- Alice picks a secret integer
*a*. She sends out a public version of this:*A = G*mod^{a}*P*.

- Bob picks a secret integer
*b*. He sends out a public version of this:*B = G*mod^{b}*P*. - Alice computes
*S*=*B*mod^{a}*P*.

- Bob computes
*S*=*A*mod^{b}*P*.

- Both sides end up with the same S because
*(G*)^{b}=^{a}*(G*)^{a}.^{b }

*S*is now a shared secret.

Note there is no authentication--you know you're talking to somebody securely, but not who you're talking to. (You might have just established a shared secret with an impostor!)

Here's a full Diffie-Hellman key exchange example, using the multi-precision arithmetic built into Python:

from time import time; # timing from random import SystemRandom; # cryptographic random byte generator rand=SystemRandom(); # create strong random number generator # This is the prime modulus used by SECG secp256k1, the BitCoin elliptic curve. # Note for real security, you should use at least a 2048-bit prime, # to resist number sieve field attacks. (Or use an elliptic curve.) P=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F; G=3; # generator for the field P nbits=256; # approximate size of the prime P start=time(); # Alice side: a=rand.getrandbits(nbits); A=pow(G,a,P); # = (G^a) mod P # Bob side: b=rand.getrandbits(nbits); B=pow(G,b,P); # = (G^b) mod P # Alice and Bob exchange A and B here (in public) print("Alice public key: ",hex(A)); print(" Bob public key: ",hex(B)); # Now we can compute shared secrets in private: Ba=pow(B,a,P); print("Alice gets shared secret: ",hex(Ba)); Ab=pow(A,b,P); print(" Bob gets shared secret: ",hex(Ab)); elapsed=time()-start; print("Elapsed time in seconds: ",elapsed);Here's a version in C++ using my own personal bignum library:

#include "osl/bignum.h" /* multi-precision arithmetic */ // We operate on 256-bit integers typedef bignum<256> integer; // This function returns a cryptographically random integer. // Or at least, it's supposed to! integer randInteger(void) { return rand(); // fail! } /* This is a big prime number. It's the same one as used by SECG secp256k1 (the BitCoin elliptic curve); but for Diffie-Hellman any prime will do. */ integer P("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F"); /* This is the generator, ideally with high order in the field. */ integer G(3); void foo(void) { // Alice picks an integer, and raises G to that power (mod P) integer a=randInteger(); // secret integer A=G.powmod(a,P); // public std::cout<<"Sending Bob A="<<A; // Bob picks an integer, and does the same thing integer b=randInteger(); // secret integer B=G.powmod(b,P); // public std::cout<<"Sending Alice B="<<B; // Alice and Bob multiply their integers integer Ba=B.powmod(a,P); // (G^b)^a integer Ab=A.powmod(b,P); // (G^a)^b std::cout<<" Alice's B^a="<<Ba; std::cout<<" Bob's A^b="<<Ab; // Eve has both sent values A and B, but not either secret a or b std::cout<<" Eve's A*B="<<(A*B).mod(P); }

Example run:

Sending Bob A=0x13218987dc0254d9ec3b71751e15371ef31fd0d283c553fe55590b0e76781bb3 Sending Alice B=0xac255f9fcbe9811bc033c1da2e72e1c21090d9062d175dbb3d64c191c87b1639

Alice's B^a=0xe735195909796602a676bf77f8f06962ef42d2e415e921e68675964c04ce50f8 Bob's A^b=0xe735195909796602a676bf77f8f06962ef42d2e415e921e68675964c04ce50f8

Eve's A*B=0x5193e245862d9f2f610dfac680d7dba0650e16513c30b2ee61a9bf76bbf0f453

Note that Eve knows *A=G** ^{a}* mod

Essentially, we're using modular exponentiation like a hash
algorithm, to conceal the secret exponent a. We don't care
much about collision resistance; and indeed every time you add P
to the exponent, you get another collision (because P is the
modulus). We care a lot about preimage resistance, since
exponentiation is the only thing keeping our secret exponent
secret.

How hard is this discrete
logarithm problem, the basis of Diffie-Hellman and several
other cryptographic algorithms?

- Brute force is to just try every possible
*a*, raise G to that power, and see if you get A. For an*n*-bit number, this takes O(2^{n}) multiplies, which is exponential time. It does parallelize nicely, but even a 128-bit prime is just too big to search.

- There are a bunch of more sophisticated algorithms, but the
best classical algorithms known run in O(2
^{n/2}) time, the square root of brute force, but still exponential. The square root means you should use at least a 256-bit prime to get the equivalent of 128 bits of security. - For fixed primes, precomputation is an option, a recent paper argues for using at least 2048-bit primes to avoid a precomputation attack by an adversary with large resources.
- On a quantum computer, Shor's
algorithm can use the quantum fourier transform to solve
the discrete logarithm in faster than O(n
^{3}) time. This means you should assume Diffie-Hellman is broken if Shor-capable quantum computers exist with enough bits to fit the prime.

We'll talk a lot more about multiplication on Monday, but here's
a table of exponents for arithmetic modulo the tiny prime
P=509. Each row acts as a generator, each column as the
exponent, and the brightness of the pixel shows the product.
Raising 0 or 1 to any power doesn't do anything, so the top two
rows are black. Raising any number to the power 0 or 1 isn't
very interesting, so the left two columns are uninteresting.
Note how much of the table looks like random chaos!