How Does Diffie-Hellman Key Exchange Work?

The Diffie-Hellman key exchange is a cryptographic protocol that allows two parties to establish a shared secret key over an insecure communication channel without having met beforehand. By relying on mathematical operations that are easy to perform in one direction but extremely difficult to reverse, both parties can independently compute the same secret value while an eavesdropper observing all exchanged messages cannot practically determine it.

Public Parameters

Before the exchange begins, the two parties—commonly referred to as Alice and Bob—agree on two public numbers: a large prime modulus \(p\) and a base \(g\) (called a primitive root modulo \(p\)). These values do not need to be kept secret and can be transmitted openly over the insecure channel.

Generating and Exchanging Keys

Each party chooses a private secret integer and uses modular exponentiation to compute a public value:

  1. Alice chooses a secret integer \(a\) and computes \(A = g^a \bmod p\). She sends \(A\) to Bob.
  2. Bob chooses a secret integer \(b\) and computes \(B = g^b \bmod p\). He sends \(B\) to Alice.

An eavesdropper intercepting the communication can see \(p\), \(g\), \(A\), and \(B\), but does not know \(a\) or \(b\).

Computing the Shared Secret

Once Alice receives \(B\) and Bob receives \(A\), each raises the received public value to their own private exponent modulo \(p\):

  1. Alice computes \(s = B^a \bmod p\).
  2. Bob computes \(s = A^b \bmod p\).

Because of the properties of modular exponentiation, both calculations yield the exact same result:

\[s = (g^b \bmod p)^a \bmod p = g^{ab} \bmod p = (g^a \bmod p)^b \bmod p\]

Alice and Bob now share the secret value \(s\), which can be used directly or passed through a key derivation function to generate a symmetric encryption key for secure communication.

Why Eavesdroppers Cannot Recover the Secret

The security of Diffie-Hellman in classical computing relies on the difficulty of the Discrete Logarithm Problem (DLP). Given \(p\), \(g\), and \(g^a \bmod p\), finding the exponent \(a\) is computationally infeasible when \(p\) is sufficiently large (typically at least 2048 bits). Without knowing either \(a\) or \(b\), an attacker cannot compute \(g^{ab} \bmod p\) from \(A\) and \(B\) alone.

Limitations

While Diffie-Hellman protects against passive eavesdropping, it does not authenticate the identities of the communicating parties. An active attacker can perform a man-in-the-middle attack by intercepting \(A\) and \(B\) and establishing separate shared secrets with Alice and Bob. For this reason, Diffie-Hellman is typically combined with digital signatures or certificates to verify each party's identity.