# 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!

## 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: 730547563Base  g: 4g^a: 4096g^b: 16777216Shared secret A^b: 0x23533229Shared secret B^a: 0x23533229Prime p: 1146660275211349850274803697017Base  g: 35g^a: 703152882437914391137998747813g^b: 302066547797101321667785500657Shared secret A^b: 0x14901821721579422765303341433Shared secret B^a: 0x14901821721579422765303341433Prime p: 1312914435623925242579913123095835705606131294279008317556477Base  g: 91g^a: 260025110135259411029398066614928316766970763876919890714931g^b: 1516449130501758165088248370527242650801Shared secret A^b: 0x256764771091704047183548835673182476142676286467672266536118Shared secret B^a: 0x256764771091704047183548835673182476142676286467672266536118`
Yet a different seed (9) results in a bad generator:
`Prime p: 981325853Base  g: 7g^a: 282475249g^b: 1Shared secret A^b: 0x1Shared secret B^a: 0x1`
Try the code on your machine: Zip, Tar-gzip.  (License is BSD.  Also includes RSA, from last week.)