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

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

\begin{document}
\inclassproblems{9, Fri.}

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

\begin{problem}

A critical question about RSA (which is described below) 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{
\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(de) = (d - 1)(e - 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$.

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

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

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

\end{document}