DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime

When a Diffie-Hellman-style modulus n is composite rather than prime, the multiplicative structure splits along its prime-power factors, so instead of one hard discrete-log problem you get several small ones — solve each and recombine with the Chinese Remainder Theorem — recombining residues across coprime moduli.

The signal that betrays it

- n is handed to you as "the modulus" (not explicitly "a prime p"), and is_prime(n) comes back False. Real DH deliberately uses a prime (often a safe prime p = 2q+1) precisely to avoid this weakness, so a composite modulus in a challenge is very rarely an oversight — it's the intended crack. - sympy.factorint(n) (or factordb) returns the factorization quickly: small primes, repeated factors (n = p^2 * q), or an RSA-shaped n = p*q with two similarly-sized primes that a Fermat/Pollard-rho pass still cracks in reasonable time. - The challenge prompt or variable names say "modulus" rather than "prime" — a small but real tell, since challenge authors who mean to hand you a safe prime almost always say so. - The order of the group you're working in (n, or something derived from it) is smooth once factored — the same smoothness signal that routes to Pohlig-Hellman — solving the discrete log when the group order is smooth, just one layer up: here it's n itself splitting, not p-1.

How it's exploited

Factor n, solve the discrete log inside each Z_{p_i^{e_i}}^* component separately, then recombine the per-component exponents with CRT:

```python from sympy import factorint, n_order, discrete_log from sympy.ntheory.modular import crt

fac = factorint(n) # n = prod p_i^e_i res, mods = [], [] for p, e in fac.items(): m = p**e x = discrete_log(m, A % m, g % m) # log of A base g, inside this component res.append(x) mods.append(n_order(g % m, m)) # the ORDER of g mod m -- not p_i, not m itself

a, _ = crt(mods, res) # recovers the exponent mod lcm(orders) ```

Each per-factor DLP is itself attacked with whatever fits its own group order: Pohlig-Hellman — solving the discrete log when the group order is smooth if that suborder is smooth, Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log if it's just small enough for meet-in-the-middle. If n = p*q looks RSA-shaped, factoring n (via Fermat when the primes are close, Pollard-rho otherwise) is the actual unlock — the composite-modulus insight only pays off once you have the factors in hand. This is structurally the same CRT-recombination move used by Pohlig-Hellman — solving the discrete log when the group order is smooth one level up (splitting by the factors of the group *order* rather than of the modulus) and by DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle (splitting a leaked exponent across repeated small-subgroup queries) — same reassembly step, different source of the residues.

What does NOT work

- Feeding the whole composite `n` straight into a generic discrete-log solver without splitting first. sympy.discrete_log and hand-rolled BSGS both assume a cyclic group; Z_n^* for a composite n with more than one prime factor is a *direct product* of the per-component groups (that's the CRT structure theorem), not cyclic overall. Running BSGS against n directly either errors out or silently returns an answer that doesn't satisfy g^x ≡ A mod n — always split by factor first. - Treating "composite modulus" as sufficient on its own. It's necessary, not sufficient. If one prime-power component p_i^{e_i} has a large, non-smooth group order, that component's DLP is exactly as hard as an ordinary prime-modulus discrete log — you still need Pohlig-Hellman — solving the discrete log when the group order is smooth or Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure for it. Composite-modulus recognition only helps if *every* resulting component is individually tractable. - Expecting `factordb`/Pollard-rho to save you against a genuine hard semiprime. If n = p*q with p and q both large and not close together, factoring n is exactly as hard as breaking RSA — this degenerates into general Integer Factorization Methodology — which factoring attack to try, in what order, not a shortcut. Don't burn time assuming every "composite n" in a challenge is secretly weak; check factorint actually returns something in reasonable time before committing to this path. - CRT-recombining on the wrong moduli. The classic slip: passing the prime factors p_i (or the raw p_i^{e_i}) to crt() instead of the *order of g* inside each component. The exponent lives mod the order of the group element, not mod the modulus — get this wrong and crt() returns a value that silently fails to satisfy the original equation, with no error to flag it. - Ignoring degenerate components. Small or repeated factors (n divisible by 2, or p^2 terms) can make a component's group order 1 or otherwise degenerate, g a non-generator there, or the "discrete log" trivially 0 regardless of A. Check n_order per component before trusting the result you recombine — a degenerate residue contributes no information and can corrupt the CRT reconstruction if treated as if it were real signal.

Related

Chinese Remainder Theorem — recombining residues across coprime moduli Pohlig-Hellman — solving the discrete log when the group order is smooth Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log Discrete Logarithm — the factorization of the group order picks your algorithm Integer Factorization Methodology — which factoring attack to try, in what order Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery Diffie-Hellman Fundamentals — what to audit first in any DH challenge DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle