Diffie-Hellman key exchange

Diffie-Hellman (shortened DH), is one of the first examples of public key exchange implemented within the field of cryptography. The strength of this method is that it allows two (or more) parties to establish a shared secret key over an insecure channel, even though they have no prior knowledge of each other.

To fully understand how DH works under the hood, we first need to explain what a primitive root modulo is. In modular arithmetic, a number is a primitive root modulo if, for every integer coprime to , there is an integer such that Such is called index or discrete logarithm of to the base modulo

The original implementation of DH protocol uses the multiplicative group of integers modulo , where is a prime, and is a primitive root modulo . In this way, we ensure that the shared secret can take on any value from to

Let's now see a step-by-step explanation of the protocol:

  1. Alice and Bob agree to use a modulus and base , i.e. a primitive root modulo
  2. Alice chooses a random secret integer , and then sends Bob
  3. Bob does the same thing, using for example , hence sending
  4. Alice computes the shared secret key as follows
  5. And Bob computes

The two parties have arrived at the same value (the shared secret key ), because