Chinese Remainder Theorem — recombining residues across coprime moduli

CRT reconstructs a unique value x mod N (with N = ∏ nᵢ) from a set of residues x ≡ aᵢ (mod nᵢ), provided the moduli nᵢ are pairwise coprime — it's the combination step, not the attack itself, behind several unrelated-looking exploits.

The signal that gives it away

CRT itself is rarely "the vulnerability" — it's the tool you reach for once you already have several congruences on the *same* unknown and need to fuse them back into one number. Recognize the setup by what you're holding, not by a single artifact size:

- The same secret shows up reduced under several different, coprime moduli — e.g. one plaintext broadcast to multiple recipients each with their own RSA n (see Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring). - A hard problem has been split by structure into several easier sub-problems whose moduli are coprime, and you now need to stitch the partial answers back together — e.g. a discrete log solved independently mod each prime-power factor of the group order (see Pohlig-Hellman — solving the discrete log when the group order is smooth). - A fault or side-channel gives you the *same* secret computation evaluated correctly under one modulus and incorrectly under a related one — the discrepancy itself factors a modulus rather than needing CRT to combine, but CRT-style residue reasoning is how you notice it.

How to exploit

Direct, library-backed combination (this is what you actually run in practice, not the manual formula): ``python from sympy.ntheory.modular import crt x, N = crt([n1, n2, n3], [a1, a2, a3]) # x mod N, N = n1*n2*n3 ` Manual two-modulus step (Garner's method), useful when you need to combine incrementally or the library isn't available: `python def crt2(a1, n1, a2, n2): # x ≡ a1 (mod n1), x ≡ a2 (mod n2); n1, n2 coprime m = pow(n1, -1, n2) x = a1 + n1 * ((a2 - a1) * m % n2) return x % (n1 * n2) ` Fold in more moduli by repeating the two-modulus step pairwise, or hand the whole list to sympy.crt / Sage's CRT_list` at once.

Concrete uses worth knowing cold: - Håstad's broadcast attack: combine k = e ciphertexts cᵢ = mᵉ mod nᵢ (coprime nᵢ) via CRT to get mᵉ mod ∏nᵢ. Because m < min(nᵢ) implies mᵉ < ∏nᵢ when you have at least e moduli, the CRT result is the *exact integer* mᵉ, not just a residue — so an integer e-th root recovers m directly, no factoring needed. Details of the padding/consistency variants live in Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring. - Pohlig-Hellman: solve the discrete log independently mod each prime-power factor pᵢ^eᵢ of the group order, then CRT-recombine the partial logs xᵢ = x mod pᵢ^eᵢ into x mod n. See Pohlig-Hellman — solving the discrete log when the group order is smooth for the per-factor solving step. - CRT-RSA speedups and their fault-attack fallout: legitimate RSA-CRT decryption computes the result mod p and mod q separately then CRT-combines for a 4x speedup — the same structure that, if one of the two branches is faulted, lets an attacker skip CRT entirely and instead take gcd(faulty_sig - correct_sig, n) to factor n (see Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright). - General moduli-splitting triage: whenever a problem's modulus (or group order) factors into coprime pieces, CRT is *why* solving each piece separately and recombining is valid at all — it's the justification, not just a formula, for the entire "split, solve small, recombine" pattern that recurs across Integer Factorization Methodology — which factoring attack to try, in what order-adjacent triage.

Always verify pairwise coprimality of the moduli before trusting the result — math.gcd on every pair, or at minimum on the product structure, before calling crt().

What does NOT work

- Feeding CRT moduli that aren't actually pairwise coprime and trusting the output. Standard CRT (and sympy.crt) assumes coprimality; if two moduli share a factor d = gcd(nᵢ, nⱼ) > 1, the naive combination either fails outright or silently returns a wrong/non-unique answer. When you find this, the *shared gcd* is the real find — it factors one of the moduli directly (this is a factoring win, not a CRT problem to route around; see Integer Factorization Methodology — which factoring attack to try, in what order). Check coprimality first, every time; don't assume a CTF hands you clean coprime moduli by default. - Reaching for the generalized (non-coprime) consistency form as a first move. The generalized CRT — a solution exists iff gcd(nᵢ, nⱼ) divides aᵢ − aⱼ for every pair, and the combined result is unique only mod lcm(nᵢ) rather than mod the full product — is real and occasionally needed, but defaulting to it hides the much more useful signal that shared factors usually mean the challenge wants you to factor a modulus, not merely combine congruences. - Treating CRT as the attack itself. It never leaks a secret on its own — it only recombines residues you must already have from some other step (broadcast ciphertexts, per-subgroup discrete logs, split fault outputs). If you don't yet have several genuine congruences on the same unknown, CRT has nothing to do yet; go get the residues first via the actual attack (Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring, Pohlig-Hellman — solving the discrete log when the group order is smooth, Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright).

Related

Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring Pohlig-Hellman — solving the discrete log when the group order is smooth Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright Integer Factorization Methodology — which factoring attack to try, in what order Primality Testing — confirming a number is prime without factoring it