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?

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

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.