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 Create the `language_models.py` file for this.
 137
 138 ---
 139
 140 # Canonical forms
 141
 142 Counting letters in _War and Peace_ gives all manner of junk.
 143
 144 * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
 145
 146 ```python
 147 [l.lower() for l in text if ...]
 148 ```
 149 ---
 150
 151
 152 # Accents
 153
 154 ```python
 155 >>> 'é' in string.ascii_letters
 156 >>> 'e' in string.ascii_letters
 157 ```
 158
 159 ## Unicode, combining codepoints, and normal forms
 160
 161 Text encodings will bite you when you least expect it.
 162
 163 - **é** : LATIN SMALL LETTER E WITH ACUTE (U+00E9)
 164
 165 - **e** + **&nbsp;&#x301;** : LATIN SMALL LETTER E (U+0065) + COMBINING ACUTE ACCENT (U+0301)
 166
 167 * urlencoding is the other pain point.
 168
 169 ---
 170
 171 # Five minutes on StackOverflow later...
 172
 173 ```python
 174 def unaccent(text):
 175     """Remove all accents from letters.
 176     It does this by converting the unicode string to decomposed compatibility
 177     form, dropping all the combining accents, then re-encoding the bytes.
 178
 179     >>> unaccent('hello')
 180     'hello'
 181     >>> unaccent('HELLO')
 182     'HELLO'
 183     >>> unaccent('héllo')
 184     'hello'
 185     >>> unaccent('héllö')
 186     'hello'
 187     >>> unaccent('HÉLLÖ')
 188     'HELLO'
 189     """
 190     return unicodedata.normalize('NFKD', text).\
 191         encode('ascii', 'ignore').\
 192         decode('utf-8')
 193 ```
 194
 195 ---
 196
 197 # Find the frequencies of letters in English
 198
 199 1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`.
 200 2. Find the frequencies (`.update()`)
 201 3. Sort by count
 202 4. Write counts to `count_1l.txt` (`'text{}\n'.format()`)
 203
 204 ---
 205
 206 # Vector distances
 207
 208 .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
 209
 210 Several different distance measures (__metrics__, also called __norms__):
 211
 212 * L<sub>2</sub> norm (Euclidean distance):
 213 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
 214
 215 * L<sub>1</sub> norm (Manhattan distance, taxicab distance):
 216 `\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
 217
 218 * L<sub>3</sub> norm:
 219 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
 220
 221 The higher the power used, the more weight is given to the largest differences in components.
 222
 223 (Extends out to:
 224
 225 * L<sub>0</sub> norm (Hamming distance):
 226 `$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
 227 \begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
 228  0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
 229
 230 * L<sub>&infin;</sub> norm:
 231 `\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
 232
 233 neither of which will be that useful here, but they keep cropping up.)
 234 ---
 235
 236 # Normalisation of vectors
 237
 238 Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
 239
 240 * 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 } }$$`
 241
 242 * 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 }$$`
 243
 244 ---
 245
 246 # Angle, not distance
 247
 248 Rather than looking at the distance between the vectors, look at the angle between them.
 249
 250 .float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
 251
 252 Vector dot product shows how much of one vector lies in the direction of another:
 253 `\( \mathbf{A} \bullet \mathbf{B} =
 254 \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
 255
 256 But,
 257 `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
 258 and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
 259
 260 A bit of rearranging give the cosine simiarity:
 261 `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
 262 \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
 263
 264 This is independent of vector lengths!
 265
 266 Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
 267
 268 ---
 269
 270 # An infinite number of monkeys
 271
 272 What is the probability that this string of letters is a sample of English?
 273
 274 Given 'th', 'e' is about six times more likely than 'a' or 'i'.
 275
 276 ## Naive Bayes, or the bag of letters
 277
 278 Ignore letter order, just treat each letter individually.
 279
 280 Probability of a text is `\( \prod_i p_i \)`
 281
 282 (Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
 283
 284 ---
 285
 286 # Which is best?
 287
 288    | Euclidean | Normalised
 289 ---|-----------|------------
 290 L1 |     x     |      x
 291 L2 |     x     |      x
 292 L3 |     x     |      x
 293 Cosine |     x     |      x
 294
 295 And the probability measure!
 296
 297 * Nine different ways of measuring fitness.
 298
 299 ## Computing is an empircal science
 300
 301 Let's do some experiments to find the best solution!
 302
 303 ---
 304
 305 ## Step 1: get **some** codebreaking working
 306
 307 Let's start with the letter probability norm, because it's easy.
 308
 309 ## Step 2: build some other scoring functions
 310
 311 We also need a way of passing the different functions to the keyfinding function.
 312
 313 ## Step 3: find the best scoring function
 314
 315 Try them all on random ciphertexts, see which one works best.
 316
 317
 318     </textarea>
 319     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 320     </script>
 321
 322     <script type="text/javascript"
 323       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 324
 325     <script type="text/javascript">
 326       var slideshow = remark.create({ ratio: "16:9" });
 327
 328       // Setup MathJax
 329       MathJax.Hub.Config({
 330         tex2jax: {
 331         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 332         }
 333       });
 334       MathJax.Hub.Queue(function() {
 335         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 336             return(elem.SourceElement());
 337         }).parent().addClass('has-jax');
 338       });
 339       MathJax.Hub.Configured();
 340     </script>
 341   </body>
 342 </html>