# Possible to know who is the owner of a message encrypted with RSA public key

Given the scenario in which I want to send 10 messages either to Stalio or Olio. I encrypt these messages with their respective public keys using textbook RSA, before sending the messages to their recipients.

Can an attacker - by knowing only the public keys of Stalio and Olio and the 10 cipher texts - tell which of those messages is addressed to who?

• How do you "sign this messages with their public keys"? $\:$ Do you also have their private keys? $\hspace{.74 in}$ – user991 Dec 29 '14 at 20:57
• You don't need private keys, you just sign it with their public keys so that only the correct receiver can decrypt. – user20043 Dec 29 '14 at 22:28
• @Omar That's not what signatures are or how they work. – cpast Dec 29 '14 at 23:48
• My mistake in using the word signature in the question, edited it – user20043 Dec 30 '14 at 9:23
• "I sign this" $\: \mapsto \:$ "I encrypt these" $\;\;\;$ ? $\;\;\;\;\;\;\;$ – user991 Dec 30 '14 at 19:49

Yes, an attacker may be able to distinguish which message is send to which recipient, but it depends on the message.

Imagine the following setting: the moduli of the keys of Stalio and Olio differ (this is a requirement for RSA). The public key is set to a well known constant, say the fourth number of Fermat, 65537. Textbook RSA encryption of the number 1 will result in 1. Not very secure - you can immediately see that the encrypted number must be 1. As the ciphertext is identical regardless of the modulus, you cannot distinguish between one recipient or the other.

Now imagine encrypting a number in such a way that it wraps around for one modulus, but not for the other. In that case you can clearly distinguish that it was encrypted using the smaller or the larger modulus. As the modulus identifies the key and therefore the recipient, you can see for which recipient the message was encrypted.

Textbook RSA is not safe for general use, you need to use a padding scheme such as PKCS#1 OAEP to be secure. Moral of the story: use cryptographically secure padding for RSA (I guess we can add this one to the list, although traffic analysis is already in).