THE GARDEN

Hastad's Broadcast Attack

Updated 19 Sep 2026

• •

  What it is

  • •

    If the same message is encrypted with a small public exponent $e$ (classically 3) under $e$ or more different moduli (e.g. broadcasting the same message to several recipients, each with their own RSA key), an eavesdropper who collects all the ciphertexts can recover the plaintext without factoring anything or knowing any private key. Since $m < N_i$ for every modulus, $m^e$ is smaller than the product of any $e$ of the moduli — so combining the $e$ congruences $c_i \equiv m^e \pmod {N_i}$ via the Chinese Remainder Theorem recovers $m^e$ exactly, over the integers, with no modular wraparound left to resolve; a plain integer $e$-th root then gives $m$ directly.

• •

  When to apply

  • •

    The same plaintext (or a message with a fixed, guessable format) is encrypted with a small, fixed exponent across at least $e$ distinct moduli, and you have the ciphertext and modulus for each.

• •

  Math

  • •

    For $e$ ciphertexts $c_i \equiv m^e \pmod{N_i}$ (pairwise coprime moduli), CRT gives a unique $C \equiv m^e \pmod{\prod N_i}$; since $m^e < \prod_{i=1}^{e} N_i$ (as $m < N_i$ for all $i$), $C = m^e$ exactly as integers, so $m = \sqrt[e]{C}$.

• •

  Worked example

  • •

    Encrypt $m=42$ with $e=3$ under pairwise-coprime $N_1=55$, $N_2=391$, and $N_3=1189$. The ciphertexts are $3$, $189$, and $370$. CRT reconstructs $42^3=74088$ because it is smaller than $N_1N_2N_3$; the exact integer cube root returns $42$.

• •

  Python

  • •

    def crt_pair(a1, n1, a2, n2):
            k = (a2 - a1) % n2
            t = (k * pow(n1 % n2, -1, n2)) % n2
            return a1 + t*n1, n1*n2
    
    def crt_many(residues, moduli):
            x, mod = residues[0], moduli[0]
            for a, n in zip(residues[1:], moduli[1:]):
                x, mod = crt_pair(x, mod, a, n)
            return x, mod
    
    C, _ = crt_many([c1, c2, c3], [n1, n2, n3])
    from gmpy2 import iroot
    m, exact = iroot(C, 3)   # exact will be True if it really was a broadcast
    

• •

  SageMath

  • •

    crt([c1,c2,c3], [n1,n2,n3]) handles the combination step in one call, and Integer(C).nth_root(3, truncate_mode=True) handles the root — tidier syntax, same underlying approach as the Python version.

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Chinese Remainder Theorem

  • •

    Low-Exponent Cube-Root Attack (Unpadded RSA)

◌ Explore connections in Graph view