
\subsubsection{Finding GCD coefficients}

The previous algorithm finds the GCD, but
it can be modified to give the coefficients in the sum expression.

\newcommand{\Euclidb}[2]{\mbox{Euclid-Coefficients}(#1,#2)}
{\bf Procedure} $\Euclidb{x}{y}$, where $x$ and $y$ are not both $0$, and $x\ge y$ 
\begin{enumerate}
\item If $y=0$, return $(1,0)$.
\item Else $x = qy + r$
\item Use $\Euclidb{y}{r}$ to find $(a,b)$ such that $\gcd{y}{r}=ay+br$ 
\item Return $(b,a-qb)$.
\end{enumerate}

\begin{theorem}
If $\Euclidb{x}{y}$ terminates, its output $(a,b)$ satisfies
$ax+by = \gcd{x}{y}$.
\end{theorem}

\begin{proof}
By induction on the number of passes the algorithm takes to terminate. 

\noindent BASE CASE: $1$ pass \\
After one pass, $y = 0$, the GCD is $x$, and the return values are $(1,0)$.  
Since $(1)(x) + (0)(y) = x$, this is correct.

\noindent INDUCTIVE STEP: \\
Show that if works for $n$ passes, if it returns the correct values for 
$n-1$ passes:

\noindent Let $x = qy + r$.  By induction, the recursive call returns $(a,b)$ with 
$ay + br = g$, where $g$ is $\gcd{y}{x \bmod y}$. 
Note that this is also $\gcd{x}{y}$.\\
Rewrite $g$ in terms of $x$ and $y$ instead of in terms of $y$
and $x \bmod y$: \\
$g = ay + br = ay + b(x-qy) = bx + (a-bq)y$. \\
This returns the values $(b,a-bq)$ as claimed. 
\end{proof}

\begin{example}
Table method for getting GCD and Coefficients: run Euclid's algorithm,
then fill in the coefficients from the bottom up.
\begin{verbatim}
q     x    y      a   b
     949  273    -2   7 
3    273  130     1  -2
2    130   13     0   1   
10    13    0     1   0   
\end{verbatim}
Filling in table entries from the bottom: $g = (1)(13) + (0)(0)$. \\
Then $g = (0)(130) + (1)(13)$. \\
Then $g = (1)(273) + (-2)(130)$. \\
Then $g = (-2)(949) + (7)(273)$. 
\end{example}

\subsection{RSA cryptosystem}

We will finish today with a nice application of number theory to
cryptography.
RSA is a {\em public key} cryptosystem: anyone can encrypt (encode) a message
to me, but no one else can decrypt (decode) it.

It uses two {\em keys}, which are positive integers: \\
$e$, the {\em encryption key} which is public, and \\
$d$, the {\em decryption key} which is private (only the decrypter knows it). \\
It also takes a very big positive integer modulus $n$. \\

A message $m$ is interpreted as an integer (it is turned into a binary
representation). 
\begin{itemize}
\item
To encrypt a message $m < n$ into a coded message $c$: \\
Compute $c = m^e \bmod n$.
Anyone can do this, because $e$ and $n$ are public. 
\item
To decrypt a coded message $c$ into an uncoded message $m$: \\
Compute $m = c^d \bmod n$.
Only someone who knows the secret key $d$ can do this. 
\end{itemize}

Of course, to give the correct message, we need the following property: \\
For any $m < n$, $(m^e)^d \bmod n = m$. \\
In other words, $m^{ed} \bmod n = m$. \\

What kinds of numbers satisfy this condition? 
Using a little number theory: 

Choose $n = p q$, where $p$ and $q$ are primes. \\
Choose $e$, $d$ such that $ed \bmod (p-1)(q-1) = 1$. \\

\begin{theorem}
Suppose that $p$ and $q$ are primes, $n = p q$,
and $e$, $d$ are positive integers with 
$ed \bmod (p-1)(q-1) = 1$, and
suppose that $m$ is any natural number $< n$ such that 
(a technicality which usually holds) neither $p$ nor $q$ divides $m$. 
Then $m^{ed} \bmod n = m$. 
\end{theorem}

\begin{proof}
In book, see p. 147. \\
Basically, a bunch of exponential calculations and modular arithmetic.
\end{proof}

Here's an example (from the book):
Let $p = 43$, $q = 59$, so $n = 43 \times 59 = 2537$. \\
Let $e = 13$, $d = 937$.  Then $ed \bmod (p-1)(q-1) = 1$, as needed. \\
If you encrypt the number 1819 using exponentiation with $13$, mod 2537, you
get 2081. \\
When you decrypt 2081 using exponentiation with 937, mod 2537, you get back 1819.
We leave this to you to check. 

Fast exponentiation: \\
In recitation, we will show how to compute the big exponentiations
that are needed to implement RSA quickly.  It relies on the fact that 
$x^{ab}\bmod n = (x^a \bmod n)^b \bmod n$. 

This all works to encrypt and decrypt numbers,
but we haven't addressed the important issue: {\em secrecy}, 
i.e., the property that the coded message is hard to decrypt without
having access to $d$, the decryption key. 
This turns out to depend on whether or not $p$ and $q$ are very large numbers
(currently 200 digits), and keeping them, as well as $d$, secret. 
(Finding $d$ actually lets you find $p$, $q$, and vice versa.) 

In case $p$ and $q$ are large, no one yet knows how to ``break'' RSA in an
efficient way:
\begin{itemize}
\item   No one knows how to compute $p$, $q$ efficiently from $n$.
(Factoring large numbers is hard, though there's been progress.) 
\item   No one knows how to compute $d$ efficiently without $p$, $q$.
\item   No one knows how to find $m$ efficiently without $d$ (ie,
solve $c=n^e$ for $m$). 
\end{itemize}

In practice, how do we find suitable $p$, $q$, $e$ and $d$? 
Using fast algorithms for generating large prime numbers $p$, $q$.

To find $e$ and $d$, recall our objective:  We need $de \bmod k = 1$,
where $k = (p-1)(q-1)$.  Pick $e$ so that it is relatively prime to $k$ (there
are lots of
choices),  that is, $\gcd{e}{k} = 1$. By the GCD theorems, we
can find coefficients $a$, $b$ such that $a e + b k = 1$. If we just use
$d = a$ then $d e \bmod k = 1$ since $de + bk = 1 \longrightarrow
de = -bk + 1 \longrightarrow de \bmod k = 1$.

\subsection{Algorithm Verification}


For our final use of induction today, we will verify an iterative algorithm.

Take an algorithm for multiplying $a \times b$, where $a$ and $b$ are positive
integers of arbitrary length represented in binary, and the result
is also to be represented in binary. 
Assume that we have integer addition available,
and can examine individual bits.
$b[k]$ denotes $k$th high order bit of $b$. 

Algorithm: \\
Maintain an accumulator $\ms{acc}$, initially set to $a$. \\
Suppose that $b$ has $n$ bits, where b[1] is the highest bit, and b[n] is
the lowest bit. \\
For $k = 1$ to $n-1$ do: \\
if $b[k+1] = 0$ then $\ms{acc} := 2*\ms{acc}$ \\
else $\ms{acc} := 2*\ms{acc} + a$ 

The final result is in $\ms{acc}$. 

We'll use $\ms{high}(b,m)$ to denote the integer defined by the $m$
highest-order bits of $b$. 

For example: let $a = 5$, $b = 13 = 1101$. 
\begin{tabbing}
XXX\=XXX\=XXX\= \kill
$k$ \> $\ms{acc}$ \> $\ms{high}(b,k+1)$ \\
$0$ \> $5$        \> $1$ \\
$1$ \> $15$       \> $3 = 11$ \\
$2$ \> $30$       \> $6 = 110$ \\
$3$ \> $65$       \> $13 = 1101$ 
\end{tabbing}

We can show this is correct by induction:\\
For every $k$, $0 \leq k \leq n-1$, $P(k)$, where \\
$P(k)$: After $k$ iterations, $\ms{acc}$ is equal to $a \times
\ms{high}(b,k+1)$. 


BASE CASE: $k = 0$. \\
The highest-order bit is $1$, so $\ms{high}(b,1) = 1$. 
So, initially, $\ms{acc}$ contains $a = a \times 1$, as needed. \\
INDUCTIVE STEP: \\
Assume for $k$.  After $k$ iterations, $\ms{acc}$ contains 
$a \times \ms{high}(b,k+1)$. 
Show that after one more iteration, $\ms{acc}$ contains $a \times
\ms{high}(b,k+2)$. 

This depends on examining the $k+1$st iterative step, 
where we need to examine the $k+2$nd bit of $b$. \\
If the bit is a $0$, double $acc$, else double $acc$ and add $a$. 
Check the cases to see this is the right thing to do: 
If $0$, new desired number is just double the old. \\
If $1$, new desired number is double plus $a$, ... 

Why does this say that the final answer is correct? 

Specialize the result to $k = n-1$, $P(n-1)$: \\
After $n-1$ iterations, $\ms{acc}$ is equal to 
$a \times \ms{high}(b,n) = b$. 

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
