Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring

Recovers a single plaintext m that was encrypted with the *same* small public exponent e to e (or more) different recipients holding pairwise-coprime moduli n_i — by combining the ciphertexts with CRT and taking an exact integer root, without factoring any modulus.

The signal that gives it away

- The challenge hands you several `(n_i, c_i)` pairs sharing one short exponent — e = 3, 5, 7 are the classic ones — instead of a single (n, e, c) triple. Any time a challenge broadcasts data structures shaped like [(n1,c1),(n2,c2),(n3,c3),...] with one e reused across all of them, that's the tell. - Unpadded / textbook RSA: no OAEP, no random padding between the message and m^e mod n. If the source or protocol description shows raw pow(m, e, n), the attack is in play. - The count of pairs is at least `e` (k >= e). This isn't cosmetic — it's the actual precondition: since m < n_i for every recipient, m^e < n_i^e, and once you have e moduli of comparable size their product exceeds m^e, which is exactly what makes the CRT-reconstructed value equal the *true* integer m^e rather than some reduction of it. Fewer than e pairs and the product usually isn't big enough — the attack becomes unreliable or fails outright. - The moduli are (or are claimed to be) pairwise coprime — different recipients, independently generated keys. This is worth checking explicitly, not assuming (see "What does NOT work" below).

How it's exploited

1. **Combine the congruences with Chinese Remainder Theorem — recombining residues across coprime moduli. Each recipient satisfies `m^e ≡ c_i (mod n_i)`. CRT-combining the `k >= e` pairs gives `M ≡ m^e (mod ∏ n_i)`. 2. The modular value is the true integer value.** Because m^e < ∏ n_i (by the count argument above), M isn't just *a* solution mod the product — it *is* m^e as an ordinary integer. That's the whole trick: CRT turned a family of modular reductions into one un-reduced number. 3. Take the exact integer `e`-th root (same primitive used in Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n) to recover m.

```python from sympy.ntheory.modular import crt from gmpy2 import iroot

M, _ = crt([n1, n2, n3], [c1, c2, c3]) # generalize to k >= e pairs m, exact = iroot(int(M), e) assert exact # if this is False, something is wrong -- see below ```

4. Always verify by re-encrypting: all(pow(m, e, n_i) == c_i for n_i, c_i in pairs). Cheap, and it catches a bad CRT combination immediately instead of shipping a wrong-looking plaintext. 5. **If the recipients used padding that's *linear/affine* in m — i.e. each recipient actually received `f_i(m)^e` for some known `f_i(x) = a_i·x + b_i` (a per-recipient offset, a counter baked into the message, etc.) rather than raw `m^e` — plain CRT + integer root no longer applies directly, but the attack is not defeated**: this is the generalization Håstad himself showed, and it reduces to finding a common root of k related polynomials mod the (still coprime) moduli. That's a job for Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction (or, for the two-ciphertext case with a purely linear relation, the same idea underlies Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD). Don't give up at "there's padding" — check whether the padding is *structured/linear* before concluding this technique is dead.

What does NOT work

- Running CRT + root when the moduli are not actually pairwise coprime. Check gcd(n_i, n_j) for every pair *before* trusting the reconstruction — CRT's guarantees (and most library implementations) assume coprimality and will silently misbehave or throw on shared factors. If a gcd comes back non-trivial, that's a *better* bait than Håstad: it directly factors both moduli (p = gcd(n_i, n_j)), which is a different, easier win — don't force this technique when the real signal is a shared-factor slip. - Trying this with fewer than `e` ciphertext/modulus pairs. The product of the moduli generally won't exceed m^e, so the CRT-combined value is just *a* residue, not the true integer — the exact-root check will (correctly) fail. Wait for more pairs, or recognize the challenge wants a different attack (single recipient with a small m is plain Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n, not this one). - Assuming linear padding blocks the attack. It doesn't — Håstad's own extension handles exactly this case via CRT + Coppersmith. What genuinely blocks it is *randomized, non-affine* padding (proper OAEP) that makes each recipient's effective plaintext unrelated to the others' in any solvable algebraic way — that's the actual stopping condition, not "padding exists." - Skipping the `exact` check on the integer root. If iroot (or equivalent) doesn't report an exact root, don't round or truncate and move on — an inexact result means either the moduli weren't really coprime, k < e, or the plaintext isn't literally the raw integer you assumed (there's an encoding step you missed). Treat it as a signal to re-diagnose, not noise to suppress. - **Confusing this with Common Modulus Attack — same n, two coprime exponents on the same message.** They look superficially similar ("multiple ciphertexts, recover one plaintext, no factoring") but the structure is the opposite: Håstad is *one modulus per recipient, same exponent*; common-modulus is *same modulus, two different exponents*. Read which value is shared (e vs n) before picking the technique.

Related

Chinese Remainder Theorem — recombining residues across coprime moduli Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD Common Modulus Attack — same n, two coprime exponents on the same message RSA Fundamentals — the routing hub: which artifact points to which attack