\Question{Quick Computes}
Simplify each expression using Fermat's Little Theorem.
\begin{Parts}
\Part $3^{33} \pmod{11}$
\Part $10001^{10001} \pmod{17}$
\Part $10^{10} + 20^{20} + 30^{30} + 40^{40} \pmod{7}$
\end{Parts}
\Question{RSA Practice}
Bob would like to receive encrypted messages from Alice via RSA.
\begin{Parts}
\Part Bob chooses $p = 7$ and $q = 11$. His public key is $(N,e)$.
What is $N$?
\nosolspace{1cm}
\Part What number is $e$ relatively prime to?
\nosolspace{1cm}
\Part $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.
\nosolspace{1cm}
\Part What is $\gcd(e,(p-1)(q-1))$?
\nosolspace{1cm}
\Part What is the decryption exponent $d$?
\nosolspace{1cm}
\Part Now imagine that Alice wants to send Bob the message $30$. She applies her encryption function $E$ to $30$. What is her encrypted message?
\nosolspace{1cm}
\Part Bob receives the encrypted message, and applies his decryption function $D$ to it.
What is $D$ applied to the received message?
\nosolspace{1cm}
\end{Parts}
\Question{Squared RSA}
\begin{Parts}
\Part Prove the identity $a^{p(p - 1)} \equiv 1 \pmod{p^2}$, where $a$ is coprime to $p$, and $p$ is prime. (Hint: Try to mimic the proof of Fermat's Little Theorem from the notes.)
\Part Now consider the RSA scheme: the public key is $(N = p^2 q^2, e)$ for primes $p$ and $q$, with $e$ relatively prime to $p(p-1)q(q-1)$. The private key is $d = e^{-1} \pmod{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} \equiv x \pmod{N}$.
\Part 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^2q^2$ allows you to deduce $p(p - 1)q(q - 1)$.
\end{Parts}