slides/caesar-break.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>Breaking caesar ciphers</title>
   5     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
   6     <style type="text/css">
   7       /* Slideshow styles */
   8       body {
   9         font-size: 20px;
  10       }
  11       h1, h2, h3 {
  12         font-weight: 400;
  13         margin-bottom: 0;
  14       }
  15       h1 { font-size: 3em; }
  16       h2 { font-size: 2em; }
  17       h3 { font-size: 1.6em; }
  18       a, a > code {
  19         text-decoration: none;
  20       }
  21       code {
  22         -moz-border-radius: 5px;
  23         -web-border-radius: 5px;
  24         background: #e7e8e2;
  25         border-radius: 5px;
  26         font-size: 16px;
  27       }
  28       .plaintext {
  29         background: #272822;
  30         color: #80ff80;
  31         text-shadow: 0 0 20px #333;
  32         padding: 2px 5px;
  33       }
  34       .ciphertext {
  35         background: #272822;
  36         color: #ff6666;
  37         text-shadow: 0 0 20px #333;
  38         padding: 2px 5px;
  39       }
  40        .float-right {
  41         float: right;
  42       }
  43     </style>
  44   </head>
  45   <body>
  46     <textarea id="source">
  47
  48 # Breaking caesar ciphers
  49
  50 ![center-aligned Caesar wheel](caesarwheel1.gif)
  51
  52 ---
  53
  54 # Human vs Machine
  55
  56 Slow but clever vs Dumb but fast
  57
  58 ## Human approach
  59
  60 Ciphertext | Plaintext
  61 ---|---
  62 ![left-aligned Ciphertext frequencies](c1a_frequency_histogram.png) | ![left-aligned English frequencies](english_frequency_histogram.png)
  63
  64 ---
  65
  66 # Human vs machine
  67
  68 ## Machine approach
  69
  70 Brute force.
  71
  72 Try all keys.
  73
  74 * How many keys to try?
  75
  76 ## Basic idea
  77
  78 ```
  79 for each key:
  80     decipher with this key
  81     how close is it to English?
  82     remember the best key
  83 ```
  84
  85 What steps do we know how to do?
  86
  87 ---
  88 # How close is it to English?
  89
  90 What does English look like?
  91
  92 * We need a model of English.
  93
  94 How do we define "closeness"?
  95
  96 ---
  97
  98 # What does English look like?
  99
 100 ## Abstraction: frequency of letter counts
 101
 102 Letter | Count
 103 -------|------
 104 a | 489107
 105 b | 92647
 106 c | 140497
 107 d | 267381
 108 e | 756288
 109 . | .
 110 . | .
 111 . | .
 112 z | 3575
 113
 114 One way of thinking about this is a 26-dimensional vector.
 115
 116 Create a vector of our text, and one of idealised English.
 117
 118 The distance between the vectors is how far from English the text is.
 119
 120 ---
 121
 122 # Frequencies of English
 123
 124 But before then how do we count the letters?
 125
 126 * Read a file into a string
 127 ```python
 128 open()
 129 read()
 130 ```
 131 * Count them
 132 ```python
 133 import collections
 134 ```
 135
 136 ---
 137
 138 # Canonical forms
 139
 140 Counting letters in _War and Peace_ gives all manner of junk.
 141
 142 * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
 143
 144 ---
 145
 146 # Vector distances
 147
 148 .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
 149
 150 Several different distance measures (__metrics__, also called __norms__):
 151
 152 * L<sub>2</sub> norm (Euclidean distance):
 153 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
 154
 155 * L<sub>1</sub> norm (Manhattan distance, taxicab distance):
 156 `\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
 157
 158 * L<sub>3</sub> norm:
 159 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
 160
 161 The higher the power used, the more weight is given to the largest differences in components.
 162
 163 (Extends out to:
 164
 165 * L<sub>0</sub> norm (Hamming distance):
 166 `$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
 167 \begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
 168  0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
 169
 170 * L<sub>&infin;</sub> norm:
 171 `\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
 172
 173 neither of which will be that useful.)
 174 ---
 175
 176 # Normalisation of vectors
 177
 178 Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
 179
 180 * Eucliean scaling (vector with unit length): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \sqrt{\mathbf{x}_1^2 + \mathbf{x}_2^2 + \mathbf{x}_3^2 + \dots } }$$`
 181
 182 * Normalisation (components of vector sum to 1): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \mathbf{x}_1 + \mathbf{x}_2 + \mathbf{x}_3 + \dots }$$`
 183
 184 ---
 185
 186 # Angle, not distance
 187
 188 Rather than looking at the distance between the vectors, look at the angle between them.
 189
 190 .float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
 191
 192 Vector dot product shows how much of one vector lies in the direction of another:
 193 `\( \mathbf{A} \bullet \mathbf{B} =
 194 \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
 195
 196 But,
 197 `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
 198 and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
 199
 200 A bit of rearranging give the cosine simiarity:
 201 `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
 202 \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
 203
 204 This is independent of vector lengths!
 205
 206 Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
 207
 208 ---
 209
 210 # An infinite number of monkeys
 211
 212 What is the probability that this string of letters is a sample of English?
 213
 214 Given 'th', 'e' is about six times more likely than 'a' or 'i'.
 215
 216 ## Naive Bayes, or the bag of letters
 217
 218 Ignore letter order, just treat each letter individually.
 219
 220 Probability of a text is `\( \prod_i p_i \)`
 221
 222 (Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
 223
 224 ---
 225
 226 # Which is best?
 227
 228    | Euclidean | Normalised
 229 ---|-----------|------------
 230 L1 |     x     |      x
 231 L2 |     x     |      x
 232 L3 |     x     |      x
 233 Cosine |     x     |      x
 234
 235 And the probability measure!
 236
 237 * Nine different ways of measuring fitness.
 238
 239 ## Computing is an empircal science
 240
 241
 242
 243     </textarea>
 244     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 245     </script>
 246
 247     <script type="text/javascript"
 248       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 249
 250     <script type="text/javascript">
 251       var slideshow = remark.create({ ratio: "16:9" });
 252
 253       // Setup MathJax
 254       MathJax.Hub.Config({
 255         tex2jax: {
 256         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 257         }
 258       });
 259       MathJax.Hub.Queue(function() {
 260         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 261             return(elem.SourceElement());
 262         }).parent().addClass('has-jax');
 263       });
 264       MathJax.Hub.Configured();
 265     </script>
 266   </body>
 267 </html>