Simplify each expression using Fermats Little Theorem.

• 3³³ (mod 11)
• 10001¹⁰⁰⁰¹ (mod 17)
• 10¹⁰ +20²⁰ +30³⁰ +40⁴⁰ (mod 7)

2 RSA Practice

Bob would like to receive encrypted messages from Alice via RSA.

• Bob chooses p= 7 and q= His public key is (N,e). What is N?
• What number is e relatively prime to?
• 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.
• What is gcd(e,(p1)(q1))?
• What is the decryption exponent d?
• 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

• Bob receives the encrypted message, and applies his decryption function D to it. What is D applied to the received message?

3 Squared RSA

• Prove the identity a^p(p1) 1 (mod p²), where a is coprime to p, and p is prime. (Hint: Try to mimic the proof of Fermats Little Theorem from the notes.)
• Now consider the RSA scheme: the public key is (N = p²q²,e) for primes p and q, with e relatively prime to p(p 1)q(q 1). The private key is d = e¹ (mod p(p 1)q(q 1)). Prove that the scheme is correct for x relatively prime to both p and q, i.e. x^ed x (mod N).
• 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 (p1)(q1). We consider squared RSA to be broken if knowing p²q² allows you to deduce p(p1)q(q1).