\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\newcommand{\rem}{\text{ rem }}

\begin{document}
\inclassproblems{7, Wed.}

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

\iffalse
\begin{problem}
Farmer Bill has some cows worth \$323 each and some pigs worth \$143
each.  How can he raise exactly \$50 through buying and selling
livestock?

\solution[\newpage]{Let $c$ be the number of pigs he sells, and $d$ be
the number of cows he sells.  In these terms, we are looking for
integers $c$ and $d$ such that:

\begin{eqnarray*}
323 c + 143 d & = & 50
\end{eqnarray*}

The Pulverizer give us integers $a$ and $b$ such that:

\begin{eqnarray*}
323 a + 143 b & = & \gcd(a, b)
\end{eqnarray*}

Assuming that $\gcd(a, b) \cdot k = 50$ for some integer $k$, we know
that:

\begin{eqnarray*}
(323 a + 143 b) \cdot k
    & = & \gcd(a, b) \cdot k \\
    & = & 50
\end{eqnarray*}

Setting $c = ka$ and $d = kb$ solves the problem.  All that remains is
to determine $a$, $b$, and $\gcd(a, b)$ with the Pulverizer:

\[
\begin{array}{rrcrcl}
x & y & \quad & x \rem y & = & x - q \cdot y \\ \hline
323 & 143 & \quad & 37 & = & 323 + (-2) \cdot 143 \\
143 & 37 & & 32 & = & 143 + (-3) \cdot 37 \\
    &    & &    & = & 143 + (-3) \cdot (323 + (-2) \cdot 143) \\
    &    & &    & = & (-3) \cdot 323 + 7 \cdot 143 \\
37 & 32 & & 5 & = & 37 + (-1) \cdot 32 \\
   &    & &   & = & (323 + (-2) \cdot 143) + (-1) \cdot ((-3) \cdot 323 + 7 \cdot 143) \\
   &    & &   & = & 4 \cdot 323 + (-9) \cdot 143 \\
32 & 5 & & 2 & = & 32 + (-6) \cdot 5 \\
   &   & &   & = & ((-3) \cdot 323 + 7 \cdot 143) + (-6) \cdot (4 \cdot 323 + (-9) \cdot 143) \\
   &   & &   & = & (-27) \cdot 323 + 61 \cdot 143 \\
5 & 2 & & 1 & = & 5 + (-2) \cdot 2 \\
  &   & &   & = & (4 \cdot 323 + (-9) \cdot 143) + (-2) \cdot ((-27) \cdot 323 + 61 \cdot 143) \\
  &   & &   & = & 58 \cdot 323 + (-131) \cdot 143
\end{array}
\]

Evidently, $a = 58$, $b = -131$, $\gcd(a, b) = 1$, and $k = 50 /
\gcd(a, b) = 50$.  Therefore, Farmer Bill can raise \$50 by selling
$50 a = 50 \cdot 58 = 2900$ cows and selling $50 b = 50 \cdot (-131) =
- 6550$ pigs, which is equivalent to buying 6550 pigs.  As a check,
his total proceeds are:

\begin{eqnarray*}
323 \cdot 2900 + 143 \cdot (-6550) & = & \$50
\end{eqnarray*}
}

\end{problem}
\fi

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

\begin{problem}
Let's try out RSA!  There is a complete description of the algorithm
at the bottom of the page.  You'll probably need extra paper.  {\em
Check your work carefully!}

\bparts

\ppart 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-40.  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 (see appendix for a reminder
on how the Pulverizer works).

\end{itemize}

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

\ppart 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 are slow!

\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}

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

\ppart 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 intended recipient.}

\eparts


\begin{center}
RSA Public Key Encryption
\fbox{
\begin{minipage}[t]{6in}
\vspace{0.1cm}
\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}

\vspace{0.1cm}
\end{minipage}
}
\end{center}


\end{problem}

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


\begin{problem}
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$.

\bparts

\ppart Use Euler's Theorem to prove that $m^{de} \equiv m \pmod{pq}$
for all messages $m$ relatively prime to $pq$.  
(Euler's Theorem says that if $k$ is relatively prime to $n$
then $k^{\phi(n)} \equiv 1 \pmod{n}$.) In practice, is $m$
likely to be relatively prime to $pq$ or not?

\solution[\vspace{2.5in}]{
\begin{eqnarray*}
m^{de} & \equiv & m^{1 + k \phi(pq)} \pmod{pq} \\
       & \equiv & m \cdot (m^{\phi(pq)})^k \pmod{pq} \\
       & \equiv & m \cdot 1^k \pmod{pq} \\
\end{eqnarray*}

The first step uses the fact that $\phi(pq) = (p - 1)(q - 1)$, the
second uses exponent laws, and third uses Euler's Theorem.  If $p$ and
$q$ are hundred-digit primes, $m$ is very likely to be relatively
prime to both $p$ and $q$.}

\ppart This congruence actually 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$.
}

\ppart 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 & \divides (m - m^{ed}), \\
q & \divides (m - m^{ed}).
\end{align*}
Thus, both $p$ and $q$ appear in the prime factorization of $m -
m^{ed}$.  Therefore, $pq \divides (m - m^{ed})$, and so:
\[
m  \equiv  m^{ed} \pmod{pq}.
\]
}

\eparts

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Appendix:  The Pulverizer}

\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, we can compute the GCD of 259 and 70 as follows:
\[
\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$ (this is worthwhile, because
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 above, 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.



\end{document}
