Hastad broadcast attack on RSA
Recover a message sent to several recipients under a small public exponent, using the Chinese remainder theorem and an exact integer root.
Open in ctfpalSend the same message to e different people, each with their own modulus but all using public exponent e, and you have leaked it. With e = 3 and three ciphertexts, the Chinese remainder theorem reconstructs m^3 modulo n1*n2*n3. Because m is smaller than any single modulus, m^3 is smaller than the product - so the CRT result is m^3 as an ordinary integer, and an exact cube root finishes it.
The mechanics
# Given (c1, n1), (c2, n2), (c3, n3) with e = 3
x = crt([c1, c2, c3], [n1, n2, n3]) # x = m^3 mod n1*n2*n3
m = integer_nth_root(x, 3) # exact root - no modular arithmetic
assert m ** 3 == xThe requirement is exactly e ciphertexts under pairwise-coprime moduli. With e = 3 you need three; with e = 5, five. Fewer than that and the CRT result wraps around, the root is not exact, and the attack fails - which is the correct diagnostic if integer_nth_root returns something that does not cube back.
Part of a module
5. RSA and the parameters that break it
Work the RSA decision tree - small modulus, close primes, tiny exponent, shared modulus - and learn to read a key for its weakness.
Practise on real challenges
Go deeper
- The RSA attack decision treeRSA challenges are not solved by knowing every attack - they are solved by reading the parameters and picking the one attack that matches. A decision tree from e and n to Fermat, Wiener, Hastad, common modulus, and the oracle attacks.
Related tools
RSA common modulus attack
Recover a plaintext encrypted twice under the same modulus with two coprime exponents, using the extended Euclidean algorithm. No factoring needed.
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.