### Small exponent attack on RSA

Is RSA secure if the private exponent is small''? Not if you send the same message to many people, even if you use different public bases for each message. This is called Hastad's broadcast attack''.

Suppose that the exponent is small, for example, . Let the private keys be , , , where each is a product of two large secret primes, and where the message satisfies . Assume that are pairwise relatively prime. Suppose that you send the same RSA encrypted message to people. The idea is very simple. Assume (mod ) is intercepted, as is (mod ) and also (mod ). (This assumption is a standard hypothesis when constructing an attack, since the encrypted messages are presumably traveling in the open). The Chinese remainder theorem allows one to determine (mod ). But since , , we must have . Thus, really is just . So take the cube root, and you have the message.

david joyner 2008-04-20