\documentclass[12pt]{article}
\usepackage{light}

\hidesolutions
%\showsolutions

\begin{document}

\recitation{7}{February 25, 2005}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{RSA}

\insolutions{
In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a
highly secure cryptosystem (called \textbf{RSA}) based on number
theory.  Despite decades of attack, no significant weakness has been
found.  (Well, none that you and me would know\dots) Moreover, RSA has
a major advantage over traditional codes: the sender and receiver of
an encrypted message need not meet beforehand to agree on a secret
key.  Rather, the receiver has both a 
\term{secret key}, which she guards closely, and a \term{public key},
which she distributes as widely as possible.  To send her a message,
one encrypts using her widely-distributed public key.  Then she
decrypts the message using her closely-held private key.  The use of
such a \term{public key cryptography} system allows you and Amazon,
for example, to engage in a secure transaction without meeting up
beforehand in a dark alley to exchange a key.
}

\vfill
\textbox{
\begin{center}
RSA Public-Key Encryption
\end{center}

\begin{description}

\item[Beforehand] The receiver creates a public key and a secret key
as follows.

\begin{enumerate}

\item Generate two distinct primes, $p$ and $q$.

\item Let $n = pq$.

\item Select an integer $e$ such that $\gcd(e, (p-1)(q-1)) = 1$.\\ The
{\em public key} is the pair $(e, n)$.  This should be distributed
widely.

\item Compute $d$ such that $de \equiv 1 \pmod{(p-1)(q-1)}$.\\ The
{\em secret key} is the pair $(d, n)$.  This should be kept hidden!

\end{enumerate}

\item[Encoding] The sender encrypts message $m$ to produce $m^\prime$ using
the public key:

\[
m' = m^e \rem n.
\]

\item[Decoding] The receiver decrypts message $m'$ back to message $m$
using the secret key:
\[
m = (m')^d \rem n.
\]

\end{description}
}
\vfill\mbox{}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Let's try it out!}
You'll probably need extra paper.  \textit{Check your work carefully!}
\begin{itemize}

\item 
As a team, go through the \textbf{beforehand} steps.
\begin{itemize}

\item
Choose primes $p$ and $q$ to be relatively small, say in the
range 10-20.  In practice, $p$ and $q$ might contain several hundred
digits, but small numbers are easier to handle with pencil and paper.

\item
Try $e = 3, 5, 7, \ldots$ until you find something that works.
Use Euclid's algorithm to compute the gcd.

\item
Find $d$ using the Pulverizer. 
\instatements{(You don't remember it? Check the last page.)}

\end{itemize}
When you're done, put your public key on the board.  This lets another
team send you a message.

\item 
Now send an encrypted message to another team using their
public key.  Select your message $m$ from the codebook below:
\begin{itemize}

\item[] 2 = Greetings and salutations!

\item[] 3 = Yo, wassup?

\item[] 4 = You guys suck!

\item[] 5 = All your base are belong to us.

\item[] 6 = Someone on {\em our} team thinks someone on {\em
your} team is kinda cute.

\item[] 7 = You {\em are} the weakest link.  Goodbye.

\end{itemize}

\item 
Decrypt the message sent to you and verify that you received
what the other team sent!

\item 
Explain how you could read messages encrypted with RSA if you
could quickly factor large numbers.

\solution{Suppose you see a public key $(e, n)$.  If you can factor $n$
to obtain $p$ and $q$, then you can compute $d$ using the Pulverizer.
This gives you the secret key $(d, n)$, and so you can decode
messages as well as the inteded recipient.}

\end{itemize}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{But does it really work?}
A critical question is whether decrypting an encrypted message always
gives back the original message!  Mathematically, this amounts to
asking whether:
\[
m^{de} \equiv m \pmod{pq}.
\]
Note that the procedure ensures that $de = 1 + k (p - 1)(q - 1)$ for
some integer $k$.
\begin{itemize}

% \item Use Euler's Theorem to prove that $m^{de} \equiv m \pmod{pq}$
% for all messages $m$ relatively prime to $pq$.  In practice, is $m$
% likely to be relatively prime to $pq$ or not?

% \solution[\vspace{2.5in}]{
% \begin{align*}
% m^{de} & = m^{1 + k (p - 1)(q - 1)} & \text{(by choice of $e$)}\\
%        & = m^{1 + k \phi(pq)} &\text{ since }\phi(pq) = (p - 1)(q - 1)\\
%        & \equiv m^{1 + k \phi(pq)} \pmod{pq} \\
%        & \equiv & m \cdot (m^{\phi(pq)})^k \pmod{pq} \\
%        & \equiv & m \cdot 1^k \pmod{pq} \\
%        & \equiv & m \pmod{pq}.
% \end{align*}

% Only one $p$th of the numbers from 0 to $pq-1$ are divisible by $p$, and
% likewise only one $q$th by $q$.  So when $p$ and $q$ are hundred-digit
% primes, the fraction of numbers relatively prime to both $p$ and $q$ is
% very close to 1, which means it is nearly certain and a random $m$ between
% 0 will be relatively prime to both $p$ and $q$.}
  
\item This congruence holds for all messages $m$.  First, use Fermat's
  theorem to prove that $m \equiv m^{de} \pmod{p}$ for all $m$.
  (Fermat's Theorem says that $a^{p-1} \equiv 1 \pmod{p}$ if $p$ is a
  prime that does not divide $a$.)

\solution[\vspace{2in}]{If $m$ is a multiple of $p$, then the claim
holds because both sides are congruent to 0 mod $p$.  Otherwise,
suppose that $m$ is not a multiple of $p$.  Then:

\begin{eqnarray*}
m^{1 + k (p-1) (q-1)}
        & \equiv &      m \cdot (m^{p-1})^{k (q-1)} \pmod{p} \\
        & \equiv &      m \cdot 1^{k (q-1)} \pmod{p} \\
        & \equiv &      m \pmod{p}
\end{eqnarray*}

The second step uses Fermat's theorem, which says that $m^{p - 1}
\equiv 1 \pmod{p}$ provided $m$ is not a multiple of $p$.
}

\item By the same argument, you can equally well show that $m \equiv
m^{ed} \pmod{q}$.  Show that these two facts together imply that $m
\equiv m^{ed} \pmod{pq}$ for all $m$.

\solution{We know that:
 \begin{align*}
p & \mid (m - m^{ed}), \\
q & \mid (m - m^{ed}).
\end{align*}
Thus, both $p$ and $q$ appear in the prime factorization of $m -
m^{ed}$.  Therefore, $pq \mid (m - m^{ed})$, and so:
\[
m  \equiv  m^{ed} \pmod{pq}.
\]
}

\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage

\mbox{}
\vfill
\textbox{
\begin{center}
I can't believe you don't remember \textbf{The Pulverizer}\dots
\end{center}
\bigskip

\noindent
Euclid's algorithm for finding the GCD of two numbers relies on
repeated application of the equation: 
\[
\gcd(a, b) = \gcd(b, a \rem b)
\]
For example, to compute the GCD of 259 and 70 we calculate:
\[
\begin{array}{rclcl}
\gcd(259, 70)
    & = & \gcd(70, 49) & \quad & \text{since $259 \rem 70 = 49$}\\
    & = & \gcd(49, 21) && \text{since $70 \rem 49 = 21$} \\
    & = & \gcd(21, 7) && \text{since $49 \rem 21 = 7$} \\
    & = & \gcd(7, 0) && \text{since $21 \rem 7 = 0$} \\
    & = & 7.
\end{array}
\]
The Pulverizer goes through the same steps, but requires some extra
bookkeeping along the way: as we compute $\gcd(a, b)$, we keep track
of how to write each of the remainders (49, 21, and 7, in the example)
as a linear combination of $a$ and $b$ (our objective is to write the
last nonzero remainder, which is the GCD, as such a linear
combination).  For our example, here is this extra bookkeeping:
\[
\begin{array}{ccccrcl}
x & \quad & y & \quad & (x \rem y) & = & x - q \cdot y \\ \hline
259 && 70 && 49 & = &   259 - 3 \cdot 70 \\
70 && 49 && 21  & = &   70 - 1 \cdot 49 \\
&&&&            & = &   70 - 1 \cdot (259 - 3 \cdot 70) \\
&&&&            & = &   -1 \cdot 259 + 4 \cdot 70 \\
49 && 21 && 7   & = &   49 - 2 \cdot 21 \\
&&&&            & = &   (259 - 3 \cdot 70) -
                                2 \cdot (-1 \cdot 259 + 4 \cdot 70) \\
&&&&            & = &   \fbox{$3 \cdot 259 - 11 \cdot 70$} \\
21 && 7 && 0
\end{array}
\]
We began by initializing two variables, $x = a$ and $y = b$.  In the
first two columns, we carried out Euclid's algorithm.  At each
step, we computed $x \rem y$, which can be written in the form $x - q
\cdot y$.  (Remember that the Division Algorithm says $x = q \cdot y +
r$, where $r$ is the remainder.  We get $r = x - q \cdot y$ by
rearranging terms.)  Then we replaced $x$ and $y$ in this equation
with equivalent linear combinations of $a$ and $b$, which we already
had computed.  After simplifying, we were left with a linear
combination of $a$ and $b$ that was equal to the remainder as desired.
The final solution is boxed.
}
\vfill
\mbox{}}

\end{document}
