Diffie-Hellman Key Exchange in Depth: Discrete Log, Safe Primes, MITM, and X25519 in Python

Why Learn Diffie-Hellman?

Diffie-Hellman key exchange (DH) was proposed in 1976 by Whitfield Diffie and Martin Hellman and is the origin of modern public-key cryptography. Before DH, only symmetric-key cryptography existed, leaving the foundational problem of “how do you securely share a key in the first place?” unsolved. DH showed that two parties can establish a shared secret over a fully public channel, opening the public-key era together with RSA , which appeared a year later.

DH and RSA are often confused but serve different purposes. RSA is a public-key cipher that encrypts the message itself, whereas DH is a key-agreement protocol that does not encrypt messages directly but instead produces a shared secret that feeds a symmetric cipher such as AES. In practice the hybrid pattern (DH key + AES bulk encryption) is standard.

DH underpins much of today’s infrastructure: TLS 1.3 mandates ECDHE (ephemeral ECDH), SSH uses DH group exchange or curve25519-sha256, and Signal uses Triple Diffie-Hellman (3DH/X3DH). The mathematical core is the same across these. This article goes beyond the basics with Python implementations. For the fast exponentiation that powers DH, see Fast Modular Exponentiation Using Binary Exponentiation , and for a wider tour of cryptography see the Cryptography Roadmap .

Discrete Logarithm Problem (DLP)

DH’s security rests on the computational hardness of the discrete logarithm problem (DLP). Fix a prime \(p\) and a generator (primitive root) \(g\) of \(\mathbb{Z}_p^*\) . For some \(h \in \mathbb{Z}_p^*\) , the integer \(x\) satisfying

is the discrete logarithm of \(h\) with base \(g\) . Forward computation of \(g^x \bmod p\) runs in \(O(\log x)\) via exponentiation by squaring , but recovering \(x\) from \(h\) requires sub-exponential time (\(L_p[1/3, c]\) ) with the best known algorithms (Number Field Sieve, Pollard’s rho). With \(p \ge 2048\) bits the inverse is intractable. This easy-forward, hard-inverse asymmetry is the same flavor of one-way function that powers RSA via integer factorization.

Primitive Root

The order of \(\mathbb{Z}_p^*\) is \(p-1\) . An element \(g\) is a primitive root when its powers \(\{g^0, g^1, \dots, g^{p-2}\}\) cover all of \(\mathbb{Z}_p^*\) , equivalently when the order of \(g\) equals \(p-1\) . With a primitive root, \(\mathbb{Z}_p^*\) is cyclic and the shared secret \(K = g^{ab} \bmod p\) is uniformly distributed across the group.

The Protocol

Alice and Bob first agree on public parameters \((p, g)\) where \(p\) is a large prime and \(g\) is a primitive root of \(\mathbb{Z}_p^*\) . These are not secret; in practice, fixed parameters from RFC 3526 or RFC 7919 are used.

Step 1. Alice picks a random secret \(a \in [2, p-2]\) and computes her public value.

Step 2. Bob picks a random secret \(b\) and computes his public value.

Step 3. Alice and Bob exchange \(A, B\) over the public channel. The eavesdropper Eve sees \((p, g, A, B)\) .

Step 4. Alice combines Bob’s \(B\) with her own secret \(a\) .

Step 5. Bob does the symmetric computation.

Commutativity of exponents gives \(K_A = K_B = g^{ab} \bmod p\) , so both parties share the same secret \(K\) . In production this raw \(K\) is not used directly as a symmetric key; instead it is run through a hash/KDF such as HKDF-SHA256.

Eve has no efficient way to derive \(g^{ab}\) from \(A, B\) alone. This is the Computational Diffie-Hellman (CDH) assumption, with the stronger Decisional Diffie-Hellman (DDH) assumption also underpinning many DH-based proofs. CDH being solvable implies DLP being solvable, but the converse is not obviously true.

Security and Safe Primes

A large \(p\) alone is not enough. Attackers can use small-subgroup attacks to pin the shared secret to a low-order subgroup and then break the discrete log there with Pohlig-Hellman. The standard countermeasure is to pick a safe prime, i.e. a prime of the form

Here \(q\) is a Sophie Germain prime. Then \(p - 1 = 2q\) , the only prime factors of \(|\mathbb{Z}_p^*|\) are \(2\) and \(q\) , and no exploitable small subgroup exists. Modern practice picks a generator of order \(q\) and performs DH inside the order-\(q\) subgroup (the quadratic residues).

Key-size guidance:

NIST SP 800-57 recommends at least 2048 bits, ideally 3072+. The 2015 Logjam attack made 1024-bit DH practically broken; do not use it.

MITM Attacks and Authenticated Key Exchange

DH’s biggest weakness is the man-in-the-middle (MITM) attack. If Eve sits between Alice and Bob and rewrites \(A \to A' = g^{a'}\) and \(B \to B' = g^{b'}\) , Alice ends up sharing \(g^{ab'}\) with Eve while Bob shares \(g^{a'b}\) , and Eve reads everything in cleartext.

As the diagram shows, the only difference between the honest protocol and MITM is whether Eve merely reads the channel or actively rewrites it. DH has no built-in way to verify who sent \(A\) or \(B\) , so an active adversary goes undetected. The root cause is that DH does not authenticate that \(A, B\) belong to the claimed parties. Countermeasures combine DH with authentication:

1. Signed DH: Sign \(A\) with a long-term key ( RSA or ECDSA) and verify against a PKI-issued certificate. TLS 1.2 ECDHE-RSA fits this pattern.
2. PAKE (Password-Authenticated Key Exchange): Use a shared password to harden DH (SPAKE2, OPAQUE) so even low-entropy secrets resist MITM.
3. STS (Station-to-Station): A classic design embedding signatures inside the DH exchange.
4. TLS 1.3 / Noise Protocol: Integrate certificate auth and ECDHE into a 1-RTT handshake with forward secrecy.

For authentication architectures in the OAuth context, see OAuth 2.0/OIDC Fundamentals . For organization-level architecture see Zero Trust Architecture .

Python Implementation

Minimal Educational Version

With sympy for primality testing and primitive roots, plus Python’s built-in pow(g, a, p) (which uses exponentiation by squaring internally), a safe-prime DH is straightforward.

import secrets
import hashlib
from sympy import isprime, primitive_root


def gen_safe_prime(bits: int) -> tuple[int, int]:
    """Generate a safe prime p = 2q + 1 with q also prime."""
    while True:
        q = secrets.randbits(bits - 1) | (1 << (bits - 2)) | 1
        if not isprime(q):
            continue
        p = 2 * q + 1
        if isprime(p):
            return p, q


def derive_key(shared_secret: int) -> bytes:
    """Derive a 256-bit session key from g^{ab} mod p via SHA-256."""
    nbytes = (shared_secret.bit_length() + 7) // 8
    return hashlib.sha256(shared_secret.to_bytes(nbytes, "big")).digest()


# --- Parameter generation (safe prime) ---
p, q = gen_safe_prime(512)  # 512-bit for demo; use >= 2048 in production
g = primitive_root(p)

# --- Alice ---
a = secrets.randbelow(p - 2) + 2
A = pow(g, a, p)

# --- Bob ---
b = secrets.randbelow(p - 2) + 2
B = pow(g, b, p)

# --- Shared secret ---
K_alice = pow(B, a, p)
K_bob = pow(A, b, p)
assert K_alice == K_bob

session_key = derive_key(K_alice)
print(f"Session key (first 16 bytes): {session_key[:16].hex()}")

Running this generates a 512-bit safe prime and produces output like the following (values change on every run since secrets is a CSPRNG):

p (512-bit safe prime) = 13218332357488551467516559264825623790005044520636005396648441145800235071016302612638629864404576627468196025621538508813206460844413702142028153726001579
q = 6609166178744275733758279632412811895002522260318002698324220572900117535508151306319314932202288313734098012810769254406603230422206851071014076863000789
g (primitive root) = 2
A = 12322118143501225073671333285517151118595792560242845888501209290961584402661227352040238111324862055888433304050750471616026040977135181508218566306196028
B = 8448598785130363115807570455163263351759770980869225353744625472479937931109088888964753475781227661278406114486266237549732608889596380136248477220391184
K_alice == K_bob: True
session key (first 16 bytes): 5515b8545246fb2e8e2380837217d2d
session key (all 32 bytes): 5515b8545246fb2e8e2380837217d2d50eebdda728a2c0a944f012d00531e5d7

The assert K_alice == K_bob passes without raising, confirming that the two independently computed values of \(g^{ab} \bmod p\) are bit-for-bit identical. \(p\) here is a 512-bit safe prime (about 155 decimal digits), and \(g=2\) turned out to be a primitive root.

Four implementation notes:

1. Use secrets, not random: random is not a CSPRNG. Use secrets.randbits and secrets.randbelow for cryptographic randomness.
2. pow(g, a, p) already uses binary exponentiation: see Fast Modular Exponentiation . No need to roll your own.
3. KDF with hashlib.sha256: Never use the raw \(g^{ab}\) as a symmetric key. Hashing normalizes length and absorbs distribution biases (e.g. when restricted to the order-\(q\) subgroup).
4. sympy.primitive_root is only suitable for small \(p\) . For 2048-bit production parameters, use fixed RFC 3526 groups with \(g=2\) .

A Reproducible Verification Run

The code above uses secrets (a CSPRNG), so its output differs on every run. For verification purposes only, we fix the randomness with random.seed() so the same inputs reproduce the same outputs (never use random in production code — the seed here exists solely to demonstrate reproducibility).

import random
import hashlib
from sympy import isprime, primitive_root

random.seed(20260614)  # fixed seed for verification only; production code uses secrets


def gen_safe_prime(bits: int) -> tuple[int, int]:
    while True:
        q = random.getrandbits(bits - 1) | (1 << (bits - 2)) | 1
        if not isprime(q):
            continue
        p = 2 * q + 1
        if isprime(p):
            return p, q


def derive_key(shared_secret: int) -> bytes:
    nbytes = (shared_secret.bit_length() + 7) // 8
    return hashlib.sha256(shared_secret.to_bytes(nbytes, "big")).digest()


p, q = gen_safe_prime(256)
g = primitive_root(p)

a = random.randrange(2, p - 2)
A = pow(g, a, p)

b = random.randrange(2, p - 2)
B = pow(g, b, p)

K_alice = pow(B, a, p)
K_bob = pow(A, b, p)
assert K_alice == K_bob

session_key = derive_key(K_alice)
print(f"p = {p}")
print(f"g = {g}")
print(f"a = {a}")
print(f"b = {b}")
print(f"A = {A}")
print(f"B = {B}")
print(f"K  = {K_alice}")
print(f"session_key.hex() = {session_key.hex()}")

Output (this script produces the same values on every run):

p = 66575616948038377445539429795132878256980195668554356069884263848216667252559
g = 13
a = 22071323109805543890258502561468447972734873442036236587291865671753037173016
b = 43406188405209672097347738883726485118762736511118495407770999805898118744546
A = 17626773632107550791481774575953842105294130954914522230733892518771412915265
B = 27116112464237150180615704853975155125775244034435951887061859079882194029377
K  = 4366696324097873572815777205789404913279110001326052910638077010571506035417
session_key.hex() = c4481ede32245c6bcade44d23066b179d92658f34695a7f757b958b8d70ac2df

Any reader can run this exact script and get the identical \(p, g, a, b, A, B, K\) , verifying firsthand the core claim of DH:

\( K_{\text{alice}} = K_{\text{bob}} = g^{ab} \bmod p \)

Speeding Up with gmpy2

For \(p > 2048\) bits, CPython’s pow becomes noticeably slow. gmpy2.powmod calls GMP’s mpz multiplication and is several to over ten times faster on large exponents.

import gmpy2
import secrets

p = gmpy2.mpz("FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" ...)  # RFC 3526 group 14
g = gmpy2.mpz(2)

a = gmpy2.mpz(secrets.randbits(256))
A = gmpy2.powmod(g, a, p)
# ... and so on

We benchmarked pow(g, a, p) against gmpy2.powmod(g, a, p) at 512/1024/2048/3072/4096-bit key sizes, averaging 30 runs each (macOS arm64, CPython 3.14).

import time
import secrets
import gmpy2

def rand_odd(bits):
    return secrets.randbits(bits) | 1 | (1 << (bits - 1))

for bits in [512, 1024, 2048, 3072, 4096]:
    p = rand_odd(bits)
    g = secrets.randbelow(p - 2) + 2
    a = secrets.randbelow(p - 2) + 2

    t0 = time.perf_counter()
    for _ in range(30):
        pow(g, a, p)
    t_pow = (time.perf_counter() - t0) / 30

    p_m, g_m, a_m = gmpy2.mpz(p), gmpy2.mpz(g), gmpy2.mpz(a)
    t0 = time.perf_counter()
    for _ in range(30):
        gmpy2.powmod(g_m, a_m, p_m)
    t_gmpy = (time.perf_counter() - t0) / 30

    print(f"{bits:5d} bit: pow()={t_pow*1000:.4f} ms, gmpy2={t_gmpy*1000:.4f} ms, speedup={t_pow/t_gmpy:.2f}x")

Results:

  512 bit: pow()=0.9718 ms, gmpy2=0.0728 ms, speedup=13.36x
 1024 bit: pow()=5.2600 ms, gmpy2=0.3716 ms, speedup=14.16x
 2048 bit: pow()=34.0342 ms, gmpy2=1.8802 ms, speedup=18.10x
 3072 bit: pow()=106.8577 ms, gmpy2=6.1426 ms, speedup=17.40x
 4096 bit: pow()=250.5079 ms, gmpy2=13.3575 ms, speedup=18.75x

At the practical key sizes of 2048 bits and above, gmpy2 was 17-19x faster. In contexts like TLS handshakes, where multiple modexp operations occur per connection, or servers handling many concurrent connections, this difference directly affects latency and server load. When using RFC 3526’s fixed 2048-bit parameters (group 14), \(g=2\) is already a known primitive root, so the sympy.primitive_root call can be skipped entirely.

Production Library (cryptography.hazmat)

Real applications should use vetted libraries (cryptography, PyNaCl, OpenSSL) instead of hand-rolling DH. Python’s canonical choice is cryptography.hazmat.primitives.asymmetric.dh.

from cryptography.hazmat.primitives.asymmetric import dh
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

# Generate 2048-bit safe-prime DH parameters (RFC 7919 style)
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Alice's key pair
alice_private = parameters.generate_private_key()
alice_public = alice_private.public_key()

# Bob's key pair
bob_private = parameters.generate_private_key()
bob_public = bob_private.public_key()

# Raw shared secret
alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)
assert alice_shared == bob_shared

# Derive 32-byte session key with HKDF-SHA256
session_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b"handshake data",
).derive(alice_shared)

cryptography.exchange() automatically validates incoming public keys (rejecting small-subgroup elements, \(1\) , \(p-1\) , etc.). Hand-rolled implementations almost always miss these checks, which is reason enough to use the library in production.

DH vs RSA vs ECDH

Three approaches side by side:

ECDH delivers the same security at dramatically smaller key sizes, which is why TLS, Signal, and WireGuard all standardize on ECDH (especially X25519). The catch is that elliptic-curve implementations are very easy to get wrong by hand, so use a library.

For the elliptic-curve variant of ElGamal see Elliptic Curve ElGamal Encryption . The introductory version of DH is in Diffie-Hellman Key Exchange Protocol: Theory and Python Implementation .

Derivative Protocols

The DH framework has been extended for decades.

ECDH (Elliptic Curve Diffie-Hellman)

Replace the finite field \(\mathbb{Z}_p^*\) with the rational-point group of an elliptic curve \(E(\mathbb{F}_p)\) . The exponentiation \(g^a\) becomes a scalar multiplication \(aG\) , and security rests on ECDLP. TLS 1.3 standardizes secp256r1, secp384r1, and x25519. For the mathematics behind elliptic curves (point addition, scalar multiplication, ECDLP) and full Python implementations, see Elliptic Curve Cryptography (ECC) in Python .

X25519 / X448 (Curve25519 family)

X25519 is ECDH over Daniel J. Bernstein’s Montgomery curve Curve25519. Its design highlights:

• Clamping: forces specific bits of the secret to fixed values, eliminating low-order subgroup attacks.
• Constant time: scalar multiplication runs in constant time, resisting side-channel attacks.
• Fixed 32-byte public keys: simple serialization with little room for implementation mistakes.

X25519 is used by OpenSSH, TLS 1.3, Signal, WireGuard, and Tor v3 — essentially every modern protocol. X448 is its higher-strength sibling (224-bit security).

Triple DH (3DH) / X3DH

The asynchronous authenticated key exchange used by Signal. The receiver may be offline when the initial message is sent, so three (X3DH: four) DH outputs are concatenated to derive the key:

where \(IK\) is the long-term identity key, \(SPK\) is a signed prekey, \(OPK\) is a one-time prekey, and \(EK\) is an ephemeral key. X3DH plus the Double Ratchet that follows is what powers end-to-end-encrypted messengers.

Hybrid DH (PQC migration)

In preparation for quantum computers, hybrid key exchange combines classical ECDH with a post-quantum key encapsulation mechanism (KEM), and it is now in production use in TLS 1.3. The design is simple: feed \(\mathrm{DH}(\text{ECDH output}) \,\|\, \mathrm{KEM}(\text{PQC output})\) through a KDF to derive a single shared key, so the result stays secure as long as either component is unbroken — the weaker side never drags the whole scheme down.

The timeline: Google Chrome enabled X25519Kyber768Draft00 — combining X25519 with Kyber-768 — by default in August 2023 (Chrome 116), and Cloudflare added support for the same combination on its origin-server connections around the same time. After NIST standardized Kyber under the name ML-KEM, Chrome switched to X25519MLKEM768 in September 2024. The IETF TLS working group’s draft-ietf-tls-ecdhe-mlkem (specifying three mechanisms: X25519MLKEM768, SecP256r1MLKEM768, and SecP384r1MLKEM1024) has reached IESG approval on the Standards Track and continues to be maintained as of this writing. Even though classical ECDH alone falls to a quantum computer (see below), the hybrid construction gives the ecosystem a practical way to stay secure through the transition.

Summary

DH key exchange has anchored public-key cryptography for half a century and still powers TLS, SSH, and Signal. Key takeaways:

• The shared secret \(K = g^{ab} \bmod p\) follows from exponent commutativity — an elegant structure.
• Security rests on the discrete logarithm problem plus CDH/DDH assumptions.
• Choose a safe prime \(p = 2q + 1\) and a generator of order \(q\) to defeat small-subgroup attacks.
• DH alone is MITM-vulnerable; combine with RSA or ECDSA signatures for authentication.
• Implementations rely on binary exponentiation ; accelerate with pow(g, a, p) or gmpy2.powmod.
• For production, use cryptography.hazmat’s dh module and derive keys with HKDF-SHA256.
• The modern default is ECDH, especially X25519, and the field is migrating to hybrid PQC schemes.

To fully grasp DH you need to cross-reference RSA , ElGamal , elliptic curves, KDFs, and PKI. Pick your next topic from the Cryptography Roadmap .

Related Articles

• RSA Encryption Theory, Key Generation, Encryption, and Decryption in Python - Public-key cryptosystem based on integer factorization.
• Understanding SSH Key Exchange Through Diffie-Hellman and Elliptic Curve Cryptography - Shows how diffie-hellman-group-exchange-sha256 maps this article’s DH onto a real protocol, implementing KEXINIT negotiation through session key derivation.
• Diffie-Hellman Key Exchange Protocol: Theory and Python Implementation - The introductory DH article, good for forward secrecy basics.
• Post-Quantum Cryptography in Python: Learning With Errors (LWE) and Regev Encryption - Explains why this article’s discrete-log problem is broken by Shor’s algorithm on a quantum computer.
• Fast Modular Exponentiation Using Binary Exponentiation in Python - The \(O(\log k)\) algorithm that powers DH and RSA.
• Elliptic Curve Cryptography (ECC) in Python - The mathematical foundation of ECDH / X25519: point addition, scalar multiplication, ECDLP, and the major curves compared.
• AES and ChaCha20 in Python - What actually consumes the DH-derived session key: AES-GCM / ChaCha20-Poly1305 AEAD and nonce management in depth.
• Digital Signatures (ECDSA / EdDSA / RSA-PSS) in Python - The authentication layer that defeats DH’s MITM problem; TLS 1.3 combines (EC)DHE with signatures for authenticated key exchange.
• Elliptic Curve ElGamal Encryption: Principles and Simplified Python Implementation - Public-key encryption over elliptic-curve DLP, the cousin of ECDH.
• Cryptography Roadmap: DLP, Factorization, Elliptic Curves to PQC - Birds-eye view of the cryptography space.
• OAuth 2.0 and OpenID Connect: Fundamentals - Real-world protocols built on DH/RSA.
• Zero Trust Architecture: Principles, Components, and Implementation - How DH/PKI plug into organization-level security.
• Security Certification Comparison: CISSP vs Japan’s Registered Information Security Specialist - Certifications whose scope covers DH and modern cryptography.

Related Tools

• Hash Generator (DevToolBox) - SHA-256/SHA-512 helpers for KDF tinkering
• Number Base Converter (CalcBox) - Convert large integers to hex when inspecting DH parameters

References

• Diffie, W., & Hellman, M. (1976). “New Directions in Cryptography”. IEEE Transactions on Information Theory, 22(6), 644–654.
• Kivinen, T., & Kojo, M. (2003). “More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE)”. RFC 3526.
• Gillmor, D. K. (2016). “Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS”. RFC 7919.
• Adrian, D., et al. (2015). “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (Logjam attack). CCS 2015.
• Bernstein, D. J. (2006). “Curve25519: new Diffie-Hellman speed records”. PKC 2006.
• Marlinspike, M., & Perrin, T. (2016). “The X3DH Key Agreement Protocol”. Signal Foundation.
• Kwiatkowski, K., Kampanakis, P., Westerbaan, B., & Stebila, D. “Post-quantum hybrid ECDHE-MLKEM Key Agreement for TLSv1.3”. IETF TLS Working Group, draft-ietf-tls-ecdhe-mlkem (Standards Track). https://datatracker.ietf.org/doc/draft-ietf-tls-ecdhe-mlkem/
• The Register (2023). “Google adds post-quantum encryption key protection to Chrome” — Chrome 116 enabling X25519Kyber768Draft00 by default (August 2023). https://www.theregister.com/2023/08/12/google_chrome_kem/