Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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).

share|improve this answer
The attack Henrick refers to is called Håstad's broadcast attack. See for instance here. Interestingly, this attack also applies when using weak (linear) padding. Using random padding and larger public exponents in RSA ($e=2^{16}+1$ as it is common) renders these attacks useless in practice. – DrLecter Oct 25 '13 at 10:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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