\documentclass[12pt]{article}

%begin{latexonly}
\usepackage{mathpazo} % or something mathppl, mathptmx or not.
\usepackage{mystyle}
%end{latexonly}
\usepackage[dvips]{graphicx}
\usepackage{floatflt}
\usepackage[usenames]{color}
\usepackage{html}

\usepackage[in,myheadings]{fullpage}
\addtolength{\topmargin}{-.2in}
\addtolength{\textheight}{.4in}
\usepackage{hyperref}

\pagestyle{myheadings}
\markboth{\small\textsc{Scott Sutherland}}
         {\small\textsc{MSTP math workshop, ~~ October 2005}}

\newcommand{\dfn}[1]{{\sffamily\textbf{#1}}}
\newcommand{\cl}{\centerline}
\newcommand{\mod}{\mbox{mod}\ }

%begin{latexonly}
\newcommand{\plain}[1]{{\fontfamily{pcr}\selectfont\bfseries%
    \obeyspaces\color{PineGreen}{#1}}}
\newcommand{\crypt}[1]{{\fontfamily{pcr}\selectfont\bfseries%
    \obeyspaces\color{BrickRed}{#1}}}
\newcommand{\describeBib}[1]{{\nonfrenchspacing \it #1}}
%end{latexonly}
\begin{htmlonly}
\newcommand{\plain}[1]{{\tt{\color{DarkGreen}#1}}}
\newcommand{\crypt}[1]{{\tt{\color{DarkRed}#1}}}
\newcommand{\describeBib}[1]{{\it #1}}
\newcommand{\href}[2]{\htmladdnormallink{#2}{#1}}
\end{htmlonly}


\newcommand{\p}[1]{\plain{#1}}
\newcommand{\C}[1]{\crypt{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{V'ir Tbg n Frperg\\ % I've Got a Secret, rot13. 
{\small An Introduction to Cryptography}}

\author{Scott Sutherland\footnote{
       Institute for Mathematical Sciences, Stony Brook University,
       Stony Brook, New York, 11794-3660.  
       \href{mailto:scott@math.sunysb.edu}{\tt scott@math.sunysb.edu},
       \href{http://www.math.sunysb.edu/~scott}
	    {\tt http://www.math.sunysb.edu/$\sim$scott/}}
}
\date{October 14, 2005 (revised \today)}

\begin{document}

\maketitle

\thispagestyle{empty}
\begin{abstract}
  We introduce ideas and techniques from cryptography,
  using mathematics related to the middle-school mathematics
  curriculum. The majority of the material in this note was presented
  as part of a professional development workshop for middle-school
  mathematics teachers.
\end{abstract}


\section{Pleased to Meet You, Hope You Guessed My Name}

People have been interested in writing secret messages almost as long
as people have been able to write. During the twentieth century, it
became clear that cryptography had a lot to do with mathematics, and
the role of making and breaking codes has increased dramatically in the
military since the First World~War.\footnote{
  Many people have claimed that if the Allies
  hadn't broken the German Enigma code, the outcome of the Second
  World War would have been different.}
Although you may not know it, cryptography plays a role in most of our
daily lives as well.  When we make a purchase over the internet,
our web browser uses encryption to keep our financial data secure.
Automatic Teller Machines (ATMs), satellite TV, and a number of other
everyday services use encryption.  
Secret codes are also just kind of fun to fiddle with, and fun is part 
of our main focus today. 

First, let's introduce some terminology.  The discipline of encoding and
decoding secret messages is called \dfn{cryptography}, 
from the Greek words 
{\it kryptos} ($\kappa\rho\nu\pi\tau{o}\sigma$), meaning hidden or
secret, and {\it graphia} ($\gamma\rho\alpha\phi\iota\alpha$), meaning
writing. The original, readable message is referred to as the
\dfn{plaintext} or \dfn{clear text}.  Encoding the message is called
\dfn{encryption} (or sometimes \dfn{enciphering}), and the
hard-to-read result is called the \dfn{ciphertext} (or the
\dfn{encrypted message}).  Turning the ciphertext back into plaintext
is called \dfn{decrypting}, \dfn{deciphering}, or \dfn{decoding} the
message.   Usually the conversion process depends on an additional piece of
information, usually called the \dfn{key} or the \dfn{password}; the
key forms the basis of the security and must be kept private.
Sometimes there are different keys used to encrypt and decrypt
messages.  If it is infeasible to determine the key used for
decryption without knowing the key used to encrypt, this method can be
used for \dfn{public-key cryptography} (which we won't be able to
discuss). 
Finally, decrypting a message without being told the corresponding key
is called \dfn{cracking} or \dfn{breaking} the code.

Technically speaking, there is a difference between a cipher and a
code:  a \dfn{code} works at the level of meaning, replacing words or
phrases with others (for example, when parents refer to a
four-year-old's upcoming birthday party as ``the festivities'' to
avoid exciting her prematurely), while a \dfn{cipher} replaces
individual letters or groups of letters with others.  Naturally, these
are not mutually exclusive, and are often used together.\footnote{%
  Another way to create a secret message is using
  \dfn{steganography}, which is the process of hiding the fact that a
  message exists at all. Using  ``invisible ink'' is steganography, as
  is hiding  messages within other messages.  For example, looking at
  the second 
  letter of each word in the message below (which was reportedly sent by
  a German spy during World War~I \cite[p. 521]{Kahn}),  
  \begin{quotation}
      \crypt{Apparently neutral's protest is thoroughly discounted
      and ignored.  Isman hard hit.  Blockade issue affects
      pretext for embargo on byproducts, ejecting suets and
      vegetable oils.}
  \end{quotation}
  one finds a rather different message, namely
  \begin{quotation}
	\plain{Pershing sails from NY June I.}
  \end{quotation}
  Steganography is often used to augment cryptography, and is also
  related to ``digital watermarking''.} 
While formally they are different things, one often informally uses the word
``code'' when speaking of ciphers.  Since we will only be looking at
ciphers, we will use the terms interchangeably.

One last bit of terminology we must cover is the choice of
\dfn{Alphabet} for the plaintext (and the ciphertext).  We need to
agree up front which characters we will be writing our messages in.
Prior to the advent of computers, messages typically consisted of only 
the 26 letters of the alphabet; all spaces, punctuation, numerals, and so on
were removed from the message prior to encryption.  No distinction was
made between upper-case and lower-case letters.  Today, a computer
tends to do the enciphering and deciphering, and the alphabet is much
larger, typically containing 128, 256, or more character codes.  We'll
adopt the more spy-like convention of using just 26 characters.    

In this note, we'll write our plaintext in all lower case letters, as \\
\cl{\plain{abcdefghijklmnopqrstuvwxyz}}
and our ciphertext in all uppercase letters\\
\cl{\crypt{ABCDEFGHIJKLMNOPQRSTUVWXYZ}}
Since we'll be leaving out the spacing and punctuation, it is
traditional to group the text into blocks of letters (typically five),
so that one doesn't get lost.

For example, if we wanted to encrypt the sentence ``Please do not read this.'',
we would first represent it as \\
\cl{\plain{pleas edono tread this}}
Note that the last group has only four letters, because the length of
the message was not divisible by 5.


\section{I'm a Substitute for Another Guy}
\label{SubstitutionCiphers}

The simplest ciphers are based on the idea of replacing each letter in
the plaintext with a different letter.  For example, instead of
\plain{a} we might use \crypt{R}, for \plain{b} write \crypt{A}, and
so on.  This class of ciphers is called a \dfn{substitution cipher}
(more precisely, a monoalphabetic substitution cipher);
these are the types of ciphers you sometimes see on the
crossword page of the newspaper.  Note that in this case, the key is
rather long (namely, just as long as the alphabet, since we must say
which character gets replaced with which), and there are many possible
encryptions ($26!$ or $40,329,146,112,660,563,584,000,000$).  But,
they are still pretty easy to crack.

Let's look at an example.
\begin{center}
\crypt{RUQDY QNTRZ AQIQB NAZNC YQQBQ WBJQR UJWXS RUNVW WENCQ TRYQK QRK}
\end{center}
%      asecr etmay bekep tbyth reepe oplea slong astwo ofthe mared ead

At first glance, this may seem like total gibberish. But upon a little
examination, we see that the letter \crypt{Q} occurs 11 times, much
more than any other.  It would reasonable to guess that \crypt{Q}
stands for a commonly occurring letter. In English, the letter
\plain{e} is the most common letter, followed by \plain{t}, \plain{a},
and \plain{o}.\footnote{
 This frequency sometimes shows up as \plain{etaoin shrdlu} in
 pre-1980s print, because the keys on Linotype machines used to set
 type were arranged in frequency order.  For the same reason,
 \plain{qwerty} or \plain{asdf} show up when people bang on keyboards.
 }

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|cc||cc||cc|}
\hline
Letter&	Frequency &  Letter & Frequency & Letter & Frequency \\ \hline
\plain{a}&  8.167 & \plain{j}&  0.153 & \plain{s}&  6.327   \\ \hline
\plain{b}&  1.492 & \plain{k}&  0.772 & \plain{t}&  9.056  \\ \hline
\plain{c}&  2.782 & \plain{l}&  4.025 & \plain{u}&  2.758  \\ \hline
\plain{d}&  4.253 & \plain{m}&  2.406 & \plain{v}&  0.978  \\ \hline
\plain{e}& 12.702 & \plain{n}&  6.749 & \plain{w}&  2.360 \\ \hline
\plain{f}&  2.228 & \plain{o}&  7.507 & \plain{x}&  0.150 \\ \hline
\plain{g}&  2.015 & \plain{p}&  1.929 & \plain{y}&  1.974 \\ \hline
\plain{h}&  6.094 & \plain{q}&  0.095 & \plain{z}&  0.074 \\ \hline
\plain{i}&  6.966 & \plain{r}&  5.987 &          &        \\ \hline
\end{tabular}
\caption{\sf Frequency (in percent) of occurrence of
  letters in English text ({\small adapted from \cite{Lewand}}) }
\end{center}
\end{table}

So, in our message, we would likely guess that \crypt{Q} corresponds to
\plain{e}, and that \crypt{W}, \crypt{R}, and \crypt{N} correspond to
\plain{o}, \plain{a}, and \plain{t}, although these last three might
be permuted.  
Then we plug them in, and guess
at which letters correspond to which until the message makes sense.
Once we have a few letters, we can try to recognize patterns
corresponding to common words (\plain{the}, \plain{and}, and so on).
We can also make use of the fact that the most common pairs of letters
in English are (in order) 
\plain{th}, \plain{he}, \plain{in}, \plain{en}, \plain{nt},
\plain{re}, \plain{er}, \plain{an}, \plain{ti}, \plain{es},
\plain{on}, \plain{at}, \plain{se}, \plain{nd}, \plain{or},
\plain{ar}, \plain{al}, \plain{te}, \plain{co}, \plain{de},
\plain{to}, \plain{ra}, \plain{et}, \plain{ed}, \plain{it},
\plain{sa}, \plain{em}, and \plain{ro}.

Making use of such probabilistic guesses is called 
\dfn{frequency analysis}.  As the length 
of the ciphertext increases, frequency analysis becomes increasingly
reliable.  There are records from the 9th century~A.D.\
indicating that frequency analysis was in use in the Arab world at
that time.  For this method to work, typically you need a message of at
least 50 characters. 

\goodbreak
So far, we have what is below (assuming the guesses for characters are
correct): 

\begin{center}
\crypt{RUQDY QNTRZ AQIQB NAZNC YQQBQ WBJQR UJWXS RUNVW WENCQ TRYQK QRK}\\
\plain{a~e~~~et~a~~~e~e~~t~~t~~~ee~e~o~~ea~~~o~~~a~t~o~o~t~e~~a~e~~ea\phantom{d}}
\end{center}

It still takes quite a bit of playing around to get the rest of the
message.  Remember that the spaces were removed from the original; as
a hint, I'll put them back in, together with our guesses.  To avoid
spoiling the fun for those who don't want a hint, it is in a 
footnote.\footnote{%
A hint:\\
\begin{tabular}{@{\extracolsep{-3pt}}cccccccccccccccc}
\C{R}&\C{UQDYQN}&\C{TRZ}&\C{AQ}&\C{IQBN}&\C{AZ}&\C{NCYQQ}&\C{BQWBJQ}&
 \C{RU}&\C{JWXS}&\C{RU}&\C{NVW}&\C{WE}&\C{NCQT}&\C{RYQ}&\C{KQRK}\\
\p{a}&\p{~e~~et}&\p{~a~}&\p{~e}&\p{~e~t}&\p{~~}&\p{t~~ee}&\p{~eo~~e}&
 \p{a~}&\p{~o~~}&\p{a~}&\p{t~o}&\p{o~}&\p{t~e~}&\p{a~e}&\p{~ea~}\\
% A secret may be kept by three people 
%  as long as two of them are dead.
\end{tabular}
}

\section{The Caesar Cipher and Modular Arithmetic}
In order to better understand substitution ciphers, and make something
better out of them, we do what is very common in mathematics:  we make
the problem easier, and don't worry (at first) that it seems like a
step backwards.

So, instead of considering all possible substitutions, we just think
about some simple ones: those where we leave the alphabet in order,
and just shift by a few letters.  Julius Caesar is reported to have
used such a cipher with a shift of 3 for his military communications.

The correspondence between plaintext and ciphertext is as follows:

\begin{center}
\plain{abcde~fghij~klmno~pqrst~uvwxy~z}\\
\crypt{XYZAB~CDEFG~HIJKL~MNOPQ~RSTUV~W}
\end{center}

If we encrypt \plain{veni vidi vici} using the Caesar cipher, we get
\crypt{SBKF SFGF SFZF}.  To decrypt, we just shift back by 3 letters.

So where's the math?  Let's see if we can find it.

First, we assign a number to each letter of the 
plaintext alphabet, beginning with 0, so we that have the
correspondence below.\\
{\small
\label{alphanumChart}
\begin{tabular}%{\textwidth}%
{@{\extracolsep{-3.4pt}}|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\p{a}&\p{b}&\p{c}&\p{d}&\p{e}&\p{f}&\p{g}&\p{h}&\p{i}&\p{j}&\p{k}&\p{l}&\p{m}
&\p{n}&\p{o}&\p{p}&\p{q}&\p{r}&\p{s}&\p{t}&\p{u}&\p{v}&\p{w}&\p{x}&\p{y}&\p{z}\\ \hline
0 &1& 2& 3& 4& 5& 6& 7& 8&9&10&11&12&
13&14&15&16&17&18&19&20&21&22&23&24&25\\ \hline
\end{tabular}
}

Now, we can view our enciphering as taking the number corresponding to
the letter, adding 3 to it, and then writing down the letter that
corresponds to the sum.  If the result is 26 or larger, we subtract 26
so that if falls back in the desired range.

This type of arithmetic is called \dfn{addition modulo 26} or just
adding \dfn{mod~26}. The number 26 is called \dfn{the base}.
You are already quite familiar with another type
of modular arithmetic, namely working mod~12.  When we answer a
question like ``What time will it be 4 hours after 10 o'clock?'', we
are adding mod~12.  Another way to view modular arithmetic is that we
do ``regular'' arithmetic, divide the answer by the base, and then only
keep the remainder.\footnote{
Modular arithmetic works for multiplication as well as for addition
and subtraction.  One has to be careful about what division means,
however. We'll cover this further in section \ref{MultCiphers}.}
  We sometimes also work modulo~7 when we make statements
like ``My birthday is on a Friday this year, so next year it will be
on Saturday''-- here we are using the fact that $365 = 7\times52 + 1$,
so $365 \equiv 1 (\mod 7)$.  Waiting a year advances the day of the
week by one (except in a leap year).

\begin{floatingfigure}[r]{.5\textwidth} %[htbp]
  \centering
  \includegraphics[height=3in]{numbercircle.eps}
\end{floatingfigure}

Returning to our encryption problem, we see that applying the Caesar
cipher corresponds just to adding 3 (mod 26). 
To decipher, we can either subtract 3 modulo 26 (remembering to add 26
to the answer if it turns out negative), or we can add 23, which is
$26-3$.  These give exactly the same answer after reducing modulo~26,
in the same way that a clock will read the same if you move the hands
ahead by 3 hours or back 9 hours.

\label{NumberCircle}
A useful mental model for modular addition is a ``number circle''.
Take the familiar number line and wrap it around a circle so that the
base (26) falls on zero.  Then adding corresponds to a clockwise
rotation, and subtraction to counterclockwise rotation.


Naturally, we don't
have to shift by 3 as Julius Caesar did (apparently Augustus Caesar
preferred to shift by 1).  We have 25 possible ciphers like the Caesar
cipher, which are called \dfn{shift ciphers}, or sometimes the general
shift cipher is called ``a Caesar cipher''.\footnote{
  One shift cipher commonly used in internet postings or emails that
  may tell the ending of a movie or the answer to a puzzle is called
  ``rot13'' (for rotation by 13).  This is just a Caesar-like cipher
  with a shift of 13 (leaving all the non-alphabetic text alone).
  This is popular because applying the same shift again decodes the
  text.}
If someone says {\em the} Caesar cipher, they almost certainly mean a
shift cipher with a shift of~3.

Notice that shift ciphers are {\it very} easy to break, since you
only have to guess one letter and then you know everything.  If you
haven't already discovered it, the title of this note is encrypted
with a shift cipher, leaving the spaces and punctuation in.
So that you don't have to look back, the (encrypted) title is \\
\cl{\crypt{V'IR TBG N FRPERG}} % I've Got a Secret, rot13. 

\section{Many Caesars: the Vigen\`ere Cipher}
\label{Vigenere}

So far, it seems we've gone in the wrong direction: from the poor
security offered by the general substitution cipher to nearly no
security offered by a shift cipher.  But, taking a step backward will
allow us to leap forward.

In the Vigen\`ere Cipher, we choose a word or phrase as our encryption
key. We then convert it to a sequence of numbers (again using
\plain{a}=0, \plain{b}=1, \ldots, \plain{z}=25), and apply a different
shift to the plaintext corresponding to the letters in the keyword.
When we use up the shifts from the keyword, we repeat it
again.

This is probably best understood via an example.  Suppose we choose
\plain{jasmine} as our key, and want to encrypt the phrase \plain{we
are getting hungry}.
Translating \plain{jasmine} to its numerical equivalents gives the
sequence of shifts {9, 0, 18, 12, 8, 13, 4}.  So we work as
follows:

\begin{center} 
\begin{tabular}{crrrrrrrrrrrrrrrrrrr}
   &\p{w}&\p{e}&\p{a}&\p{r}&\p{e}&\p{g}&\p{e}&\p{t}&\p{t}&\p{i}&\p{n}&\p{g}&\p{h}&\p{u}&\p{n}&\p{g}&\p{r}&\p{y}\\[2pt]
   &$22$&$4$&$ 0$&$17$&$ 4$&$ 6$&$4$&$19$&$19$&$ 8$&$13$&$ 6$&$ 7$&$20$&$13$&$ 6$&$17$&$24$ \\[2pt]
$+$&$ 9$&$0$&$18$&$12$&$ 8$&$13$&$4$&$ 9$&$ 0$&$18$&$12$&$ 8$&$13$&$ 8$&$ 4$&$ 9$&$ 0$&$18$ \\ \hline
$=$&$ 5$&$4$&$18$&$ 3$&$12$&$19$&$8$&$ 2$&$19$&$ 0$&$25$&$14$&$20$&$ 2$&$17$&$15$&$17$&$16$ \\[2pt]
   &\C{F}&\C{E}&\C{A}&\C{D}&\C{M}&\C{T}&\C{I}&\C{C}&\C{T}&\C{A}&\C{Z}&\C{O}&\C{U}&\C{C}&\C{R}&\C{P}&\C{R}&\C{Q}\\
\end{tabular}
\end{center}

Depending on where it falls in the message, each character of
plaintext could be any one of several ciphertexts.  
For example, in the example above, \plain{e} becomes \crypt{E}, \crypt{M}, or
\crypt{I}, and the two \crypt{E}s in the ciphertext come from an \plain{e}
or an \plain{r}.

\smallskip
The Vigen\`ere cipher is significantly harder to break than a Caesar
cipher.  For about 300 years, it was believed to be unbreakable,
although Charles Babbage and Friedrich Kasiski independently
determined a method of breaking it in the middle of the nineteenth
century.  The method uses repeated patterns in the text to
determine the length of the key.  Once it is known that the key is,
say, 8 characters long, frequency analysis can be applied to every 8th
letter to determine the plaintext.  This method is called \dfn{Kasiski
examination} (although it was first discovered by Babbage).
Despite the fact that the method of breaking the Vigen\'ere cipher had
been published 50 years earlier,  
the cipher was widely held to be unbreakable until the 1920s, 
being described as ``impossible of translation'' in an article
appearing in {\em Scientific American} in 1917.

%
\begin{floatingtable}[r]
{\ttfamily\tiny
\begin{tabular*}{42em}
{@{\extracolsep{-.8em}}r|rrrrrrrrrrrrrrrrrrrrrrrrrr}
~&a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p&q&r&s&t&u&v&w&x&y&z\\ \hline
a&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\
b&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A\\
c&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B\\
d&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C\\
e&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D\\
f&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E\\
g&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F\\
h&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G\\
i&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H\\
j&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I\\
k&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J\\
l&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K\\
m&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L\\
n&N&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M\\
o&O&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N\\
p&P&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O\\
q&Q&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P\\
r&R&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q\\
s&S&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R\\
t&T&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S\\
u&U&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T\\
v&V&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U\\
w&W&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V\\
x&X&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W\\
y&Y&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X\\
z&Z&A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y\\
\end{tabular*}
}
\caption{\sffamily A \textit{tabula recta}}
\end{floatingtable}

We should remark that one can implement this cipher using a 
{\it tabula recta}, which is a $26\times26$ table listing all the
shifts corresponding to each letter of the key. It is really just an
addition table for letters. To use the {\it tabula recta},
the plaintext letter gives the row, and the key letter gives the column.
The letter of ciphertext is then found where the two intersect.
Using such a table, one doesn't need to do the numerical conversion and the
modular addition; this is how people in the sixteenth century used the
cipher.  However, the underlying mathematical structure is hidden, which is
a disadvantage for our purposes.


\medskip
The Vigen\`ere cipher is named after Blaise de Vigen\`ere, a sixteenth
century diplomat and cryptographer, although the cipher was invented by
Giovan Batista Belaso in 1553.  Vigen\`ere actually invented a
different cipher, which we will now discuss.

The cipher Vigen\`ere invented is a little harder to crack than the
one that bears his name.  In this cipher, rather than repeating the
key, one begins with a key, and then appends the text itself to get
the shifts to apply.  This is a type of \dfn{autokey} cipher, because
the key is (semi-)automatically generated by the message itself.
                                                                     
As an example, we will use the same plaintext (\plain{we are getting hungry})
and initial key (\plain{jasmine}), and apply Vigen\`ere's autokey
cipher.  The autokey will then be \plain{jasminewearegettin}, 
giving us the encryption below.\footnote{
  Some accounts append the ciphertext to the initial key rather than
  the plaintext as we do here. In both cases, there is a serious
  drawback to this cipher: if an error is made in enciphering even one
  letter, it will
  propagate throughout the remainder of the text.}

\begin{center} 
\begin{tabular}{crrrrrrrrrrrrrrrrrrr}
   &\p{w}&\p{e}&\p{a}&\p{r}&\p{e}&\p{g}&\p{e}&\p{t}&\p{t}&\p{i}&\p{n}&\p{g}&\p{h}&\p{u}&\p{n}&\p{g}&\p{r}&\p{y}\\[2pt]
   &$22$&$4$&$ 0$&$17$&$ 4$&$ 6$&$4$&$19$&$19$&$ 8$&$13$&$ 6$&$ 7$&$20$&$13$&$ 6$&$17$&$24$ \\[2pt]
$+$&$ 9$&$0$&$18$&$12$&$8 $&$13$&$4$&$22$&$4 $&$ 0$&$17$&$4 $&$6 $&$4 $&$19$&$19$&$ 8$&$13$ \\\hline
$=$&$ 5$&$4$&$18$&$ 3$&$12$&$19$&$8$&$15$&$23$&$ 8$&$ 4$&$10$&$13$&$24$&$ 6$&$25$&$25$&$11$ \\[2pt]
   &\C{F}&\C{E}&\C{A}&\C{D}&\C{M}&\C{T}&\C{I}&\C{P}&\C{X}&\C{I}&\C{E}&\C{K}&\C{N}&\C{Y}&\C{G}&\C{Z}&\C{Z}&\C{L} \\
\end{tabular} 
\end{center}


Another variation on these same ideas is to use a passage from a book
in order to determine the sequence of shifts.  The location of the
start of the passage serves as the key.
For example, the key might be given as {123:5}, and then cryptographer
turns to page 123 and begins with the 5th word to extract the key.
The Bible and the works of Shakespeare were both popular to use as source
books. 

While these methods do away with the problem of repeating shifts that
hinder the Vigen\`ere cipher, frequency analysis and similar
techniques can still be employed.  This is because certain letters
(specifically \plain{e}, \plain{t}, \plain{o}, etc.) will still occur
more frequently in both the text and the key.  Given a long sample of
ciphertext, a competent cryptographer can break both of these codes.

\section{An Unbreakable Cipher}
Is it possible to create a cipher that no one can break, no matter how
smart they are and how hard they try?  Yes, as long as you remember
that you don't get to know the key to crack the code.

The idea is similar to the Vigen\`ere cipher, except that instead of
using English text as our key, we use a sequence of random numbers.
It is critical that the random sequence of numbers be truly random,
and that the sequence never be reused.  Such a cipher is called a
\dfn{one-time pad}, and was proven to be unbreakable by Claude Shannon
in 1949.

To use a one-time pad, we have an arbitrarily long list of random
numbers. This sequence is our ``one-time pad''.  We add each of these
in turn to our plaintext, and reduce modulo 26. This gives our
ciphertext.  To decrypt, we reverse the process, subtracting the same
sequence of numbers from the ciphertext.   For this to be truly
secure, we can never use this sequence of numbers again, hence the
phrase ``one-time'' in the name.

The security of the system stems from the fact that any plaintext can
encrypt to any ciphertext of the same length.  For example, the
ciphertext \crypt{QQQQQQ} could correspond to the plaintext
\plain{attack} or \plain{gohome}.  For the first, the key sequence is 
16,23,23,16,14,6 and in the second message, the key is 13,2,12,2,4,9.
Since the key could be any of these (or any other one), there is no
way to break the cipher except to get your hands on the key.

One-time pads were used heavily during the second world war, and
during the cold war.  Books consisting of long lists of random digits
were given to agents.  But it was critical that the codebooks not fall
into enemy hands, or the ciphers would immediately become useless.
Anyone who possessed the codebook could easily decrypt the messages.

It is also very important that the numbers be truly random.  A
computer program cannot generate truly random numbers without some
outside source of randomness.  Several successful attacks on early
``secure'' web communications relied on weaknesses in the browser's
random number generator.  There is a story that during World War II,
some of the codebooks were generated by drawing numbered balls out of
a bin.  However, the person drawing the balls would put the ball back
if he drew it twice in a row, thinking a repeated number wasn't
random.   This slight deviation from true randomness was enough to
enable several ``unbreakable'' messages to be broken. 

\section[{\em Mod}ern Times]{{\em Mod}ern Times
\footnote{
  Because of time limitations, this and following sections were not
  covered in the professional development workshop.}
}
\label{MultCiphers}
Having squeezed all of the juice out of the idea of adding letters to others,
we go back and look again at other ways to proceed.
It seems like it should work to multiply the numeric codes for the
letters in the plaintext instead of adding them, so let's try that.
Just as before, we'll begin with something analogous to the Caesar
cipher: our key is a single number between 1 and 25, and we multiply
each letter by that number and reduce modulo 26.

Since the Caesar cipher added 3, let's try multiplying by 3.  Suppose
our plaintext is \plain{blue}.  Representing this as numbers, we have
the sequence 1,11,20,4 (refer to the chart on page~\pageref{alphanumChart} if
you like).  Now we multiply each one by 3 and reduce modulo~26. For
the first letter of the ciphertext, we get the numeric value 3, or
\crypt{D}.  The second letter is $33~\mod 26$, or 7, which we can
write as \crypt{H}.  The third is $60~\mod 26$, which is 8 (or
\crypt{I}), since $60 = 8 + 2\times 26$.  And our final letter
encrypts to \crypt{M}, so the ciphertext is \crypt{DHIM}.

One thing to notice here is that we get a different class of
substitution ciphers out of this process.  The Caesar ciphers gave us
one set, and these multiplicative ones give us another set.  These
seem to mix things up a little more (for example, although \plain{l}
and \plain{u} start out far apart in the alphabet, they encrypt to the
adjacent letters \crypt{H} and \crypt{I}. 

Now that we see how to encrypt, let's try to decrypt this enciphered
message, assuming we know that the encryption key was 3.  That is, we
are given the ciphertext \crypt{DHIM} as well as the fact that the
encryption key was 3, and we want to recover the plaintext.  Writing
the ciphertext as numbers, we have 3,7,8,12 and we want to divide each
by 3.  The first is easy: $3/3 = 1$, and sure enough, \crypt{D}
corresponds to \crypt{b}.  But $7/3 = 2\frac{1}{3}$, and we don't have
a letter for that.  Is all lost?

We just have to make sense of what we mean by division.  Remember, we are
working modulo 26, so we want to solve the equation
$$7 = 3x (\mod 26).$$
This means we get to add multiples of 26 to get things to work out;
the above equation is the same as saying
$$ 7 = 3x      \quad\mbox{or}\quad 
   7+26 = 3x   \quad\mbox{or}\quad 
   7+52 = 3x   \quad\mbox{or}\quad \ldots$$
Since $7+26=33$, we see that $x=11$ works, and our plaintext letter
was indeed the letter \plain{l}.

Deciphering $I$ works the same way: $8/3$ isn't a whole number, and
neither is $34/3$, but $60/3=20$, so our plaintext is just the letter
with character code 20, or \plain{u}.

\smallskip
We could have saved a little work by changing division into an appropriate
multiplication.  Just as with real numbers, to divide by 3 we can
multiply by $\frac{1}{3}$, as long as we interpret $\frac{1}{3}$
correctly.  As above, we have to find a number $x$ so that
$$3x = 1 (\mod 26).$$
This number is 9, since $3\times 9 = 27 = 1 + 26$. 9 is called the
\dfn{multiplicative inverse} of 1, modulo 26.  When we are working
modulo 26, division by 3 is the same as multiplication by 9.


\medskip
Now suppose we had tried a key of 4, and wanted to encrypt the name of
our friend \plain{bob}.  This has the numeric sequence 1,14,1, and
after multiplying by 4, we have 4,56,4. Since we are working\ \mod~26,
we must 
reduce 56 to 4, giving the ciphertext \crypt{EEE}.
Something is fishy here--- there is no way to know whether the
\crypt{E} came from \plain{b} or \plain{o}.  Why is 4 different from 3?

The issue is 4 and 26 share a common divisor, 2, while 3 and 26 are
relatively prime.  When the key (4) and the size of the alphabet (26)
are not relatively prime, there will be different plaintext letters
which correspond to the same ciphertext.  In the example above, we
have
$$ 4\times 1 = 4 \qquad\mbox{and}\qquad 
   4\times 14 = 56 = 4 + (2\times 26) .$$
If any time we use key which is an even number, any two plaintext
letters which have character codes differing by 13 will encrypt to the
same ciphertext, and so can't be deciphered again.

Notice also that 4 does not have a multiplicative inverse\ \mod~26,
because the equation $4x = 1 (\mod 26)$ has no solution. To see this,
notice that $4x$ must be an even number, but if we add 1 to any
multiple of 26, we get an odd number.  So there can be no number $x$
so that $4x$ is of the form $1 + 26k$.


There are two obvious ways to avoid this collision problem: don't use
keys which share a common divisor with the length of the alphabet, or
change the the alphabet so that its length is a prime number.  In our
case, this is easily accomplished by adding some punctuation to the
alphabet (for example, adding a period, a comma, and and exclamation
mark), which would give us a 29-character alphabet.  Or we could
include the digits 0--9, and a period.  In order to be consistent with
the what we've done before, however, we'll just avoid using even keys
(or 13). 

\medskip
We can combine the cipher above with a Caesar cipher to get an
\dfn{affine cipher}.  That is, our key consists of two numbers $m$
and $b$, where $m$ is relatively prime to the length of the alphabet.
Then to get the ciphertext for the letter with character code $x$,
we compute $mx + b$ and reduce modulo the length of the alphabet (26
in our case).

\label{affineCipher}
As an example of an affine cipher, let's encrypt the work \plain{blue}
using $m=3$ and $b=20$.  As before, we note that \plain{blue} has
character codes 1,11,20,4, which becomes 3,7,8,12 after multiplying by
3 (and reducing/ \mod~26).  Now we add 20 to each one to get
23,27,28,32, which reduces to 23,1,2,6 modulo 26.  This gives the
ciphertext \crypt{XBCG}.

To decrypt, we just reverse the process: subtract 20 from each, then
multiply by 9 (the inverse of 3), reducing modulo 26.

\medskip
An affine cipher is just a specific case of the general substitution
cipher we discussed in section~\ref{SubstitutionCiphers}, and so it is 
readily broken using frequency analysis.  Indeed, if you know a
message is encrypted with an affine cipher, you only need to determine
what two letters are to crack the encryption.

\section{Twins and Triplets}

Of course, one could increase the security of an an affine cipher
using a different one on each letter, as the Vigen\`ere cipher
discussed in section~\ref{Vigenere} does.  But this is extra effort
with no payoff: such a cipher can be cracked by exactly the same
methods, and it is more work to encipher.

However, because an affine cipher sends adjacent letters far apart,
one way to improve the cipher is to work on multiple letters at a
time, either in pairs, triplets, or larger groupings.  Instead of
assigning numbers to individual letters, we think of our message as
made up of ``super-characters'', where each individual letter gives us
one ``digit'' of the group.

For example, if we wanted our super-characters to be made up of pairs of
two letters (called a \dfn{digraph}), we would think of the plaintext
\plain{double} as being made up of the three pairs of digraphs
\plain{do}, \plain{ub}, and \plain{le}.  How many pairs of such
digraphs do we have?  Since we have 26 choices for the first letter
and 26 for the second, there are $26\times 26 = 676$ such pairs.  The
first one is \plain{aa} and gets assigned the number 0, \plain{ab}
gets 1, \plain{ac} has the code 2, and so on, up to \plain{zz} which
gets the character code 675.  If the plaintext has an odd number of
characters, we add an additional character onto the end (usually
\plain{x}, \plain{q}, or \plain{z}).

With so many digraphs, we certainly don't want to have to use a table
to look up the numeric equivalences.  But notice that we can readily
figure out which letter pair gets which number by paying attention to
place value.  Remember that when we write the decimal number for
six hundred seventy five, we write
$$ 675 ~=~ 6\times 100 ~+~ 7\times 10 ~+~ 5.$$
Here, we don't have ten ``digits'', we have twenty-six.\footnote{
  I suppose we could call these hexicosimal numbers (from the Greek
  for 26), but that's too weird, so we just say we are working in
  base~26.}
So to determine the code for \plain{do}, we multiply the number for
the single letter \plain{d} by 26, and add the number for \plain{o}.
That is, it has the numeric code  $3\times 26 ~+~ 14 = 92$.
Similarly, \plain{ub} corresponds to $20\times 26 ~+~ 1 = 521$, and
\plain{le} gives 290.  To go from the number to its letter equivalent,
we divide by 26; the dividend gives the first character, and the
remainder gives the second.  For example, to figure out the letters
which correspond to 524, we divide 524 by 26.  The result is 20, with
a remainder of 4, so 524 corresponds to \plain{ue}.

\medskip
Let's encrypt the word \plain{blue} using the same affine cipher as in
section~\ref{affineCipher} (that is, with $m=3$ and $b=20$), but
working with digraphs.  

\begin{center} 
\begin{tabular}{|r|c|c|}
\hline
{\rm plaintext} &  \plain{bl}           &\plain{ue}              \\ \hline
x               &$1\times26~+~11=37$    &$20\times26 ~+~ 4 = 524$ \\[5pt]
3x+20           &$131$                  &$1592 = 240 ~(\mod 676)$ \\
                &$131 = 5\times 26 ~+~1$&$240 = 9\times26 ~+~ 6$ \\\hline
{\rm ciphertext}&  \crypt{FB}           &\crypt{JG}              \\\hline
\end{tabular} 
\end{center}

Note that we can take $m$ to be any number between 1 and 675 (as long as
it is relatively prime to 26), and we can take $b$ as anything between
0 and 675.

\medskip
To break such a code, we can apply frequency analysis, but this time
we must look at frequency of pairs of letters.  This is still doable,
but more challenging.

\medskip
Notice that we can just as well use triplets of letters
(\dfn{trigraphs}), or blocks of any length we choose.  For example, if
we were using 4-tuples, the word \plain{blue} would be a single
``character'' and would have the numeric code
$$1\times 26^3 ~+~ 11\times 26^2 ~+~ 20\times 26 ~+~ 4 ~~=~ 25536.$$
However, such numbers quickly become unwieldy unless one is using a
computer. 


\section{The Hill Cipher}

Rather than working with such large numbers, the \dfn{Hill cipher}
works on groups of letters in a somewhat different manner. The Hill
cipher works by viewing a group of letters as a vector, and encryption
is done by matrix multiplication.  However, we will avoid reference to
linear algebra in our explanation.

\smallskip
The Hill cipher was first described by Lester Hill in a paper
published in 1931. While this cipher can work on blocks of letters of
any length, we'll describe it as working on pairs of letters, or
digraphs.   

First, our key consists of four numbers which we call $a$, $b$, $c$,
and $d$.  These numbers must be chosen so that the quantity $ad-bc$ is
relatively prime to the length of the alphabet (26 in our case, so
$ad-bc$ cannot be even or a multiple of 13).

To encrypt a pair of letters, we look up their numeric equivalents as
usual. Suppose these numbers are $x$ and $y$.  Then the corresponding
letters in the ciphertext are given by
$$ ( ax + by ) \mod 26  \quad\mbox{and}\quad (cx + dy) \mod 26 .$$

\medskip
As an example, let's encipher the phrase \plain{do it now} using a
Hill Cipher with the key $a=2$, $b=3$, $c=5$, and $d=6$.  
Since $ad-bc=-3=23 (\mod 26)$, this is a valid key.  To encode, we
break our text up into pairs, and since there are an odd number of
letters, we add  \plain{x} to the end.


\begin{center} 
{\ttfamily
\begin{tabular}{|r|c|c|c|c|}
\hline
{\rm plaintext} & \p{do} &\p{it}      &\p{no}      & \p{wx}      \\ \hline
            &$(3, 14)$   &$(8, 19)$   &$(13,14)$   & $(22,23)$   \\[5pt]
(ax+by,     &$(6+42=22 $ &$(16+57=21,$&$(26+42=16,$&$(44+69=9,$  \\
 cx+dy)     &$ 15+84=21)$&$40+114=24)$&$65+84=19) $&$110+138=14$ \\\hline
{\rm ciphertext}& \C{WV} &  \C{VY}    & \C{QT}     & \C{JO}      \\\hline
\end{tabular} 
}
\end{center}


To decipher, we apply a different Hill cipher to the ciphertext.  If
the pairs of letters have numeric equivalencies $X$ and $Y$, then the
plaintext is given by
$$(AX + BY)\ \mod 26  \quad\mbox{and}\quad (CX+DY)\ \mod 26.$$
To find $A$, $B$, $C$, and $D$, we first find the multiplicative
inverse of $ad-bc$ and denote it by $J$.  Then\footnote{
This formula comes from linear algebra.  It is just the inverse of the
matrix $\left(\begin{array}{cc} a&b\\c&d\end{array} \right)$.
}
$$A=(\phantom{-}d\times J)\ \mod 26, \qquad
  B=          (-b\times J)\ \mod 26       $$
$$C=          (-c\times J)\ \mod 26, \qquad
  D=(\phantom{-}a\times J)\ \mod 26       $$

For example, if we encipher with $a=2$, $b=3$, $c=5$, and $d=6$ as
above, then $J=17$, and the deciphering transformation has
 $A=24$, $B=1$, $C=19$, and $D=8$.



The real strength of the Hill cipher is that it can be adapted to work
on large blocks of text without having to use huge numbers as we did
in the previous section.  For example, to work on blocks of 3 letters
at a time, we choose 9 numbers $a,b,c, d,e,f, g, h, k$, and then
the code of the ciphertext corresponding to the triple $(x,y,z)$
is
$$(ax+by+cz, dx+ey+fz, gx+hy+kz)\ \mod 26.$$
Extending this to larger blocks of letters works analogously.


\smallskip
In attempting to crack a Hill cipher, the usefulness of frequency
analysis becomes vanishingly small as the size of the blocks of
letters increases. A Hill cipher isn't hard to implement on groups of
6 or more letters.  A major disadvantage, however, is that it is quite
susceptible to what is called a \dfn{known plaintext attack}. If part
of the plaintext is known to the attacker, then the deciphering
transformation can be deduced merely by solving some linear equations.
Some help can be gained by applying a Vigen\`ere cipher after
encrypting with a Hill cipher,\footnote{If the length of the key for the
  Vigen\`ere cipher is the same as the length of the letter-blocks,
  this yields an affine cipher $AX+B$, where $A$ is an $n\times n$
  matrix,  $X$ is our vector of $n$ plaintext letters,
and $B$ is the $n$-vector corresponding to the Vigen\`ere key.}
although there are much better ways to improve the security.



%\begin{floatingfigure}[r]{.5\textwidth}
\begin{figure}[htbp]
  \centering
  \includegraphics[width=.7\textwidth]{HillFig2.eps}
\end{figure}
%\end{floatingfigure}

It is possible to build a machine that does all of the arithmetic
corresponding to the Hill cipher by means of gears and pulleys.  
Lester Hill and Louis Weisner were issued a patent for a ``Message
Protector'' which mechanically implemented a Hill cipher
acting on blocks of six letters at a  time.  The major gears in the machine
correspond to a ``number circle'' as discussed on
page~\pageref{NumberCircle}; multiplication is done by advancing
the gear by a fixed number of teeth several times (that is, repeated addition).
The figure is taken from the patent application (adapted from
\cite{CryptoSite}).  

\section{Adieu}
In this note we've discussed just a few ideas related to
cryptography.  There are many others, most of which use quite
sophisticated mathematics.  The National Security Agency, which is the
U.S. government agency dealing with cryptography, is reportedly also
the largest employer of mathematicians in the world.  (We don't really
know, because they keep this information secret!)

%\newpage
\begin{thebibliography}{WWW}

\bibitem[Cdb]{CryptoSite}
{\em Crypto Drop Box}.
\url{http://www.und.nodak.edu/org/crypto/crypto/}.\\
\describeBib{Contains figures from Hill's patent application,
pictures of a German Enigma machine, and other material. Maintained by the  
American Cryptogram Association.}


\bibitem[Fla]{InCode}
Sarah Flannery with David Flannery,
{\em In Code: A Mathematical Journey}.
Workman Publishing, 2001.\\
\describeBib{A very engaging and readable account by Sarah
  Flannery, whose high school project on cryptography (done when she
  was 16) won the 1999 European Union Young Scientists contest. 
  Part memoir, part puzzle book, and part mathematical exploration, and
  all very entertaining.}


\bibitem[Gar]{Gardiner}
Martin Gardner,
{\em Codes, Ciphers and Secret Writing}.
Dover Publishing, 1984.\\
\describeBib{ Explains in simple terms how to encode and
  decode messages in various ciphers, describes coding machines, and
  gives formulas for invisible ink. Appropriate for middle school
  students.} 

\bibitem[Kah]{Kahn}
David Kahn,
{\em The Codebreakers; The Comprehensive History of Secret Communication
from Ancient Times to the Internet}.
Charles Scribner's Sons, 1996.\\
\describeBib{ A massive (nearly 1200 pages!), but very
  readable historical account of cryptography.  A classic.}

\bibitem[Lew]{Lewand}
Robert E. Lewand,
{\em Cryptological Mathematics}.
Mathematical Association of America, 2000.\\
\describeBib{ Covers the essential number theory required to 
understand various encryption schemes. Requires mathematics at
about the level of a good high-school student.}

\bibitem[Sut]{331Notes}
Scott Sutherland, 
{\em fsqFsHn sGGousG (Secret Messages)}. \\
\href{http://www.math.sunysb.edu/~scott/Book331/crypto.html}
     {\tt http://www.math.sunysb.edu/$\sim$scott/Book331/crypto.html}.\\
\describeBib{ Part of my own text aimed at doing mathematics
  with computers, for math majors in their junior or sophomore year of
  college. Uses the {\tt Maple} programming language.}

\bibitem[Wik]{Wikipedia}
{\em Encryption}, article in Wikipedia.
\url{http://en.wikipedia.org/wiki/Encryption}.\\
\describeBib{ A good online article with more details about most of 
  the material here, and links to much more.}


\end{thebibliography}
\end{document}


