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.