\Question{Count and Prove}
\begin{Parts}
\Part
Over 1000 students walked out of class and marched to protest the war. To count the exact number of students protesting, the chief organizer lined the students up in columns of different length. If the students are arranged in columns of 3, 5, and 7, then 2, 3, and 4 people are left out, respectively. What is the minimum number of students present? Solve it with Chinese Remainder Theorem.
\Part
Prove that for $n\geq 1$, if $935 = 5 \times 11 \times 17$ divides $n^{80} -1$, then $5$, $11$, and $17$ do not divide $n$.
\end{Parts}
\Question{RSA Lite}
Woody misunderstood how to use RSA.
So he selected prime $P = 101$ and encryption
exponent $e = 67$, and encrypted his message $m$ to get $35 = m^e \bmod P$.
Unfortunately he forgot his original message $m$
and only stored the encrypted value $35$. But Carla thinks she
can figure out how to recover $m$ from $35 = m^e \bmod P$, with
knowledge only of $P$ and $e$. Is she right?
Can you help her figure out the message $m$? Show all your work.
\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 \bmod N$.
\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}$.
\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{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 \Leftrightarrow
x \equiv y \pmod N $.
\end{Parts}
\Question{Polynomials in Fields}
Define the sequence of polynomials by $P_0(x) = x+12$, $P_1(x) = x^2 - 5x + 5$ and $P_n(x) = x P_{n-2}(x) - P_{n-1}(x)$.
(For instance, $P_2(x) = 17x-5$ and $P_3(x) = x^3 - 5x^2 - 12x + 5$.)
\begin{Parts}
\Part Show that $P_n(7) \equiv 0 \pmod{19}$ for every $n\in \N$.
\Part Show that, for every prime $q$, if $P_{2017}(x) \not\equiv 0 \pmod{q}$, then $P_{2017}(x)$ has at most 2017 roots modulo $q$.\\
\end{Parts}