\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pst-all}
\usepackage{multicol}

\newcommand{\histob}[4]{
\pspolygon[fillstyle=solid,fillcolor=gray](#1,0)(#2,0)(#2,#3)(#1,#3)
\uput[ur](#1,-2){#4}
}

\begin{document}

\title{Episode 12 -- Breaking a substitution code}
\subtitle{European section -- Season 3}
\author{}
\date{}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}{Frequency analysis}

\begin{center}{\large A Manuscript on Deciphering Cryptographic Messages.}

by Abu Yusuf Ya 'qub ibn Is-haq ibn as-Sabbah\\ ibn 'omran ibn Ismail {\bf al-Kindi} (9th century).

\begin{multicols}{2}
\includegraphics[scale=0.7]{images/alkindi2.eps}

\includegraphics[scale=0.4]{images/alkindi.eps}
\end{multicols}

\end{center}
\end{frame}

\begin{frame}{Frequency analysis}

\begin{center}
{\large Letter frequencies in English}
\end{center}


\psset{xunit=0.35cm,yunit=0.3cm}
\begin{pspicture}(-2,-2)(27,14)
\psaxes[Dy=2](0,0)(0.1,14)
\psline(0,0)(27,0)
\histob{0}{1}{8.2}{a}
\histob{1}{2}{1.5}{b}
\histob{2}{3}{2.8}{c}
\histob{3}{4}{4.3}{d}
\histob{4}{5}{12.7}{e}
\histob{5}{6}{2.2}{f}
\histob{6}{7}{2.0}{g}
\histob{7}{8}{6.1}{h}
\histob{8}{9}{7.0}{i}
\histob{9}{10}{0.2}{j}
\histob{10}{11}{0.8}{k}
\histob{11}{12}{4.0}{l}
\histob{12}{13}{2.4}{m}
\histob{13}{14}{6.7}{n}
\histob{14}{15}{7.5}{o}
\histob{15}{16}{1.9}{p}
\histob{16}{17}{0.1}{q}
\histob{17}{18}{6.0}{r}
\histob{18}{19}{6.3}{s}
\histob{19}{20}{9.1}{t}
\histob{20}{21}{2.8}{u}
\histob{21}{22}{1.0}{v}
\histob{22}{23}{2.4}{w}
\histob{23}{24}{0.2}{x}
\histob{24}{25}{2.0}{y}
\histob{25}{26}{0.1}{z}
\end{pspicture}

\end{frame}

\begin{frame}{The Gold Bug cipher}
\Large
53\ddag\ddag\dag305))6\textasteriskcentered;4826)4\ddag.)4\ddag);806\textasteriskcentered;48\dag8\\
\$60))85;1\ddag(;:\ddag\textasteriskcentered8\dag83(88)5\textasteriskcentered\dag;46(;88\textasteriskcentered96\\
\textasteriskcentered?;8)\textasteriskcentered\ddag(;485);5\textasteriskcentered\dag2:\textasteriskcentered\ddag(;4956\textasteriskcentered2(5\textasteriskcentered--4)8\\
\$8\textasteriskcentered;4069285);)6\dag8)4\ddag\ddag;1(\ddag9;48081;8:8\ddag\\
1;48\dag85;4)485\dag528806\textasteriskcentered81(\ddag9;48;(88;4\\
(\ddag?34;48)4\ddag;161;:188;\ddag?;
\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large


\begin{center}
Symbol frequencies in the cipher
\end{center}


\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
8 & ; & 4 & \ddag & ) & \textasteriskcentered & 5 & 6 & \dag & 1 \\
\hline
33 & 26 & 19 & 16 & 16 & 13 & 12 & 11 & 8 & 8 \\
\end{tabular}

\bigskip

\begin{tabular}{c|c|c|c|c|c|c|c|c}
0 & 9 & 2 & : & 3 & ?& \$ & -- & . \\
\hline
6 & 5 & 5 & 4 & 4 & 3 & 2 & 1 & 1 \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\begin{center}
\huge
8 = e
\end{center}

\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c}
8 \\
\hline
e \\
\end{tabular}
\end{center}\pause


\begin{center}
\huge
;48 =\pause\ the
\end{center}
\end{frame}


\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c}
8 & ; & 4\\
\hline
e & t & h\\
\end{tabular}
\end{center}\pause


\begin{center}
\huge
;48;(88;4 =\pause\ thet.eeth =\pause\ the tree th
\end{center}

\end{frame}


\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c|c}
8 & ; & 4 & (\\
\hline
e & t & h & r\\
\end{tabular}
\end{center}\pause

\begin{center}
\huge
the tree ;4(\ddag?34\\ =\pause\ the tree thr\ddag?3h\\ =\pause\ the tree through
\end{center}

\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
8 & ; & 4 & ( & \ddag & ? & 3\\
\hline
e & t & h & r & o & u & g\\
\end{tabular}
\end{center}\pause

\begin{center}
\huge
\dag83(88 =\pause\ \dag egree =\pause\ degree
\end{center}

\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c}
8 & ; & 4 & ( & \ddag & ? & 3 & \dag\\
\hline
e & t & h & r & o & u & g & d\\
\end{tabular}
\end{center}\pause

\begin{center}
\huge
;46(;88\textasteriskcentered =\pause\ th6rtee\textasteriskcentered =\pause\ thirteen
\end{center}

\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
8 & ; & 4 & ( & \ddag & ? & 3 & \dag & 6 & \textasteriskcentered\\
\hline
e & t & h & r & o & u & g & d & i & n\\
\end{tabular}
\end{center}\pause

\large

\begin{center}
\huge
53\ddag\ddag\dag =\pause\ 5good =\pause\ A good
\end{center}
\end{frame}

\begin{frame}{The Gold Bug cipher : A solution}

\large

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}
8 & ; & 4 & ( & \ddag & ? & 3 & \dag & 6 & \textasteriskcentered & 5\\
\hline
e & t & h & r & o & u & g & d & i & n & a\\
\end{tabular}
\end{center}\pause

\begin{quote}
'A good glass in the bishop's hostel in the devil's seat forty-one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the death's-head a bee-line from the tree through the shot fifty feet out.'
\end{quote}

\end{frame}

\begin{frame}{Tips for frequency analysis}

\large

\begin{itemize}
\item Count up the frequencies of all the letters in the ciphertext. 
\item About five of the letters should have a frequency less than 1 per cent, they probably represent j, k, q, x and~z. 
\item One of the letters should have a frequency greater than 10 percent, and it probably represents e.
\end{itemize}

\begin{center}
\psset{xunit=0.35cm,yunit=0.2cm}
\begin{pspicture}(-2,-2)(27,14)
\psaxes[Dy=4](0,0)(0.1,14)
\psline(0,0)(27,0)
\histob{0}{1}{8.2}{a}
\histob{1}{2}{1.5}{b}
\histob{2}{3}{2.8}{c}
\histob{3}{4}{4.3}{d}
\histob{4}{5}{12.7}{e}
\histob{5}{6}{2.2}{f}
\histob{6}{7}{2.0}{g}
\histob{7}{8}{6.1}{h}
\histob{8}{9}{7.0}{i}
\histob{9}{10}{0.2}{j}
\histob{10}{11}{0.8}{k}
\histob{11}{12}{4.0}{l}
\histob{12}{13}{2.4}{m}
\histob{13}{14}{6.7}{n}
\histob{14}{15}{7.5}{o}
\histob{15}{16}{1.9}{p}
\histob{16}{17}{0.1}{q}
\histob{17}{18}{6.0}{r}
\histob{18}{19}{6.3}{s}
\histob{19}{20}{9.1}{t}
\histob{20}{21}{2.8}{u}
\histob{21}{22}{1.0}{v}
\histob{22}{23}{2.4}{w}
\histob{23}{24}{0.2}{x}
\histob{24}{25}{2.0}{y}
\histob{25}{26}{0.1}{z}
\end{pspicture}

\end{center}


\end{frame}

\begin{frame}{Tips for frequency analysis}

\large

\begin{itemize}
\item If the plaintext doesn't reveal itself immediately, which is often the case, then focus on pairs of repeated letters. 
\item In English the most common repeated letters are ss, ee, tt, ff, ll, mm and oo. 
\item If the ciphertext contains any repeated characters, you can assume that they represent one of these.
\end{itemize}
\end{frame}


\begin{frame}{Tips for frequency analysis}

\large

\begin{itemize}
\item More complex use of statistics can be conceived, such as considering counts of pairs of letters, or triplets (trigrams), and so on. 
\item For instance, q and u nearly always occur together in that order in English, even though q itself is rare. 
\item Also,\emph{th} is the most common bigram, and \emph{the} the most common trigram.
\end{itemize}
\end{frame}


\begin{frame}{Tips for frequency analysis}

\large

\begin{itemize}
\item One of the most useful skills for a cryptanalyst is the ability to identify words, or even entire phrases, based on experience or sheer guesswork. Any such word or phrase is known as a \emph{crib}.
\end{itemize}
\end{frame}

\begin{frame}{Cipher 8}

\pause

\begin{center}
\includegraphics[scale=0.9]{images/alkindi2.eps}\\
Al-Kindi
\end{center}

\end{frame}

\begin{frame}{Cipher 6}

\pause

\begin{center}
\includegraphics[scale=1.2]{images/vigenere.eps}\\
Blaise de Vigenère
\end{center}

\end{frame}

\begin{frame}{Cipher 1}

\pause

\begin{center}
\includegraphics[scale=0.4]{images/babbage.eps}\\
Charles Babbage
\end{center}

\end{frame}

\begin{frame}{Cipher 2}

\pause

\begin{center}
\includegraphics[scale=0.25]{images/turing.eps}\\
Alan Turing
\end{center}

\end{frame}

\begin{frame}{Cipher 5}

\pause

\begin{center}
\includegraphics[scale=0.6]{images/diffie.eps}\\
Ralph Merkle, Martin Hellman, Whitfield Diffie
\end{center}

\end{frame}

\begin{frame}{Cipher 4}

\pause

\begin{center}
\includegraphics[width=8cm]{images/rivest.eps}\\
Adi Shamir, Ronald Rivest, Len Adleman
\end{center}

\end{frame}

\begin{frame}{Cipher 3}

\pause

\begin{center}
\includegraphics[scale=2]{images/zimmermann.eps}\\
Phil Zimmermann
\end{center}

\end{frame}

\begin{frame}{Cipher 7}

\pause

\begin{center}
\includegraphics[scale=0.45]{images/cocks.eps}\\
Clifford Cocks
\end{center}

\end{frame}

\begin{frame}{Cipher 9}

\pause

\begin{center}
\includegraphics[scale=1.1]{images/perec.eps}\\
Georges Perec
\end{center}

\end{frame}



\end{document}
