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.
  1. Pick a big prime number p.  All arithmetic from here is modulo this number.  Unlike RSA, you publish this.
  2. Pick a base g, which for security needs to be a "generator" of p.  You publish this too.
  3. Your side picks a secret integer a.  You send out A = ga mod p.
  4. Their side picks a secret integer b.  They send out B = gb mod p.
  5. You compute S=Ba mod p.  They compute S=Ab mod p.  Both sides end up with the same S because (gb)a = (ga)b .
  6. 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!


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.


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