[SOLVED] CS70 Homework5

Simplify each expression using Fermat’s 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,(p−1)(q−1))?
• 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(p−1) ≡ 1 (mod p²), where a is coprime to p, and p is prime. (Hint: Try to mimic the proof of Fermat’s 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 (p−1)(q−1). We consider squared RSA to be broken if knowing p²q² allows you to deduce p(p−1)q(q−1).