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 $n$ is. In modular arithmetic, a number $g$ is a primitive root modulo $n$ if, for every integer $a$ coprime to $n$, there is an integer $k$ such that Such $k$ is called index or discrete logarithm of $a$ to the base $g$ modulo $n$

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

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

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

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