As mentioned in this chapter, "textbook" RSA is subject to a forward search attack. An easy way to prevent this attack is to pad the plaintext with random bits before encrypting. This problem shows that there is another potential issue with RSA that is also prevented by padding the plaintext. Suppose that Alice's RSA public key is (N, e) and her private key is d. Bob encrypts the message M (without padding) using Alice's public key to obtain the ciphertext C = M^e (mod N). Bob sends C to Alice and, as usual, Trudy intercepts C.

a. Suppose that Alice will decrypt one message of Trudy's choosing, provided that it is not C. Show that Trudy can easily determine M. Hint: Trudy chooses r and asks Alice to decrypt the ciphertext C1 = Cr^e (mod N).

b. Why is this "attack" prevented by padding the message?