Simplify each expression using Fermat’s Little Theorem.
(a) 333 (mod 11)
(b) 1000110001 (mod 17)
(c) 1010 +2020 +3030 +4040 (mod 7)
2 RSA Practice
Bob would like to receive encrypted messages from Alice via RSA.
(a) Bob chooses p= 7 and q= 11. His public key is (N,e). What is N?
(b) What number is e relatively prime to?
(c) e need not be prime itself, but what is the smallest prime number e can be? Use this value for e in all subsequent computations.
(d) What is gcd(e,(p−1)(q−1))?
(e) What is the decryption exponent d?
(f) Now imagine that Alice wants to send Bob the message 30. She applies her encryption function E to 30. What is her encrypted message?
CS 70, Fall 2018, HW 5 1
(g) Bob receives the encrypted message, and applies his decryption function D to it. What is D applied to the received message?
3 Squared RSA
(a) Prove the identity ap(p−1) ≡ 1 (mod p2), where a is coprime to p, and p is prime. (Hint: Try to mimic the proof of Fermat’s Little Theorem from the notes.)
(b) Now consider the RSA scheme: the public key is (N = p2q2,e) for primes p and q, with e relatively prime to p(p− 1)q(q− 1). The private key is d = e−1 (mod p(p− 1)q(q− 1)). Prove that the scheme is correct for x relatively prime to both p and q, i.e. xed ≡x (mod N).
(c) Prove that this scheme is at least as hard to break as normal RSA; that is, prove that if this scheme can be broken, normal RSA can be as well. We consider RSA to be broken if knowing pq allows you to deduce (p−1)(q−1). We consider squared RSA to be broken if knowing p2q2 allows you to deduce p(p−1)q(q−1).
