Diffie-Hellman Key Exchange

• Based on the Decision Diffie-Helman Problem: there is no efficient probabilistic algorithm that given (ga mod n, gb mod n, gc mod n) outputs true if c=ab and false, otherwise.

• Allows two entities to compute a shared key.

• Algorithm :
  • Zn* = {1, …, n-1}, n prime and g generator, n and g public.

Compute (gb mod n)a = gab mod n = K

ga mod n

gb mod n

Compute (ga mod n)b = gab mod n = K

Pick random, secret a

Compute and send ga mod n

Pick random, secret b

Compute and send gb mod n

Previous slide

Next slide

Back to first slide

View graphic version