Diffie-Hellman Key Exchange

Unlike RSA, where you can send messages of your choice, the DHKE is used to generate a secret number shared between Alice and Bob. This shared secret is then used as the key for a symmetric cryptosystem like AES.

The Key Exchange

A large prime $p$ and a generator $g \in \mathbb{F}_p, g \neq 0$ are made public.

Alice and Bob choose their secret integers $a$ and $b$ respectively. They then compute the following:

$$A = g^a \mod p \\ B = g^b \mod p$$

These numbers $A$ and $B$ are exchanged between Alice and Bob over a public channel. Once the other person's number is received, they then put it to the power of their secret integer, i.e. Alice computes $B^a$ and Bob computes $A^b$, both modulo $p$. Note that:

$$B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b$$

This means that once they do this, they are in possession of the same number, which they can then use as a shared secret.

The Discrete Logarithm Problem

The safety of the Diffie-Hellman Key Exchange is grounded on he difficulty of solving the discrete logarithm problem - the difficulty of computing $x$ given

$$g^x \equiv a \mod p$$

You can see this in Overview presented above - the values $g^a \mod p$ and $g^b \mod p$ are sent over a public channel, but because we cannot solve the DLP efficiently an attacker is unable to retrieve $a$ or $b$. We say that the DLP is DHKE's trapdoor function.

As you may expect from here, many attacks on Diffie-Hellman rely on situations in which you can efficiently compute the discrete logarithm.