Exchanging Secret Keys

CS 463 Lecture, Dr. Lawlor

Diffie–Hellman–Merkle key exchange is a neat, simple way to exchange private keys with a communication party. Like RSA, the basic operation is modular exponentiation on large numbers.

Pick a big prime number p. All arithmetic from here is modulo this number. Unlike RSA, you publish this.
Pick a base g, which for security needs to be a "generator" of p. You publish this too.
Your side picks a secret integer a. You send out A = g^a mod p.
Their side picks a secret integer b. They send out B = g^b mod p.
You compute S=B^a mod p. They compute S=A^b mod p. Both sides end up with the same S because (g^b)^a = (g^a)^b.
S is now a shared secret. There aren't any fast algorithms known for the discrete logarithm problem, so it's tough for attackers to figure out

CAUTION: unlike RSA signatures, 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!

Generators

Turns out that you always end up with the same secret for any g. But poor choices for g (not generators) tend to end up with a shared secret of... just 1! There's nothing magic about the good values, so you can actually use published values (theoretically this makes you somewhat more vulnerable to a rainbow table style enumeration attack, but this is still much better than converging to a one-digit key). See discussion of problem here.

Example

Here's a trivial example, using the BigInteger class we used for RSA.

	// Generate shared public values:
	BigInteger p=BigInteger::probablePrime(bits); // publish
	BigInteger g=BigInteger::random(bits/2);  // FIXME: find generator
	
	// side A:
	BigInteger a=BigInteger::random(bits/2);
	BigInteger A=g.modPow(a,p);
	
	// side B:
	BigInteger b=BigInteger::random(bits/2);
	BigInteger B=g.modPow(b,p);
	
	// .. exchange A and B across network here ...
	
	// Compute private keys
	BigInteger SA=A.modPow(b,p); // on B side
	BigInteger SB=B.modPow(a,p); // on A side
	
	// Print results
	std::cout<<"Prime p: "<<p<<"\n";
	std::cout<<"Base  g: "<<g<<"\n";
	std::cout<<"g^a: "<<A<<"\n";
	std::cout<<"g^b: "<<B<<"\n";
	std::cout<<"Shared secret A^b: 0x"<<SA.hex()<<"\n";
	std::cout<<"Shared secret B^a: 0x"<<SB.hex()<<"\n";

On my machine, for bit sizes of 30, 100, and 200 (all too small for real security!), this prints:

Prime p: 730547563
Base  g: 4
g^a: 4096
g^b: 16777216
Shared secret A^b: 0x23533229
Shared secret B^a: 0x23533229

Prime p: 1146660275211349850274803697017
Base  g: 35
g^a: 703152882437914391137998747813
g^b: 302066547797101321667785500657
Shared secret A^b: 0x14901821721579422765303341433
Shared secret B^a: 0x14901821721579422765303341433

Prime p: 1312914435623925242579913123095835705606131294279008317556477
Base  g: 91
g^a: 260025110135259411029398066614928316766970763876919890714931
g^b: 1516449130501758165088248370527242650801
Shared secret A^b: 0x256764771091704047183548835673182476142676286467672266536118
Shared secret B^a: 0x256764771091704047183548835673182476142676286467672266536118

Yet a different seed (9) results in a bad generator:

Prime p: 981325853
Base  g: 7
g^a: 282475249
g^b: 1
Shared secret A^b: 0x1
Shared secret B^a: 0x1

Try the code on your machine: Zip, Tar-gzip. (License is BSD. Also includes RSA, from last week.)