4. [RSA]
In this problem you are asked to hand-turn the RSA protocol to encrypt and decrypt messages (using rather smaller numbers than are used in practice, so that calculations can be done by hand). Suppose that Bob generates two primes, p = 11 and q = 23. (In reality these would be much larger numbers, with say 512 bits.) He computes the product N = pq = 253, and also selects the number e = 7, which is relatively prime to (p - 1)(q - 1) = 220. Bob then publishes the pair (N, e) as his public key.
(a) What is Bob's private key, d? [HINT: Part (c) of Problem 1 may be useful here!]
(b) Suppose that Alice wants to send the message 44 (an integer between 0 and 252) to Bob. What is the encrypted message that Alice sends? Again, show your calculation clearly.
(c) Suppose that Bob receives from Alice the encrypted message 103. What was the original message that Alice sent?
[NOTE: In this and similar problems, little or no credit will be given for numerical answers (even if they are correct) without a clear explanation of how they were derived, showing all the steps. Also, you are expected to perform your calculations in an intelligent manner, using techniques such as repeated squaring and reducing intermediate answers mod N.]