# RSA Decryption from samples

I am working on a project for a client which involves decryption of data which was encrypted using RSA.

The system in question retains three independent copies of each data-set, but each copy is encrypted with a different key. In this scenario, all of the private keys are gone and i want to know if anyone knows of a methodology to use the three encrypted copies of the data (which are identical - no padding) to determine the original data-set.

Any help/thoughts/comments would be appreciated.

• What's the public exponent? If e=3 decryption is simple (see Watson's answer). If e is bigger than the number of copies, this attack shouldn't work. But lack of proper padding (preferably OAEP) is still a very bad idea. – CodesInChaos Mar 16 '15 at 14:45
• See Dan Boneh - Twenty Years of Attacks on the RSA Cryptosystem Section 4.2 Hastad's Broadcast Attack. – CodesInChaos Mar 16 '15 at 15:26

Using the Chinese Remainder Theorem I can compute $M^3$, and then take the cube root. This is why multiple recipient RSA is insecure.