\Question{RSA with Three Primes}
Show how you can modify the RSA encryption method to work with three primes instead of two primes (i.e.\ $N=pqr$ where $p, q, r$ are all prime), and prove the scheme you come up with works in the sense that $D(E(x)) \equiv x \pmod N$.
\Question{Breaking RSA}
\begin{Parts}
\Part 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{Squared RSA}
\begin{Parts}
\Part Prove the identity $a^{p(p-1)} \equiv 1 \pmod{p^2}$, where $a$ is relatively prime to $p$ and $p$ is prime.
\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, i.e.\ $x^{ed} \equiv x \pmod{N}$. You may assume that $x$ is relatively prime to both $p$ and $q$.
\Part Continuing the previous part, prove that the scheme is unbreakable, i.e.\ your scheme is at least as difficult as ordinary RSA.
\end{Parts}
\Question{Badly Chosen Public Key}
Your friend would like to send you a message using the RSA public key $N = (pq, e)$.
Unfortunately, your friend did not take CS 70, so your friend mistakenly chose $e$ which is \textit{not} relatively prime to $(p-1)(q-1)$.
Your friend then sends you a message $y = x^e$.
In this problem we will investigate if it is possible to recover the original message $x$.
Throughout this problem, assume that you have discovered an integer $a$ which has the property that $a^{(p-1)(q-1)} \equiv 1 \pmod N$, and for any positive integer $k$ where $1 \le k < (p-1)(q-1)$, $a^k \not\equiv 1 \pmod N$.
\begin{Parts}
\Part Show that for any integer $z$ which is relatively prime to $N$, $z$ can be written as $a^k \pmod N$ for some integer $0 \le k < (p-1)(q-1)$.
[\textit{Hint}: Show that $1, a, a^2, \dotsc, a^{(p-1)(q-1)-1}$ are all distinct modulo $N$.]
\Part Show that if $k$ is any integer such that $a^k \equiv 1 \pmod N$, then $(p-1)(q-1) \mid k$.
\Part Assume that $y$ is relatively prime to $N$.
By the first part, we can write $y \equiv a^\ell \pmod N$ for some $\ell \in \{0, \dotsc, (p-1)(q-1)-1\}$.
Show that if $k$ is an integer such that $(p-1)(q-1) \mid ek - \ell$, then $\tilde{x} := a^k$ satisfies $\tilde{x}^e \equiv y \pmod N$.
\Part Unfortunately the solution $\tilde{x}$ found in the previous part might not be the original solution $x$.
Show that if $d := \gcd(e, (p-1)(q-1)) > 1$, then there are exactly $d$ distinct integers $x_1, \dotsc, x_d$ which are all distinct modulo $N$ such that $x_i^e = y$, $i = 1,\dotsc, d$.
[\textit{Hint}: You will probably find it helpful to use $a$ as a tool here.]
\end{Parts}
\Question{Properties of $\GF(p)$}
\begin{Parts}
\Part Show that, if $p(x)$ and $q(x)$ are polynomials over the
reals (or complex, or rationals) and $p(x)\cdot q(x) = 0$ for all
$x$, then either $p(x)=0$ for all $x$ or $q(x)=0$ for all $x$ or both.
(\textit{Hint}: You may want to prove first this lemma, true in all fields:
The roots of $p(x)\cdot q(x)$ is the union of the roots of $p(x)$ and $q(x)$.)
\nosolspace{2cm}
\Part Show that the claim in part (a) is false for finite fields $\GF(p)$.
\nosolspace{1cm}
\end{Parts}
\Question{Repeated Roots}
Let $p(x) = a_k x^k + \cdots + a_0$ be a polynomial in the variable $x$, where $k$ is a positive integer and the coefficients $a_0, \dotsc, a_k$ are from some field $F$ (here, $F$ can be $\Q$, $\R$, $\C$, or $\GF(p)$ for some prime $p$).
We formally define the polynomial's \textbf{derivative} to be the polynomial $p'(x) := ka_k x^{k-1} + \cdots + a_1 = \sum_{j=1}^k ja_j x^{j-1}$.
[Note: You may be familiar with the derivatives of polynomials from studying calculus, but we are not using any calculus here, because it does not really make sense to perform calculus on finite fields!
Think of the polynomial's derivative as a formal definition, i.e., in this context, it has nothing to do with rate of change, etc.
In particular, you should not use any calculus rules such as the product rule without proof.]
We say that $\alpha$ is a \textbf{repeated root of $p$} if $p(x)$ can be factored as $(x-\alpha)^2 q(x)$ for some polynomial $q$.
Show that $\alpha$ is a repeated root of $p$ if and only if $p(\alpha) = p'(\alpha) = 0$.