Diffie-Hellman(-Merkel) Key Exchange

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 = G^a mod P. 
   
4. Bob picks a secret integer b.  He sends out a public version of this: B = G^b mod P.
5. Alice computes S=B^a mod P. 
   
6. Bob computes S=A^b mod P. 
   
7. Both sides end up with the same S because (G^b)^a = (G^a)^b .
   
8. S is now a shared secret. 

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

(Try this in NetRun now!)

#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);
}

(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=G^a 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?

• 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ⁿ) 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³) 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!

(Try this in NetRun now!)