\hyperdef{mod}{n}{\section{Arithmetic with an Arbitrary Modulus}}

Turing's code did not work as he hoped.  However, his essential
idea--- using number theory as the basis for cryptography--- succeeded
spectacularly in the decades after his death.

In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman at MIT proposed a
highly secure cryptosystem (called \textbf{RSA}) based on number theory.
Despite decades of attack, no significant weakness has been found.
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.

Interestingly, RSA does not operate modulo a prime, as Turing's scheme
may have, but rather modulo the product of \textit{two} large primes.
Thus, we'll need to know a bit about how arithmetic works modulo a
composite number in order to understand RSA.  Arithmetic modulo an
arbitrary positive integer is really only a little more painful than
working modulo a prime, in the same sense that a doctor says ``This is
only going to hurt a little'' before he jams a big needle in your arm.

\subsection{Relative Primality and Phi}

First, we need a new definition.  Integers $a$ and $b$ are
\term{relatively prime} iff $\gcd(a, b) = 1$.  For example, 8 and 15
are relatively prime, since $\gcd(8, 15) = 1$.  Note that every
integer is relatively prime to a genuine prime number $p$, except for
multiples of $p$.

We'll also need a certain function that is defined using relative
primality.  Let $n$ be a positive integer.  Then $\phi(n)$ denotes the
number of integers in $\set{1, 2, \dots, n - 1}$ that are relatively
prime to $n$.  For example, $\phi(7) = 6$, since 1, 2, 3, 4, 5, and 6
are all relatively prime to 7.  Similarly, $\phi(12) = 4$, since only
1, 5, 7, and 11 are relatively prime to 12.  If you know the prime
factorization of $n$, then computing $\phi(n)$ is a piece of cake,
thanks to the following theorem.

\begin{theorem}
\label{th:phi}
The function $\phi$ obeys the following relationships:
\begin{enumerate}
\item[(a)] If $a$ and $b$ are relatively prime, then $\phi(ab) = \phi(a)\phi(b)$.
\item[(b)] If $p$ is a prime, then $\phi(p^k) = p^k - p^{k-1}$ for $k \geq 1$.
\end{enumerate}
\end{theorem}

Here's an example of using Theorem~\ref{th:phi} to compute $\phi(300)$:
%
\begin{align*}
\phi(300)
    & = \phi(2^2 \cdot 3 \cdot 5^2)\\
    & = \phi(2^2) \cdot \phi(3) \cdot \phi(5^2)
            & \text{(by Theorem~\ref{th:phi}.(a))}\\
    & = (2^2 - 2^1) (3^1 - 3^0) (5^2 - 5^1) 
            & \text{(by Theorem~\ref{th:phi}.(b))}\\
    & = 80.
\end{align*}
\iffalse
We factor 300 in the first step, use part (1) of Theorem~\ref{th:phi}
twice in the second step, use part (2) in the third step, and then
simplify.
\fi

We'll work out a proof of Theorem~\ref{th:phi}.(a) in the next
section, after we've work out a few more properties of modular arithmetic.
We'll also give another a proof in a few weeks based on rules for counting
things.

To prove Theorem~\ref{th:phi}.(b), notice that the numbers in the interval
from 0 to $p^{k}-1$ that are divisible by $p$ are all those of the form
$mp$.  For $mp$ to be in the interval, $m$ can take any value from 0 to
$p^{k-1}-1$ and no others, so there are exactly $p^{k-1}$ numbers in the
interval that are divisible by $p$.  Now $\phi(p^{k})$ equals the number
of remaining elements in the interval, namely, $p^k -p^{k-1}$.


\subsection{Generalizing to an Arbitrary Modulus}

Let's generalize what we know about arithmetic modulo a prime.  Now,
instead of working modulo a prime $p$, we'll work modulo an arbitrary
positive integer $n$.  The basic theme is that arithmetic modulo $n$ may
be complicated, but the integers {\em relatively prime} to $n$ remain
fairly well-behaved.  For example, the proof of Lemma~\ref{lem:inverses}
of an inverse for $k$ modulo $p$ extends to an inverse for $k$ relatively
prime to $n$:

\begin{lemma}
\label{lem:inverse-arb}
Let $n$ be a positive integer.  If $k$ is relatively prime to $n$,
then there exists an integer $k^{-1}$ such that:
%
\[
k \cdot k^{-1} \equiv 1 \pmod{n}
\]
\end{lemma}


\iffalse
\begin{proof}
There exist integers $s$ and $t$ such that $s k + t n = \gcd(k, n) =
1$ by Theorem~\ref{th:gcd}.  Rearranging terms gives $tn = 1 - sk$,
which implies that $n \divides 1 - sk$ and $sk \equiv 1 \pmod{n}$.  Define
$k^{-1}$ to be $s$.
\end{proof}
\fi

As a consequence of this lemma, we can cancel a multiplicative term
from both sides of a congruence if that term is relatively prime to
the modulus:

\begin{corollary}
\label{cor:cancellation-arb}
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
If
%
\[
a k \equiv b k \pmod{n}
\]
%
then
%
\[
a \equiv b \pmod{n}
\]
\end{corollary}

This holds because we can multiply both sides of the first congruence
by $k^{-1}$ and simplify to obtain the second.

\subsection{Euler's Theorem}

RSA essentially relies on Euler's Theorem, a generalization of
Fermat's Theorem to an arbitrary modulus.  The proof is much like the
proof of Fermat's Theorem, except that we focus on integers relatively
prime to the modulus.  Let's start with a lemma.

\begin{lemma}
\label{lem:permutes-arb}
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
Let $k_1, \dots, k_r$ denote all the integers relatively prime to $n$
in the range $0 \leq k_i < n$.  Then the sequence:
%
\[
\rem{k_1 \cdot k}{n},\quad
\rem{k_2 \cdot k}{n},\quad
\rem{k_3 \cdot k}{n},\quad
\quad \dots\quad,
\rem{k_r \cdot k}{n}
\]
%
is a permutation of the sequence:
%
\[
k_1,\quad k_2,\quad \dots\quad, k_r.
\]
\end{lemma}

\begin{proof}
We will show that the numbers in the first sequence are all distinct
and all appear in the second sequence.  Since the two sequences have
the same length, the first must be a permutation of the second.

First, we show that the numbers in the first sequence are all
distinct.  Suppose that $\rem{k_i k}{n} = \rem{k_j k}{n}$.  This is
equivalent to $k_i k \equiv k_j k \pmod{n}$, which implies $k_i \equiv
k_j \pmod{n}$ by Corollary~\ref{cor:cancellation-arb}.  This, in turn,
means that $k_i = k_j$ since both are between 1 and $n-1$.  Thus, a
term in the first sequence is not equal to any other term.

Next, we show that each number in the first sequence appears in the
second.  By assumption, $\gcd(k_i, n) = 1$ and $\gcd(k, n) = 1$, which
means that
%
\begin{align*}
\gcd(n, \rem{k_i k}{n}) & = \gcd(k_i k, n)
            & \text{(by Lemma~\ref{lem:gcd}.\ref{gcd5})}\\
      & = 1 & \text{(by Lemma~\ref{lem:gcd}.\ref{gcd3})}.
\end{align*}
%
So $\rem{k_i k}{n}$ is relatively prime to $n$ and is in the range from 0
to $n - 1$ by the definition of remainder.  The second sequence is defined
to consist of all such integers.
\end{proof}

We can now prove Euler's Theorem:

\begin{theorem}[Euler's Theorem]
Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
Then
\begin{eqnarray*}
k^{\phi(n)} \equiv 1 \pmod{n}
\end{eqnarray*}
\end{theorem}

\begin{proof}
Let $k_1, \dots, k_r$ denote all integers relatively prime to $n$
such that $0 \leq k_i < n$.  Then $r = \phi(n)$, by the definition of
the function $\phi$.  Now we can reason as follows:
%
\begin{align*}
\lefteqn{k_1 \cdot k_2 \cdots k_r} \hspace{0.25in} \\
& =
\rem{k_1 \cdot k}{n} \cdot 
\rem{k_2 \cdot k}{n} \cdots 
\rem{k_r \cdot k}{n} & \text{(by Lemma~\ref{lem:permutes-arb})}
\\
& \equiv 
(k_1 \cdot k) \cdot 
(k_2 \cdot k) \cdot 
\cdots 
(k_r \cdot k) \pmod{n} & \text{(by Cor~\ref{aran})}
\\
& \equiv  
(k_1 \cdot k_2 \cdots k_r) \cdot k^r \pmod{n} & \text{(rearranging terms)}
\end{align*}

Lemma~\ref{lem:gcd}.\ref{gcd3}.\ implies that $k_1 \cdot k_2
\cdots k_r$ is prime relative to $n$.  Therefore, we can cancel this
product from the first expression and the last by
Corollary~\ref{cor:cancellation-arb}.  This proves the claim.
\end{proof}

We can find multiplicative inverses using Euler's theorem as we did
with Fermat's theorem: if $k$ is relatively prime to $n$, then
$k^{\phi(n) - 1}$ is a multiplicative inverse of $k$ modulo $n$.
However, this approach requires computing $\phi(n)$.  Our best method
for doing so requires factoring $n$, which can be quite difficult in
general.  Fortunately, when we know how to factor $n$, we can
use Theorem~\ref{th:phi} to compute $\phi(n)$ efficiently!

\begin{notesproblem}\label{phi2}
This problem provides the remaining proof of Theorem~\ref{th:phi}.(a).

Suppose $m,n$ are relatively prime.

\bparts

\ppart Prove that for any $a,b$, there is an
$x$ such that
\begin{align}
x \equiv & a \pmod{m}, \label{xa}\\
x \equiv & b \pmod{n} \label{xb}.
\end{align}

\hint Congruence~\eqref{xa} holds iff
\begin{equation}\label{xj}
x = jm + a.
\end{equation}
for some $j$.  So there is such an $x$ only if
\begin{equation}\label{jn}
j m +a \equiv b \pmod{n}.
\end{equation}
Solve~\eqref{jn} for $j$.

\solution{
\begin{proof}
\footnote{Adapted from
\href{http://www.cut-the-knot.org/blue/chinese.shtml}{\texttt{http://www.cut-the-knot.org/blue/chinese.shtml}}.}
Since $m,n$ are relatively prime, there is an inverse, $m'$, modulo $n$ of
$m$.  So $j = m'(b-a)$ satisfies~\eqref{jn}.  Now~\eqref{xj} leads to the
definition
\[
x_1 \eqdef m'(b-a)m + a.
\]
So
\[
x_1 = (m'(b-a))m + a \equiv a \pmod{m}, 
\]
and
\[
x_1 = m'(b-a)m + a = m'm(b-a) +a \equiv 1\cdot(b-a) + a \equiv b \pmod{n},
\]
proving that $x_1$ satisfies the congruences~\eqref{xa} and~\eqref{xb}.
\end{proof}}

\ppart\label{x0} Prove that there is an $x$ satisfying the
congruences~\eqref{xa} and~\eqref{xb} such that $0 \leq x < mn$.

\solution{
Let
\[
x_0 \eqdef \rem{x_1}{mn},
\]
where $x_1$ satisfies~\eqref{xa} and~\eqref{xb}.

Now $0 \leq x_0 < mn$ by definition of remainder.  Further, we know $x_0
\equiv x_1 \pmod{mn}$, which immediately implies that $x_0 \equiv x_1 \pmod{m}$ and $x_0 \equiv x_1 \pmod{n}$.  So $x_0$ also satisifies~\eqref{xa}
and~\eqref{xb}, and is therefore the desired solution.
}

\ppart\label{uniq} Prove that the $x$ satisfying part~\eqref{x0} is unique.

\solution{Assume $x_0,y$ both satisfy congruences~\eqref{xa}
and~\eqref{xb}.  Taking the differences we see that
\[
x_0 - y \equiv 0 \pmod{m} \text{  and  } x_0 - y \equiv 0 \pmod{n}.
\]
So by definition, both $m$ and $n$ divide $x_0 - y$, and since $m$ and $n$
are relatively prime, this implies $mn \divides (x_0 - y)$.  But if $x_0$
and $y$ are both in the range $0$ to $mn-1$, then $mn > \card{x_0 - y}$,
so it must be that $y = x_0$, as required.}

\ppart Conclude from the preceding parts of this problem
\iffalse and Problem~\ref{pmn}\eqref{rp} \fi
that
\[
\phi(mn)=\phi(m)\phi(n)
\]
where $\phi$ is Euler's function.  This will complete the proof of
Theorem~\ref{th:phi}.(a).

\solution{
For any positive integer, $k$, let
\[
[0,k) \eqdef \set{0,1,\dots, k-1}.
\]
By part~\eqref{uniq}, the mapping from $x$ to $(\rem{x}{m},\rem{x}{n})$ is
a bijection between $[0,mn)$ and $[0,m) \cross [0,n)$.  Moreover, since
$x$ is relatively prime to $mn$ iff $x$ is relatively prime to $m$ and $x$
is relatively prime to $n$, \iffalse by problem~\ref{pmn}\eqref{rp}\fi
this mapping also defines a bijection between the integers in $[0,mn)$
that are relatively prime to $mn$ and the pairs of integers in $[0,m)
\cross [0,n)$ that are relatively prime to $m$ and $n$, respectively.  In
particular the number, $\phi(mn)$ of numbers in $[0,mn)$ that are
relatively prime to $mn$ is the same as the number $\phi(m)\phi(n)$ of
pairs of integers in $[0,m) \cross [0,n)$ whose first coordinate is
relatively prime to $m$ and whose second coordinate is relatively prime to
$n$.  }

\eparts
\iffalse

General case:

There is an $x$ such that
\begin{align}
x \equiv a \pmod{m_1}, \text{ and}\label{xa}\\
x \equiv b \pmod{m_2}\label{xb}
\end{align}
iff $a \equiv b \pmod{\gcd(m_1, m_2)}$, where, by convention, $a \equiv b
\pmod{1}$ holds iff $a=b$.  The solution is unique modulo the least common
multiple, $\lcm(m_1, m_2)$, of $m_1$ and $m_2$.

Congruence~\eqref{xa} holds iff $x = jm_1 + a$, and congruence~\eqref{xb}
holds iff $x = km_2 + b$ for some $j,k$, so
\begin{equation}\label{jk}
jm1 - km2 = a-b
\end{equation}
The lefthand side of~\eqref{jk} is divisible by $g \eqdef \gcd(m_1, m_2)$
and therefore so is the righthand side.  Letting
\begin{align*}
n_1 & \eqdef m_1/g, \\
n_2 & \eqdef m_2/g, \text{ and}\\
c & \eqdef \frac{a-b}{g},
\end{align*}
and dividing both sides of~\eqref{jk} by $g$ gives
\[
j n_1 - k n_2 = c.
\]
This implies
\begin{equation}\label{jn}
j n_1 \equiv c \pmod{n_2}.
\end{equation}
By definition, $n_1$ and $n_2$ are relatively prime, for we got them by
dividing $m_1$ and $m_2$ by their greatest common factor.  So letting $h$
be an inverse modulo $n_2$ of $n_1$, we conclude that $j = hc$ satisfies
~\eqref{jn}, and so
\[
x_0 \eqdef hcm_1 + a
\]
is a solution to the congruences~\eqref{xa} and~\eqref{xb}.

To prove the uniqueness part, assume $y$ also is a solution to the two
congruences.  Taking the differences we see that
\[
x_0 - y = 0 \pmod{m_1} \text{  and  } x_0 - y = 0 \pmod{m_2}
\]
which implies
\[
x_0 - y \equiv 0 \pmod{\lcm(m_1, m_1)},
\]
that is
\[
x_0 \equiv y \pmod{\lcm(m_1, m_1)},
\]
as required.

\footnote{Adapted from \href{http://www.cut-the-knot.org/blue/chinese.shtml}}

\fi
\end{notesproblem}

\subsection{RSA}
Finally, we are ready to see how the RSA public key encryption scheme works:
\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' = \rem{m^e}{n}.
\]

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

\end{description}

%We'll explain in class why this way of Decoding works!

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

\endinput