Question

4. Suppose Alec wishes to communicate with Diego, who is using RSA with a public key (e, n) and corresponding private key d. Alec takes his message m and sends c m mod n to Diego. Unfortunately, Eve is able to intercept Alec's message, modifying it to instead send d'c() mod n for some (secret) r that Eve chooses. (a) Diego receives Alec's tampered ciphertext d' and tries to decrypt it using his private key d. What is the resulting decrypted message m', in terms of m and r? Is Diego likely to be able to make any sense of his message? (b) In an effort to figure out what happened, Diego tweets the value of m to Alec. Eve, of course, is able to eavesdrop on this communication and thus also learns m'. How can Eve use this information to recover Alec's original message m? How should Eve have chosen r at the beginning so that this is possible? c) Suppose that Alec also has an RSA public key (eA,nA) and that Diego knows this key. How can Alec and Diego modify their protocol so that Diego is able to verify that Alec's messages really did come from Alec, and that the message was not tampered with mid-transmission?