next up previous
Next: One way and collision-free Up: A Whirlwind Tour of Previous: Emergence of public key

Diffie-Hellman key exchange

Alice and Bob want to construct a private key over a public channel.

Both agree on a public prime p and primitive root g modulo p.



  1. Alice chooses a random value x
  2. Alice sends gx mod p to Bob
  3. Bob chooses a random value y
  4. Bob sends gy mod p to Bob
  5. Alice computes gxy mod p as (gxmod p)y mod p
  6. Bob computes gxy mod p as (gymod p)x mod p


Discrete logarithm problem: Given g, p, and gx mod p, find x.

Diffie-Hellman problem: Given g, p, gx mod p, and gy mod p, find gxy mod p.



Kevin McCurley
1/23/1998