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 Use this to predict the probability of each letter, and hence the probability of a sequence of letters.
 115
 116 ---
 117
 118 # An infinite number of monkeys
 119
 120 What is the probability that this string of letters is a sample of English?
 121
 122 ## Naive Bayes, or the bag of letters
 123
 124 Ignore letter order, just treat each letter individually.
 125
 126 Probability of a text is `\( \prod_i p_i \)`
 127
 128 Letter      | h       | e       | l       | l       | o       | hello
 129 ------------|---------|---------|---------|---------|---------|-------
 130 Probability | 0.06645 | 0.12099 | 0.04134 | 0.04134 | 0.08052 | 1.10648239 × 10<sup>-6</sup>
 131
 132 Letter      | i       | f       | m       | m       | p       | ifmmp
 133 ------------|---------|---------|---------|---------|---------|-------
 134 Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 × 10<sup>-8</sup>
 135
 136 (Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
 137
 138 Letter      | h       | e       | l       | l       | o       | hello
 139 ------------|---------|---------|---------|---------|---------|-------
 140 Probability | -1.1774 | -0.9172 | -1.3836 | -1.3836 | -1.0940 | -5.956055
 141
 142
 143 ---
 144
 145 # Frequencies of English
 146
 147 But before then how do we count the letters?
 148
 149 * Read a file into a string
 150 ```python
 151 open()
 152 .read()
 153 ```
 154 * Count them
 155 ```python
 156 import collections
 157 ```
 158
 159 Create the `language_models.py` file for this.
 160
 161 ---
 162
 163 # Canonical forms
 164
 165 Counting letters in _War and Peace_ gives all manner of junk.
 166
 167 * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
 168
 169 ```python
 170 [l.lower() for l in text if ...]
 171 ```
 172 ---
 173
 174 # Accents
 175
 176 ```python
 177 >>> 'é' in string.ascii_letters
 178 >>> 'e' in string.ascii_letters
 179 ```
 180
 181 ## Unicode, combining codepoints, and normal forms
 182
 183 Text encodings will bite you when you least expect it.
 184
 185 - **é** : LATIN SMALL LETTER E WITH ACUTE (U+00E9)
 186
 187 - **e** + **&nbsp;&#x301;** : LATIN SMALL LETTER E (U+0065) + COMBINING ACUTE ACCENT (U+0301)
 188
 189 * urlencoding is the other pain point.
 190
 191 ---
 192
 193 # Five minutes on StackOverflow later...
 194
 195 ```python
 196 def unaccent(text):
 197     """Remove all accents from letters.
 198     It does this by converting the unicode string to decomposed compatibility
 199     form, dropping all the combining accents, then re-encoding the bytes.
 200
 201     >>> unaccent('hello')
 202     'hello'
 203     >>> unaccent('HELLO')
 204     'HELLO'
 205     >>> unaccent('héllo')
 206     'hello'
 207     >>> unaccent('héllö')
 208     'hello'
 209     >>> unaccent('HÉLLÖ')
 210     'HELLO'
 211     """
 212     return unicodedata.normalize('NFKD', text).\
 213         encode('ascii', 'ignore').\
 214         decode('utf-8')
 215 ```
 216
 217 ---
 218
 219 # Find the frequencies of letters in English
 220
 221 1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`.
 222 2. Find the frequencies (`.update()`)
 223 3. Sort by count
 224 4. Write counts to `count_1l.txt` (`'text{}\n'.format()`)
 225
 226 ---
 227
 228 # Reading letter probabilities
 229
 230 1. Load the file `count_1l.txt` into a dict, with letters as keys.
 231
 232 2. Normalise the counts (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 }$$`
 233     * Return a new dict
 234     * Remember the doctest!
 235
 236 3. Create a dict `Pl` that gives the log probability of a letter
 237
 238 4. Create a function `Pletters` that gives the probability of an iterable of letters
 239     * What preconditions should this function have?
 240     * Remember the doctest!
 241
 242 ---
 243
 244 # Breaking caesar ciphers
 245
 246 ## Remember the basic idea
 247
 248 ```
 249 for each key:
 250     decipher with this key
 251     how close is it to English?
 252     remember the best key
 253 ```
 254
 255 Try it on the text in `2013/1a.ciphertext`. Does it work?
 256
 257 ---
 258
 259 # Aside: Logging
 260
 261 Better than scattering `print()`statements through your code
 262
 263 ```python
 264 import logging
 265
 266 logger = logging.getLogger(__name__)
 267 logger.addHandler(logging.FileHandler('cipher.log'))
 268 logger.setLevel(logging.WARNING)
 269
 270         logger.debug('Caesar break attempt using key {0} gives fit of {1} '
 271                       'and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
 272
 273 ```
 274  * Yes, it's ugly.
 275
 276  Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
 277
 278 ---
 279
 280 # Back to frequency of letter counts
 281
 282 Letter | Count
 283 -------|------
 284 a | 489107
 285 b | 92647
 286 c | 140497
 287 d | 267381
 288 e | 756288
 289 . | .
 290 . | .
 291 . | .
 292 z | 3575
 293
 294 Another way of thinking about this is a 26-dimensional vector.
 295
 296 Create a vector of our text, and one of idealised English.
 297
 298 The distance between the vectors is how far from English the text is.
 299
 300 ---
 301
 302 # Vector distances
 303
 304 .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
 305
 306 Several different distance measures (__metrics__, also called __norms__):
 307
 308 * L<sub>2</sub> norm (Euclidean distance):
 309 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
 310
 311 * L<sub>1</sub> norm (Manhattan distance, taxicab distance):
 312 `\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
 313
 314 * L<sub>3</sub> norm:
 315 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
 316
 317 The higher the power used, the more weight is given to the largest differences in components.
 318
 319 (Extends out to:
 320
 321 * L<sub>0</sub> norm (Hamming distance):
 322 `$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
 323 \begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
 324  0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
 325
 326 * L<sub>&infin;</sub> norm:
 327 `\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
 328
 329 neither of which will be that useful here, but they keep cropping up.)
 330 ---
 331
 332 # Normalisation of vectors
 333
 334 Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
 335
 336 * 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 } }$$`
 337
 338 * 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 }$$`
 339
 340 ---
 341
 342 # Angle, not distance
 343
 344 Rather than looking at the distance between the vectors, look at the angle between them.
 345
 346 .float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
 347
 348 Vector dot product shows how much of one vector lies in the direction of another:
 349 `\( \mathbf{A} \bullet \mathbf{B} =
 350 \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
 351
 352 But,
 353 `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
 354 and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
 355
 356 A bit of rearranging give the cosine simiarity:
 357 `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
 358 \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
 359
 360 This is independent of vector lengths!
 361
 362 Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
 363
 364 ---
 365
 366 # Which is best?
 367
 368    | Euclidean | Normalised
 369 ---|-----------|------------
 370 L1 |     x     |      x
 371 L2 |     x     |      x
 372 L3 |     x     |      x
 373 Cosine |     x     |      x
 374
 375 And the probability measure!
 376
 377 * Nine different ways of measuring fitness.
 378
 379 ## Computing is an empircal science
 380
 381 Let's do some experiments to find the best solution!
 382
 383 ---
 384
 385 # Experimental harness
 386
 387 ## Step 1: build some other scoring functions
 388
 389 We need a way of passing the different functions to the keyfinding function.
 390
 391 ## Step 2: find the best scoring function
 392
 393 Try them all on random ciphertexts, see which one works best.
 394
 395 ---
 396
 397 # Functions are values!
 398
 399 ```python
 400 >>> Pletters
 401 <function Pletters at 0x7f60e6d9c4d0>
 402 ```
 403
 404 ```python
 405 def caesar_break(message, fitness=Pletters):
 406     """Breaks a Caesar cipher using frequency analysis
 407 ...
 408     for shift in range(26):
 409         plaintext = caesar_decipher(message, shift)
 410         fit = fitness(plaintext)
 411 ```
 412
 413 ---
 414
 415 # Changing the comparison function
 416
 417 * Must be a function that takes a text and returns a score
 418     * Better fit must give higher score, opposite of the vector distance norms
 419
 420 ```python
 421 def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert):
 422     def frequency_compare(text):
 423         ...
 424         return score
 425     return frequency_compare
 426 ```
 427
 428 ---
 429
 430 # Data-driven processing
 431
 432 ```python
 433 metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'},
 434     {'func': norms.l2, 'invert': True, 'name': 'l2'},
 435     {'func': norms.l3, 'invert': True, 'name': 'l3'},
 436     {'func': norms.cosine_similarity, 'invert': False, 'name': 'cosine_similarity'}]
 437 scalings = [{'corpus_frequency': normalised_english_counts,
 438          'scaling': norms.normalise,
 439          'name': 'normalised'},
 440         {'corpus_frequency': euclidean_scaled_english_counts,
 441          'scaling': norms.euclidean_scale,
 442          'name': 'euclidean_scaled'}]
 443 ```
 444
 445 Use this to make all nine scoring functions.
 446
 447
 448     </textarea>
 449     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 450     </script>
 451
 452     <script type="text/javascript"
 453       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 454
 455     <script type="text/javascript">
 456       var slideshow = remark.create({ ratio: "16:9" });
 457
 458       // Setup MathJax
 459       MathJax.Hub.Config({
 460         tex2jax: {
 461         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 462         }
 463       });
 464       MathJax.Hub.Queue(function() {
 465         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 466             return(elem.SourceElement());
 467         }).parent().addClass('has-jax');
 468       });
 469       MathJax.Hub.Configured();
 470     </script>
 471   </body>
 472 </html>