Diffie–Hellman Key Exchange: How Two Strangers Create a Shared Secret

In secure communication, one of the fundamental problems is key exchange:

How can two parties agree on a secret key over a public channel without anyone else learning it?

The Diffie–Hellman (DH) Key Exchange algorithm solves exactly this problem. It allows two users to generate a shared secret even when an attacker is listening to the entire conversation.

The Core Idea Behind Diffie–Hellman

Diffie–Hellman is based on a mathematical principle:

• Some operations are easy to perform
• But extremely hard to reverse

Specifically, DH relies on the Discrete Logarithm Problem:

• Easy: compute $a^x \bmod p$
• Hard: compute $x$ from $a^x \bmod p$

This one-way nature enables secure key exchange.

Why This Matters:

• Exponentiation modulo a prime is computationally efficient
• Finding the exponent (discrete logarithm) is computationally infeasible for large primes
• This asymmetry creates the security foundation

Public and Private Values

Publicly Known (Everyone Can See)

• $p$ → a large prime number
• $a$ → a primitive root modulo $p$

These values are not secret and can be shared publicly.

Properties:

• $p$ is typically 2048 bits or larger for security
• $a$ is a generator that produces all values from 1 to $p-1$ when raised to different powers
• These parameters are often standardized (e.g., RFC 7919)

What Is a Primitive Root?

A primitive root (also called a generator) modulo $p$ is a number $a$ such that the sequence:

$a^1 \bmod p, a^2 \bmod p, a^3 \bmod p, \ldots, a^{p-1} \bmod p$

contains all integers from 1 to $p-1$ exactly once.

In other words, $a$ is a primitive root modulo $p$ if the set $\{a^1 \bmod p, a^2 \bmod p, \ldots, a^{p-1} \bmod p\}$ equals the set $\{1, 2, 3, \ldots, p-1\}$.

Example: For $p = 7$, $a = 3$

The result modulo 7 are: $3, 2, 6, 4, 5, 1$

All values from 1 to 6 appear exactly once.

Therefore, $a = 3$ is a primitive root modulo $7$ because it maintains the sequence property—the powers of 3 modulo 7 generate all integers from 1 to 6 exactly once.

The Discrete Logarithm Property:

For any integer $b$ in the range $[1, p-1]$, there exists a unique $i$ such that:

$b \equiv a^i \bmod p$

So:

$\text{dlog}_{a,p}(b) = i$

Key Insight:

• Computing $a^i \bmod p$ is easy — Efficient exponentiation algorithms exist
• Finding $i$ is very difficult — This is the discrete logarithm problem

Why This Matters for Security:

• Given $Y_a = a^{X_a} \bmod p$ (public key), finding $X_a$ (private key) requires solving the discrete logarithm
• For large primes (2048+ bits), this is computationally infeasible
• This one-way property is what makes Diffie–Hellman secure

Secret (Kept Private)

• $X_a$ → Alice's private key
• $X_b$ → Bob's private key

Only the owner knows their private key.

Properties:

• Private keys are randomly chosen large numbers
• Typically 256 bits or larger
• Must remain secret—never shared or transmitted

Step-by-Step Diffie–Hellman Algorithm

Step 1: Private Key Selection

Each party chooses a secret number.

• Alice chooses $X_a$ (her private key)
• Bob chooses $X_b$ (his private key)

Requirements:

• Private keys must be random
• Should be large enough to resist brute-force attacks
• Typically chosen from the range $[1, p-1]$

Step 2: Public Key Generation

Each party computes a public key using:

$Y = a^X \bmod p$

• Alice computes: $Y_a = a^{X_a} \bmod p$

• Bob computes: $Y_b = a^{X_b} \bmod p$

They exchange $Y_a$ and $Y_b$ openly over the public channel.

Key Insight:

• Public keys can be transmitted without encryption
• Even if intercepted, they don't reveal the private keys
• The discrete logarithm problem protects the private keys

Step 3: Shared Secret Key Computation

Now both compute the shared secret:

• Alice computes: $K = (Y_b)^{X_a} \bmod p$

• Bob computes: $K = (Y_a)^{X_b} \bmod p$

Why Both Get the Same Value:

Because: $(Y_b)^{X_a} = (a^{X_b})^{X_a} = a^{X_a X_b}$

$(Y_a)^{X_b} = (a^{X_a})^{X_b} = a^{X_a X_b}$

✔️ Both parties obtain the same secret key $K$

Mathematical Proof:

• Alice computes: $K = (a^{X_b})^{X_a} \bmod p = a^{X_a X_b} \bmod p$
• Bob computes: $K = (a^{X_a})^{X_b} \bmod p = a^{X_a X_b} \bmod p$
• Both results are identical: $a^{X_a X_b} \bmod p$

Numerical Example

Let's work through a concrete example with small numbers (for clarity—real systems use much larger values):

Public Parameters:

• $p = 353$ (prime number)
• $a = 3$ (primitive root modulo 353)

Alice's Side:

• Private key: $X_a = 97$
• Public key: $Y_a = 3^{97} \bmod 353 = 40$
• Alice sends $Y_a = 40$ to Bob

Bob's Side:

• Private key: $X_b = 233$
• Public key: $Y_b = 3^{233} \bmod 353 = 248$
• Bob sends $Y_b = 248$ to Alice

Shared Secret Computation:

• Alice computes: $K = 248^{97} \bmod 353 = 160$
• Bob computes: $K = 40^{233} \bmod 353 = 160$

✔️ Shared secret key $K = 160$

Verification:

• Both parties independently computed the same value: $160$
• This shared secret can now be used for symmetric encryption
• An attacker who intercepted $40$ and $248$ cannot compute $160$ without solving the discrete logarithm problem

Why Diffie–Hellman Is Secure

An attacker can see:

• $p$ (public prime)
• $a$ (public generator)
• $Y_a$ (Alice's public key)
• $Y_b$ (Bob's public key)

But cannot compute:

• $X_a$ (Alice's private key)
• $X_b$ (Bob's private key)
• or the shared key $K$

Why?

Because that would require solving the Discrete Logarithm Problem:

• Given $Y_a = a^{X_a} \bmod p$, find $X_a$
• Given $Y_b = a^{X_b} \bmod p$, find $X_b$

This is computationally infeasible for large primes (e.g., 2048-bit).

Security Level:

Modern Recommendation: Use at least 2048-bit primes for production systems.

The Man-in-the-Middle (MITM) Problem

Diffie–Hellman creates secrecy, but it does not verify identity.

How MITM Works

Attack Scenario:

1. Attacker intercepts Alice's public key $Y_a$
2. Attacker sends their own public key $Y_{attacker}$ to Bob
3. Attacker establishes:
   • One shared key with Alice: $K_1 = (Y_a)^{X_{attacker}} \bmod p$
   • Another shared key with Bob: $K_2 = (Y_b)^{X_{attacker}} \bmod p$
4. Attacker decrypts, modifies, and re-encrypts messages between Alice and Bob

But why why Bob accepts attacker’s key?

Bob accepts the attacker’s public key because plain Diffie–Hellman does not authenticate public keys, so Bob has no way to know which public key belongs to Alice.

❌ Alice and Bob think they're talking to each other—but they're not.

Visual Representation:

Alice                    Attacker                    Bob
  |                         |                         |
  |--- Y_a ---------------->|                         |
  |                         |--- Y_attacker ---------->|
  |                         |<--- Y_b -----------------|
  |<--- Y_attacker ---------|                         |
  |                         |                         |
  | (thinks talking to Bob) | (intercepts all)        | (thinks talking to Alice)

What the Attacker Can Do:

• Read all messages between Alice and Bob
• Modify messages before forwarding
• Inject their own messages
• Maintain separate encrypted sessions with each party

Why MITM Works

The Problem:

• Diffie–Hellman only establishes a shared secret
• It does not authenticate who you're communicating with
• Public keys are exchanged without verification
• No way to verify the public key actually belongs to the intended party

Preventing MITM Attacks

Diffie–Hellman must be combined with authentication:

1. Digital Signatures

How It Works:

• Each party signs their public key with their private signing key
• Recipient verifies the signature using the sender's public signing key
• Ensures public key actually came from the claimed sender

Example:

• Alice signs $Y_a$ with her private signing key
• Bob verifies the signature using Alice's public signing key
• If verification succeeds, Bob knows $Y_a$ is authentic

For more details, see: Digital Signatures: Proving Identity and Integrity

2. Certificates (PKI)

How It Works:

• Public keys are embedded in digital certificates
• Certificates are signed by trusted Certificate Authorities (CAs)
• Recipient verifies certificate chain to trusted root

Example:

• Alice's public key is in a certificate signed by a CA
• Bob verifies the certificate using the CA's public key
• If valid, Bob trusts Alice's public key

Where Diffie–Hellman Is Used

Diffie–Hellman is fundamental to modern secure communication:

1. HTTPS (TLS Handshake)

• Used in TLS 1.2 and earlier versions
• Establishes session keys for encrypted web traffic
• Combined with certificate authentication

2. Secure Messaging Apps

• Signal, WhatsApp, Telegram
• End-to-end encryption key establishment
• Forward secrecy (new keys for each session)

3. VPNs

• IPsec, OpenVPN
• Secure tunnel establishment
• Key exchange for encrypted VPN connections

4. SSH (Secure Shell)

• Key exchange during SSH connection setup
• Establishes session encryption keys
• Used in combination with host authentication

5. Key Agreement in Modern Cryptographic Protocols

• ECDH (Elliptic Curve Diffie–Hellman)
• X25519 (Curve25519-based key exchange)
• Modern TLS 1.3 uses ECDH variants

Real-World Impact:

• Protects billions of daily internet transactions
• Enables secure e-commerce, banking, and communication
• Foundation of modern internet security

Key Takeaways

• ✅ Diffie–Hellman securely establishes a shared secret over a public channel
• ✅ Security is based on the hardness of the discrete logarithm problem
• ⚠️ DH alone does not authenticate identities
• ✅ Authentication is required to prevent MITM attacks
• ✅ Widely used in modern secure communication protocols

Remember:

• Diffie–Hellman solves the key distribution problem
• It enables secure communication without prior shared secrets
• Always combine with authentication for complete security
• Use appropriate key sizes for your security requirements

One-Line Summary

Diffie–Hellman enables secure key exchange over an insecure channel by leveraging one-way mathematical functions, forming the foundation of modern secure communication.