The following is an important and interesting chosen ciphertext attack against RSA (i.e., plain RSA, without further precautions added). Let n = pq (where p and q are two large private primes), with public RSA key (n, e) and private key (n, d). Let m be any message, and let c = m e mod n be the corresponding ciphertext, encrypted by the receivers public key. A spy can intercept c when c is sent to the receiver. The spy would like to find the message m = c d mod n (but d is private). For an attack, the spy picks an integer r in [2, n 2] randomly, and computes x = r e c mod n , and t = r 1 mod n. The number x is the spys chosen ciphertext for the attack. Note that x will look rather random. Next, assume that the spy gets the receiver to sign x (by RSA signature with the receivers private key d); alternatively, the spy gets the receiver to decrypt x. In any case, x gets decrypted, so y = x d mod n is returned to the spy. Show how the spy can use the information now available to find m.