Diffie-Hellman Key Exchange — Establishing Shared Secrets

Whitfield Diffie and Martin Hellman published 'New Directions in Cryptography' in 1976 — the paper that invented public key cryptography. The Diffie-Hellman key exchange protocol solves the fundamental key distribution problem: how do two parties who have never met establish a shared secret over a public channel?

The protocol is used in every TLS handshake (HTTPS), every SSH connection, every Signal message. Its security rests on the discrete logarithm problem: given g^x mod p, computing x is computationally infeasible for large p. Ephemeral Diffie-Hellman (DHE/ECDHE) in TLS provides forward secrecy — past sessions remain secure even if the server's long-term key is later compromised.

The Protocol

Public parameters: large prime p, generator g. Alice chooses private a, sends A = g^a mod p. Bob chooses private b, sends B = g^b mod p. Shared secret = A^b = B^a = g^(ab) mod p. An eavesdropper sees p, g, A, B but cannot compute g^(ab) without solving the discrete log problem.

import random

# Using small numbers for demonstration — real DH uses 2048+ bit primes
P = 23   # prime modulus (real: 2048+ bits)
G = 5    # generator

# Alice
alice_private = random.randint(2, P-2)
alice_public  = pow(G, alice_private, P)

# Bob
bob_private = random.randint(2, P-2)
bob_public  = pow(G, bob_private, P)

# Exchange public keys over insecure channel
# Alice computes shared secret
alice_secret = pow(bob_public, alice_private, P)
# Bob computes shared secret
bob_secret   = pow(alice_public, bob_private, P)

print(f'Alice public: {alice_public}')
print(f'Bob public:   {bob_public}')
print(f'Alice secret: {alice_secret}')
print(f'Bob secret:   {bob_secret}')
print(f'Match: {alice_secret == bob_secret}')

The Discrete Logarithm Problem

DH security rests on: given g, p, and g^x mod p, find x. This is the discrete logarithm problem. The best classical algorithms (Index Calculus, Number Field Sieve) run in sub-exponential time — which is why 2048-bit DH parameters are needed even though AES-128 is considered equivalent security.

Note: Shor's quantum algorithm solves discrete log in polynomial time. Elliptic curve Diffie-Hellman (ECDH) suffers the same quantum vulnerability. Post-quantum key encapsulation (CRYSTALS-Kyber) is the replacement being deployed in TLS 1.3 and Signal.

Forward Secrecy

DH enables forward secrecy — a property that makes past sessions immune to future key compromise. In classic RSA key exchange, the server's RSA private key encrypts the session key. If an attacker records encrypted traffic and later obtains the RSA key, they can decrypt all past sessions.

DHE (ephemeral DH): each TLS session generates a fresh DH key pair. Even if the server's certificate key is compromised, past session keys cannot be derived — they were never stored and the ephemeral DH keys are discarded after use. TLS 1.3 mandates ephemeral key exchange (ECDHE) and removed all non-forward-secret cipher suites.

Frequently Asked Questions