Proof of batch RSA security

Question

Suppose we have two encrypted messages with two different public key issued from the one server. There is a client who wants to send these to messages to the server.

In the middle there is an adversary, who eavesdrops all the communications, so he already got the two encryption keys and the two encrypted messages.

According to batch RSA, the adversary can recover the encrypted messages without the need to use the private key to decrypt the messages. Can anyone explain how can we prove that batch RSA is secure in such a scenario?

Answer 1

RSA public key encryption should always be used together with a randomized padding scheme, such as OAEP or PKCS#1 v1.5. Only if you don't use such padding and encrypt the same message with a sufficiently high number of different public keys, an adversary might simply apply the Chinese Remainder Theorem to the cipher texts, and then calculate the E:th root of that value (E being the public exponent used by the RSA public keys).