Diffie-Hellman(-Merkel) Key Exchange

Computer Security Lecture, Dr. Lawlor

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.
  1. 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.
  2. 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.
  3. Alice picks a secret integer a.  She sends out a public version of this: A = Ga mod P. 
  4. Bob picks a secret integer b.  He sends out a public version of this: B = Gb mod P.
  5. Alice computes S=Ba mod P
  6. Bob computes S=Ab mod P
  7. Both sides end up with the same S because (Gb)a = (Ga)b .
  8. S is now a shared secret. 
The idea is it's supposed to be tough for attackers to figure out the shared secret based only on the public values A and B without knowing the secrets a or b.  This is known as the discrete logarithm problem (see below).

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.)
G=3; # generator for the field P
nbits=256; # approximate size of the prime P


# Alice side:
A=pow(G,a,P); # = (G^a) mod P

#      Bob side:
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:
print("Alice gets shared secret: ",hex(Ba));

print("  Bob gets shared secret: ",hex(Ab));

print("Elapsed time in seconds: ",elapsed);

(Try this in NetRun now!)

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. */

/* 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);

(Try this in NetRun now!)

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

Discrete Logarithm

Note that Eve knows A=Ga mod P, and she knows the integer A, the generator G (probably just 2), and the fixed prime P.  It seems like it would be trivial to figure out the exponent a from this, but because of the mod P, the generator wraps around again and again during the exponent computation.

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?

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!
Exponentiation table, modulo the prime 509

(Try this in NetRun now!)