Recover reused DH exponents across groups

A discrete logarithm can remain hard in a group’s large prime-order component while leaking useful information through smaller components. Reusing the same secret exponent across independently chosen groups lets those partial disclosures accumulate.

Research anchor and scope

Adrian Zhang’s Strong Primes analysis examines fixed-exponent public values across multiple 2048-bit prime moduli. It checks the subgroup generated by 2, solves small projected logarithms, and accumulates residues. The prerequisite is exponent reuse; fresh independent exponents cannot be combined into one CRT system. This brief is an original explanation with a new toy example, not an adaptation of the article’s text or code; the source itself is CC BY-SA 3.0.

Derive exactly what a projection reveals

Let A = g^a mod p, and suppose r is a known prime divisor of the order of g. Raise both sides to an exponent that removes the other order factors. The result is a discrete logarithm in a subgroup of order r, giving a mod r. Verify the projected generator has the claimed order; a projection equal to one yields no information. Factoring p-1 alone is insufficient because the chosen generator may occupy a smaller subgroup.

Maintain a table of modulus, projected generator, residue, and the observation that verifies it. Solve small logs by enumeration or baby-step giant-step. Prime powers require their own handling; repeated prime factors should not be counted as independent coprime moduli. Reject inconsistent residues rather than forcing them into a candidate key.

A bounded toy example

Suppose a secret lies in [0, 1000) and observations reveal a mod 7 = 4, a mod 11 = 5, and a mod 13 = 6. These combine to a = 214 mod 1001, uniquely identifying 214 in that interval. By contrast, the first two observations alone leave candidates separated by 77. The useful measure is the combined modulus relative to the secret’s known range, not how many transcripts have been collected.

If the interval remains too large, keep the result as a congruence. A remaining search may be possible with additional constraints, but CRT itself does not identify which representative was originally sampled. Validate a candidate against public values from more than one group before deriving any shared secret.

Recognition and limits

Inspect parameter-generation code and logs for stable public-key behavior, variable moduli, and bounded exponents. A prime advertised as strong may still have exploitable smaller factors in its predecessor. A single large factor does not erase these components. This passive cross-group method differs from actively supplying malicious small-order peer keys; both rely on group structure, but their input control and observable outputs differ.