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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{5}{September 24, 2004}

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

\insolutions{%\stamp
\section{The Pulverizer}
To employ RSA, we'll need a mathematical tool that dates to
sixth-century India, where it was called {\em kuttak}, ``The
Pulverizer''.  (The Pulverizer is often lamely referred to as the
``extended Euclidean GCD algorithm'', but that will not happen in {\em
this} recitation.)  The Pulverizer constructively proves the following
theorem:

\begin{theorem}
\label{th:pulverizer}
For every pair of positive integers $a$ and $b$, there exist integers
$x$ and $y$ such that:
\[
x \cdot a + y \cdot b  =  \gcd(a, b).
\]
\end{theorem}

For example, if $a = 259$ and $b = 70$, then the Pulverizer works as
follows:

\[
\begin{array}{ccccrcl}
a^\prime & \quad & b^\prime & \quad & r & = & a' - q \cdot b' \\ \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) \\
&&&&		& = &	3 \cdot 259 - 11 \cdot 70 \\
21 && 7
\end{array}
\]

In the first two columns, we're just carrying out Euclid's gcd
algorithm.  We keep track of two variables, $a'$ and $b'$.  Initially,
we set $a' = a$ and $b' = b$.  At each step, we compute $r = a' \rem
b'$.  If $r = 0$, then the procedure terminates and $b' = \gcd(a, b)$.
If $r \neq 0$, then let $a' = b'$, let $b' = r$, and continue the
procedure.

In the third column, we express the remainder $r$ in the form $r = a'
- q \cdot b'$ at each step.  By replacing $a'$ and $b'$ with
previously-computed linear combinations of $a$ and $b$, we can express
$r$ as a linear combination of $a$ and $b$ as well.  Consequently, the
final equation in the third column expresses $\gcd(a, b)$ as a linear
combination of $a$ and $b$:

\begin{eqnarray*}
3 \cdot 259 - 11 \cdot 70\ =\ \gcd(259, 70)\ =\ 7
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\instatements{\newpage}

\begin{problem}
Let's try out RSA!  There is a complete description of the algorithm
on the next page.  You'll probably need extra paper.  \textit{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-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.

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

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

\eparts

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

\instatements{\newpage}

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

\end{problem}

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

\instatements{\newpage}

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

\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 & \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}.
\]
}

\eparts

\end{problem}

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

\end{document}
