CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 RSA Warm-Up
Consider an RSA scheme with modulus N = pq, where p and q are distinct prime numbers larger than 3.
(a) What is wrong with using the exponent e = 2 in an RSA public key?
(b) 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.
(c) Nowsupposethat p=5,q=17,ande=3. Whatisthepublickey?
(d) What is the private key?
(e) Alice wants to send a message x = 10 to Bob. What is the encrypted message E(x) she sends using the public key?
CS 70, Fall 2021, DIS 4B 1
(f) Suppose Bob receives the message y = 24 from Alice. What equation would he use to decrypt the message? What is the decrypted 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 (N1,e),…,(Nk,e) 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 (p1q1,7) and (p1q2,7) 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. Think of p1,q1,q2 as massive 1024-bit numbers. Assume p1,q1,q2 are all distinct and are valid primes for RSA to be carried out.
(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 (p1q1,3), (p2q2,3), and (p3q3,3) along with their transmissions. Argue why Eve cannot break the encryption in the same way as above. Assume p1,p2,p3,q1,q2,q3 are all distinct and are valid primes for RSA to be carried out.
CS 70, Fall 2021, DIS 4B 2
(c) Let’s say the secret x was not changed (e = 3), so they used the same public keys as before, but did not transmit different messages. How can Eve figure out x?
3 RSA for Concert Tickets
Alice wants to tell Bob her concert ticket number, m, which is an integer between 0 and 100 inclusive. She wants to tell Bob over an insecure channel that Eve can listen in on, but Alice does not want Eve to know her ticket number.
(a) Bob announces his public key (N = pq,e), where N is large (512 bits). Alice encrypts her message using RSA. Eve sees the encrypted message, and figures out what Alice’s ticket number is. How did she do it?
(b) Alice decides to be a bit more elaborate. She picks a random number r that is 256 bits long, so that it is too hard to guess. She encrypts that and sends it to Bob, and also computes rm, encrypts that, and sends it to Bob. Eve is aware of what Alice did, but does not know the value of r. How can she figure out m?
CS 70, Fall 2021, DIS 4B 3