Diffie-Hellman Fundamentals — what to audit first in any DH challenge

Diffie-Hellman (DH) is a key-exchange protocol where two parties derive a shared secret over a public channel: with public parameters (p, g), Alice sends A = g^a mod p, Bob sends B = g^b mod p, and both independently compute the same shared secret s = g^{ab} mod p = A^b mod p = B^a mod p. Security rests on the Discrete Logarithm — the factorization of the group order picks your algorithm problem (recovering a from A) and the harder Computational Diffie-Hellman assumption (computing g^{ab} from A and B without either exponent).

The signal that gives it away

A DH challenge announces itself with a prime modulus p, a generator g, and one or two public values A/B sitting in the transcript — keywords like "key exchange", "shared secret", or code doing pow(g, a, p). The thing you actually need to recover is never p or g (those are public by design) — it's the private exponent (a or b) or, failing that, the shared secret g^{ab} itself, which becomes the symmetric key for whatever is layered on top (AES, a MAC, a login token).

This page is not itself an attack — it's the audit you run *before* picking one. The parameters are the whole game: a DH challenge is solved by finding which assumption the implementer forgot to enforce, not by attacking the math head-on.

How it's exploited

Run this checklist top to bottom before reaching for any heavy discrete-log machinery — each line is a cheap check that either closes off a whole attack class or hands it to you outright.

1. Is `p` actually prime, and is `p-1` smooth? Factor p-1. If it factors into small primes, the discrete log splits into small sub-problems via Pohlig-Hellman — solving the discrete log when the group order is smooth — this is very often the intended path when a challenge hand-rolls its own p instead of using a standard group. 2. What is the order of `g`? If g doesn't generate the full group (order p-1) but instead sits in a small-order subgroup — or if an attacker-supplied public value can be forced into one — the shared secret is confined to a handful of possible values and leaks via DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order. 3. Is there any leaked or partially-known exponent? If a (or b) is available from anywhere in the challenge — a debug endpoint, a side channel, a previous step of a multi-stage challenge — the secret is trivial to recover directly, no discrete-log solving needed at all:

```python from sympy import factorint

n = p - 1 print(factorint(n)) # smooth? -> Pohlig-Hellman path

# given a leaked exponent, the shared secret is one modexp away: s = pow(B, a, p) ```

Recovering an unknown exponent from scratch is exactly solving a Discrete Logarithm — the factorization of the group order picks your algorithm — which algorithm applies is picked entirely by the factorization of the group order, not by anything specific to DH itself.

Beyond this parameter triage, the same handshake opens onto a wider decision tree that this page routes into: composite modulus (DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime), the ability to tamper with p, g, or the public values in transit (DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable, DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys), a static secret exponent queried repeatedly (DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle), or an elliptic-curve variant where the interesting bugs move to point validation and scalar clamping instead (X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks). Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery is the full checklist across all of these branches; this page is only the first three lines of it.

A well-designed DH deployment closes off lines 1 and 2 by construction: using a safe prime p = 2q + 1 (with q itself prime) and a generator g of the large prime-order subgroup q leaves no small factor of p-1 to exploit and no small-order subgroup to confine into. Seeing a safe prime and a genuine full-order generator in a challenge is itself a signal — it tells you the vulnerability is deliberately *not* in the parameters, and you should stop auditing p/g and look at what else the protocol does (reuse, oracle behavior, transport tampering).

What does NOT work

- Brute-forcing `a` directly against a large safe prime with a full-order generator. With no smooth p-1 and no small subgroup to confine into, there is no shortcut here — the discrete log is exactly as hard as advertised, and grinding it head-on is a waste of the clock. Move to the next line of the checklist instead of pushing harder on this one. - Assuming every DH challenge must break at the discrete-log math. If the parameter audit comes up clean (prime p, non-smooth p-1, full-order g, no leaked exponent), the intended vulnerability is almost always somewhere else in the protocol — weak randomness, a static exponent reused across sessions, an oracle that leaks bits, or a transport layer that lets you tamper with p/g/A/B in flight. Treating "it's DH" as synonymous with "attack the discrete log" burns time that the parameter checklist would have redirected in seconds. - Skipping the smoothness/order check because `p` "looks big enough." Bit-length alone says nothing about whether p-1 is smooth or whether g has full order — a 2048-bit p with a smooth p-1 is just as breakable as a small one; the check is cheap (factorint) and has to be done regardless of how large the modulus looks.

Related

Discrete Logarithm — the factorization of the group order picks your algorithm Pohlig-Hellman — solving the discrete log when the group order is smooth DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks