0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Mar 16 '15 at 14:45
  • $\begingroup$ See Dan Boneh - Twenty Years of Attacks on the RSA Cryptosystem Section 4.2 Hastad's Broadcast Attack. $\endgroup$ – CodesInChaos Mar 16 '15 at 15:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks guys - this gives me somewhere to start. I'm sure i will be back.. $\endgroup$ – Brian Koffler Mar 17 '15 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.