Next: One way and collision-free
Up: A Whirlwind Tour of
Previous: Emergence of public key
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.
- Alice chooses a random value x
- Alice sends gx mod p to Bob
- Bob chooses a random value y
- Bob sends gy mod p to Bob
- Alice computes gxy mod p as (gxmod p)y mod p
- 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