\Question{Squared RSA} \begin{Parts} \Part (5 points) 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 (10 points) 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} \Question{Breaking RSA (15 points)} %\begin{Parts} Eve is not convinced she needs to factor $N = pq$ in order to break RSA. She argues: "All I need to know is $(p-1)(q-1)$... then I can find $d$ as the inverse of $e$ mod $(p-1)(q-1)$. This should be easier than factoring $N$." Prove Eve wrong, by showing that if she knows $(p-1)(q-1)$, she can easily factor $N$ (thus showing finding $(p-1)(q-1)$ is at least as hard as factoring $N$). Assume Eve has a friend Wolfram, who can easily return the roots of polynomials over $\R$ (this is, in fact, easy). % \Part When working with RSA, it is not uncommon to use $e=3$ in the public % key. Suppose that Alice has sent Bob, Carol, and Dorothy the same % message indicating the time she is having her birthday party. Eve, who is % not invited, wants to decrypt the message and show up to the % party. % Bob, Carol, and Dorothy have public keys $(N_1, e_1), (N_2, e_2), (N_3, % e_3)$ respectively, where $e_1=e_2=e_3=3$. Furthermore assume that $N_1,N_2,N_3$ are % all different. Alice has chosen a number $0\leq x< \min\{N_1,N_2,N_3\}$ which % indicates the time her party starts and has encoded it via the three % public keys and sent it to her three friends. Eve has been able to % obtain the three encoded messages. Prove that Eve can figure out $x$. % First solve the problem when two of $N_1,N_2,N_3$ have a % common factor. Then solve it when no two of them have a common factor. % Again, assume Eve is friends with Wolfram as above. % % % \textit{Hint}: The concept behind this problem is the Chinese Remainder Theorem: % Suppose $n_1, ...,n_k$ are positive integers, that are pairwise co-prime. % Then, for any given sequence of integers $a_1, ..., a_k$, there exists an % integer $x$ solving the following system of simultaneous congruences: % \begin{align*} % x &\equiv a_1 \pmod{n_1} \\ % x &\equiv a_2 \pmod{n_2} \\ % &\vdots \\ % x &\equiv a_k \pmod{n_k} % \end{align*} % Furthermore, all solutions $x$ of the system are congruent modulo % the product, $N=n_1 \dotsm n_k$. Hence: % $x \equiv y \pmod{n_i} \text{ for } 1 \leq i \leq k \iff % x \equiv y \pmod N$. %\end{Parts} \Question{Polynomial Practice} \begin{Parts} \Part If $f$ and $g$ are non-zero real polynomials, how many roots do the following polynomials have at least? How many can they have at most? (Your answer may depend on the degrees of $f$ and $g$.) \begin{enumerate}[(i)] \item (2 points) $f + g$ \item (2 points) $f\cdot g$ \item (2 points) $f/g$, assuming that $f/g$ is a polynomial \end{enumerate} \Part Now let $f$ and $g$ be polynomials over $\mathrm{GF}(p)$. \begin{enumerate}[(i)] \item (3 points) We say a polynomial $f = 0$ if $$\forall x, f(x) = 0$$. If $f\cdot g = 0$, is it true that either $f=0$ or $g=0$? \item (3 points) If $\deg{f} \geq p$, show that there exists a polynomial $h$ with $\deg{h} < p$ such that $f(x) = h(x)$ for all $x \in \{0,1,...,p-1\}$. \item (3 points) How many $f$ of degree \textit{exactly} $d 0$.]\\ (Hint: Try to relate it to something we know that's countable, such as $\Q \times \Q$) \nosolspace{2cm} \Part (5 points) Is a set of circles in $\R^2$ such that no two circles overlap necessarily countable or possibly uncountable? [\textit{Hint}: A circle is a subset of the plane of the form $\{(x, y) \in \R^2 : (x - x_0)^2 + (y - y_0)^2 = r^2\}$ for some $x_0, y_0, r \in \R$, $r > 0$. The difference between a circle and a disk is that a disk contains all of the points in its interior, whereas a circle does not.] \nosolspace{2cm} \end{Parts}