1 RSA Warm-Up
Consider an RSA scheme modulus N = pq, where p and q are distinct prime numbers larger than
3.
(a) Recall that e must be relatively prime to p−1 and q−1. Find a condition on p and q such that e = 3 is a valid exponent.
(b) Now suppose that p = 5, q = 17, and e = 3. What is the public key?
(c) What is the private key?
(d) Alice wants to send a message x = 10 to Bob. What is the encrypted message she sends using the public key?
(e) Suppose Bob receives the message y = 24 from Alice. What equation would he use to decrypt the message?
2 RSA with Multiple Keys
Members of a secret society know a secret word. They transmit this secret word x between each other many times, each time encrypting it with the RSA method. Eve, who is listening to all of their communications, notices that in all of the public keys they use, the exponent e is the same. Therefore the public keys used look like (e,N1),...,(e,Nk) where no two Ni’s are the same. Assume that the message is x such that 0 ≤ x < Ni for every i.
(a) Suppose Eve sees the public keys (7,35) and (7,77) as well as the corresponding transmissions. Can Eve use this knowledge to break the encryption? If so, how? Assume that Eve cannot compute prime factors efficiently.
CS 70, Fall 2018, DIS 4B 1
(b) The secret society has wised up to Eve and changed their choices of N, in addition to changing their word x. Now, Eve sees keys (3,5×23), (3,11×17), and (3,29×41) along with their transmissions. Argue why Eve cannot break the encryption in the same way as above.
3 RSA with Limited Messages
Suppose that Alice only has two possible messages she might send Bob: either “Yes” or “No”.
(a) If Alice and Bob use the standard RSA procedure, describe how Eve could find out which message Alice sent.
(b) Describe how Alice and Bob might modify the RSA procedure to stop Eve from using this exploit. (Hint: Try using a one-time pad somewhere in your procedure)
