Breaking RSA with Håstad's Broadcast Attack

Breaking RSA with Håstad’s Broadcast Attack

Introduction

A small public exponent makes RSA encryption fast. e = 3 cubes a number instead of raising it to the 65537th power. On its own, that’s not a mistake. A single recipient with e = 3 is still safe, given proper padding. Johan Håstad showed in 1988 where the real danger hides. It’s broadcasting the same message to enough recipients, all using the same small e. This post builds that attack, using nothing but the Chinese Remainder Theorem.

Table of Contents

• Why Broadcasting Breaks Low-Exponent RSA
• The Attack: Combine, Then Take a Root
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Håstad vs. This Site’s Other RSA Breakers
• Limitations of This Attack
• FAQ
• References

Why Broadcasting Breaks Low-Exponent RSA

Encrypting M with a single low-e key is just C = M^e mod n. One equation, one unknown, and no shortcut back to M without the private key. That changes the moment the same M gets encrypted under e = 3 to three recipients. Now there are three separate ciphertexts: C₁ = M³ mod n₁, C₂ = M³ mod n₂, C₃ = M³ mod n₃. All three describe the exact same unknown value.

Three congruences over three pairwise coprime moduli are exactly what the Chinese Remainder Theorem combines. It doesn’t need any of the three private keys. It needs only the public moduli and the three ciphertexts. An eavesdropper already has both. Combined, the result is a single number modulo the product of all three moduli. M³ is almost always smaller than that product, for three same-size moduli. That number isn’t just congruent to M³. It equals M³ exactly, precisely because that size condition holds. No modular wraparound is left to undo. An ordinary integer cube root finishes the job.

The version built here is the elementary special case. Identical message, pure power, nothing else. Håstad’s original 1988 result goes further. It covers whole systems of low-degree polynomial equations. It even shows that certain fixed linear paddings don’t protect against it, given enough ciphertexts. Modern treatments often pair it with Coppersmith’s theorem for stronger variants still. Those extensions sit outside what this post builds.

The Attack: Combine, Then Take a Root

Given Cᵢ = Mᵉ mod nᵢ for e recipients, with pairwise coprime moduli:

1. Confirm the moduli are pairwise coprime. gcd(nᵢ, nⱼ) = 1 for every pair. Different RSA users almost always satisfy this automatically, since their primes come from independent generation.
2. Combine via the Chinese Remainder Theorem. Find the unique C modulo N = n₁·n₂·⋯·nₑ satisfying every C ≡ Cᵢ (mod nᵢ) at once. This needs only the public moduli, standard CRT arithmetic, and no private key.
3. Recognize that C equals Mᵉ exactly. M is already smaller than the smallest modulus, true for any valid RSA plaintext. That alone isn’t quite enough. The product N also has to be large relative to Mᵉ. For similar-size moduli, that holds automatically once there are at least e of them. C isn’t just congruent to Mᵉ mod N then. It’s the literal integer Mᵉ, small enough to have never wrapped around at all.
4. Take the integer e-th root of C. An ordinary root extraction, not a modular one, recovers M directly.

No factoring, no discrete logarithm, no brute force. The entire attack is arithmetic any of the recipients’ own public keys already made available.

A Worked Example

The visualizer’s defaults broadcast M = 42 under e = 3 to three recipients. Their moduli: n₁ = 3233 (the base RSA guide’s own worked-example modulus), n₂ = 4757, and n₃ = 4897.

1. Encrypt under all three (the setup, not the attack): C₁ = 42³ mod 3233 = 2962. C₂ = 42³ mod 4757 = 2733. C₃ = 42³ mod 4897 = 633.
2. Confirm coprimality. gcd(3233, 4757) = gcd(3233, 4897) = gcd(4757, 4897) = 1. All three moduli qualify.
3. Combine via CRT. N = 3233 × 4757 × 4897 = 75312828757. Solving the three congruences gives C = 74088.
4. Check against M³. 42³ = 74088, exactly matching C. Since 74088 < 75312828757, no wraparound ever happened.
5. Take the cube root. ∛74088 = 42, the original message, recovered without any private key.

Three ciphertexts, three public moduli, and one classical theorem from number theory. That’s the whole attack.

Python Implementation

The interactive visualizer above runs this exact combination in JavaScript. Same CRT step, same integer root extraction. Here’s the same attack in Python.

Key Features

• crt implements the theorem directly, reusing the modular-inverse code from the base RSA guide’s key generation. Here it’s applied to moduli, not a totient.
• integer_root extracts an exact e-th root, not an approximate one. It uses binary search over where r^e could plausibly land. A floating-point root would silently lose precision at these sizes.
• Never touches p, q, or any private key. The entire recovery only uses e, the moduli, and the ciphertexts, all public.
• Works for any number of recipients. moduli and ciphertexts are plain lists. Nothing here is hardcoded to exactly three.

Code

# hastad_breaker.py
#
# Breaks RSA when the same message is broadcast, under the same small e,
# to enough different recipients. The Chinese Remainder Theorem combines
# the ciphertexts into M^e as an exact integer (not merely a residue),
# and an ordinary integer root recovers M. No private key, no factoring.

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        return None
    return x % m


def crt(remainders, moduli):
    N = 1
    for m in moduli:
        N *= m
    result = 0
    for r, m in zip(remainders, moduli):
        Ni = N // m
        result += r * Ni * mod_inverse(Ni, m)
    return result % N, N


def integer_root(x, e):
    if x == 0:
        return 0
    lo, hi = 0, 1
    while hi ** e <= x:
        hi *= 2
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** e <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo


def hastad_attack(e, moduli, ciphertexts):
    C, N = crt(ciphertexts, moduli)
    return integer_root(C, e)


if __name__ == '__main__':
    e = 3
    moduli = [3233, 4757, 4897]
    message = 42

    ciphertexts = [pow(message, e, n) for n in moduli]
    print(f"Ciphertexts: {ciphertexts}")

    recovered = hastad_attack(e, moduli, ciphertexts)
    print(f"Recovered message: {recovered}")
    assert recovered == message

Running this against the same values as the visualizer produces:

Ciphertexts: [2962, 2733, 633]
Recovered message: 42

This matches the visualizer’s own result exactly. It matches the worked example above, step for step.

For Fun: The Whole Attack in 2 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version trusts a floating-point cube root outright, with no integer nudge afterward.

import math
e=3; moduli=[3233,4757,4897]; M=42; c=[pow(M,e,n) for n in moduli]; N=math.prod(moduli); C=sum(r*(N//n)*pow(N//n,-1,n) for r,n in zip(c,moduli))%N; R=round(C**(1/e)); print(f"Ciphertexts: {c}\nRecovered message: {R}"); assert R==M

Verified to produce the identical Ciphertexts: [2962, 2733, 633] and Recovered message: 42. math.prod replaces the readable version’s running-product loop. round(C ** (1/e)) only works for small toy values like this one. Floating-point precision breaks down fast as C grows into hundreds of digits. The readable version’s binary search is the production-grade approach, exact at any size.

Interactive Visualizer

Try it above. Enter e and three moduli, plus a demo message. Watch the three ciphertexts combine into an exact power of M via CRT. Watch the root extraction recover the message, with no private key anywhere in the computation.

Håstad vs. This Site’s Other RSA Breakers

Håstad’s attack scales with the number of victims, not any single key’s own weakness. One low-e recipient is fine on its own. Three or more, all sent the same unpadded message, hand an eavesdropper everything they need.

Limitations of This Attack

This attack needs the exact same message, sent to at least e recipients. All of them must share the same e. Different messages give an eavesdropper nothing here, even with the same low e used everywhere.

It also assumes no randomized padding. Real-world RSA wraps the message in OAEP before raising it to any power. That randomizes each ciphertext independently, which alone defeats this entire attack. The recipients would no longer be encrypting the same underlying value at all.

Even fixed, non-random padding doesn’t fully save the scheme. Håstad’s fuller result also breaks known linear padding, like f_i(M) = a_i·M + b_i, with public a_i and b_i. It just needs more ciphertexts and a heavier version of the same idea. Only randomized padding closes that door reliably.

Finally, this implementation assumes the moduli are pairwise coprime. That’s true for any set of honestly generated RSA keys. A shared prime factor between two moduli needs the separate Fermat-style or gcd-based techniques instead.

The defense is simple: always use randomized padding such as OAEP. Never broadcast an identical, unpadded message under one small fixed e.

FAQ

Does OAEP padding actually stop this attack?

Yes, completely. OAEP folds in random padding before encryption. The same message then produces a different padded value every time. That means a different underlying number too. The three ciphertexts would no longer share the relationship this attack depends on.

How many recipients does this attack actually need?

At least e, matching the public exponent. For e = 3, three recipients suffice. A larger e needs correspondingly more recipients. Mᵉ must still lie below the product of the moduli.

Does this attack need to know M in advance?

No. It needs only the public moduli and the intercepted ciphertexts. M falls out of the CRT combination and root extraction. It’s never assumed as an input to the attack itself.

Is e = 65537, the standard modern choice, still vulnerable to this?

Not practically. M^65537 needs an enormous number of same-size recipients to drop below the product of their moduli. That’s far more than any real broadcast scenario involves. This attack is specifically a low-e problem.

Why is this called a “broadcast” attack?

Because the vulnerable scenario is inherently one-to-many: one sender, one message, several recipients. A single point-to-point message under low e is fine, as long as it’s never repeated.

References

1. Håstad, J. “Solving Simultaneous Modular Equations of Low Degree.” SIAM Journal on Computing, 1988.

2. Boneh, D. “Twenty Years of Attacks on the RSA Cryptosystem.” Notices of the AMS, 1999. Available at: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

3. Menezes, A., van Oorschot, P., and Vanstone, S. “Handbook of Applied Cryptography.” CRC Press, 1996 (Section 8.2.2, low-exponent broadcast attacks).