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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\renewcommand{\coursecopyrightnames}{Eric~Lehman}

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

\begin{document} 
\inclassproblems{6}

Turing's plan to use number theory as the basis for a cryptographic
system reached was realized in 1978, when Rivest, Shamir, and Adleman
invented the RSA cryptosystem.  RSA has proved to be vastly more
secure than the German navy's Enigma.

RSA is a {\em public-key cryptosystem}.  Each user creates a {\em
public key} and a {\em secret key}.  The public key is published
widely, like a phone number.  The secret key is kept hidden.  If I
want to send you a message, I encrypt it using your public key.  Then
you decrypt it using your secret key.  This is a great setup, because
you and I can have a private conversation without meeting in advance
to agree on a key!

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

%\newpage

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

\bparts

\ppart Use the Pulverizer to find integers $x$ and $y$ such that $x
\cdot 326 + y \cdot 175 = 1$.

\solution{
\[
\begin{array}{ccccrcl}
a' & \quad & b' & \quad & r & = & a' - q \cdot b' \\ \hline
326 && 175 && 151	& = & 326 - 1 \cdot 175 \\
175 && 151 && 24	& = & 175 - 1 \cdot 151 \\
&&&&			& = & 175 - 1 \cdot (326 - 1 \cdot 175) \\
&&&&			& = & -1 \cdot 326 + 2 \cdot 175 \\
151 && 24 && 7		& = & 151 - 6 \cdot 24 \\
&&&&			& = & (326 - 1 \cdot 175)
				- 6 \cdot (-1 \cdot 326 + 2 \cdot 175) \\
&&&&			& = & 7 \cdot 326 - 13 \cdot 175 \\
24 && 7 && 3		& = & 24 - 3 \cdot 7 \\
&&&&			& = & -1 \cdot 326 + 2 \cdot 175
				- 3 \cdot (7 \cdot 326 - 13 \cdot 175) \\
&&&&			& = & -22 \cdot 326 + 41 \cdot 175 \\
7 && 3 && 1		& = & 7 - 2 \cdot 3 \\
&&&&			& = & (7 \cdot 326 - 13 \cdot 175)
				- 2 \cdot (-22 \cdot 326 + 41 \cdot 175) \\
&&&&			& = & 51 \cdot 326 - 95 \cdot 175 \\
3 && 1 \\
\end{array}
\]
}



\ppart Theorem~\ref{th:pulverizer} determines when a multiplicative
inverse exists for a {\em composite} modulus.  Show that if $\gcd(c,
n) = 1$, then there is an integer $c^{-1}$ such that $c \cdot c^{-1}
\equiv 1 \pmod{n}$.

\solution{ By Theorem~\ref{th:pulverizer}, there exist integers $x$
and $y$ such that:
\[
xc + yn  =  1.
\]
Rearranging terms gives:
\[
xc - 1  =  -yn.
\]

Therefore, $n \divides (xc - 1)$ and so $xc \equiv 1 \pmod{n}$.  Thus, $x$
is the multiplicative inverse of $c$ modulo $n$.}

\ppart This, in turn, clarifies when we can cancel multiplicative
terms in a congruence.  Show that $ac \equiv bc \pmod{n}$ implies that
$a \equiv b \pmod{n}$ provided $\gcd(c, n) = 1$.

\solution{By the previous problem part, $c$ has a multiplicative
inverse.  Multiplying both sides of $ac \equiv bc \pmod{n}$ by this
inverse gives $a \equiv b \pmod{n}$.}

\eparts

\end{problem}

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

%\newpage

\begin{problem}
Let's try out RSA!  There is a complete description of the algorithm
on the last page.

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

\end{itemize}

When you're done, write your public key on the board.

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

\end{itemize}

Remember that you can compute a power quickly by repeated squaring.
Put your encrypted message on the board next to the recipient's public
key.  Why might you not want to send message $m = 0$ or $m = 1$?

\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

\end{problem}

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

%\newpage

\begin{problem}
A important question is whether decrypting an encrypted message always
gives back the original message!  Mathematically, this amounts to
asking whether:
\[
m  \equiv  m^{de} \pmod{pq}.
\]

We know that $de \equiv 1 \pmod{(p-1)(q-1)}$, by our choice of $d$ in
step 4 of the \textbf{beforehand} procedure.  This means that for some
integer $k$:
\[
de  =  1 + k (p-1) (q-1).
\]

\bparts

\ppart Use Fermat's theorem to prove that $m \equiv m^{de} \pmod{p}$.

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

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

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

\newpage

\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' \eqdef 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{document}
