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       .indexlink {
  41         position: absolute;
  42         bottom: 1em;
  43         left: 1em;
  44       }
  45        .float-right {
  46         float: right;
  47       }
  48     </style>
  49   </head>
  50   <body>
  51     <textarea id="source">
  52
  53 # Breaking caesar ciphers
  54
  55 ![center-aligned Caesar wheel](caesarwheel1.gif)
  56
  57 ---
  58
  59 layout: true
  60
  61 .indexlink[[Index](index.html)]
  62
  63 ---
  64
  65 # Human vs Machine
  66
  67 Slow but clever vs Dumb but fast
  68
  69 ## Human approach
  70
  71 Ciphertext | Plaintext
  72 ---|---
  73 ![left-aligned Ciphertext frequencies](c1a_frequency_histogram.png) | ![left-aligned English frequencies](english_frequency_histogram.png)
  74
  75 ---
  76
  77 # Human vs machine
  78
  79 ## Machine approach
  80
  81 Brute force.
  82
  83 Try all keys.
  84
  85 * How many keys to try?
  86
  87 ## Basic idea
  88
  89 ```
  90 for each key:
  91     decipher with this key
  92     how close is it to English?
  93     remember the best key
  94 ```
  95
  96 What steps do we know how to do?
  97
  98 ---
  99 # How close is it to English?
 100
 101 What does English look like?
 102
 103 * We need a model of English.
 104
 105 How do we define "closeness"?
 106
 107 ## Here begineth the yak shaving
 108
 109 ---
 110
 111 # What does English look like?
 112
 113 ## Abstraction: frequency of letter counts
 114
 115 .float-right[![right-aligned Letter frequencies](letter-frequency-treemap.png)]
 116
 117 Letter | Count
 118 -------|------
 119 a | 489107
 120 b | 92647
 121 c | 140497
 122 d | 267381
 123 e | 756288
 124 . | .
 125 . | .
 126 . | .
 127 z | 3575
 128
 129 Use this to predict the probability of each letter, and hence the probability of a sequence of letters.
 130
 131 ---
 132
 133 .float-right[![right-aligned Typing monkey](typingmonkeylarge.jpg)]
 134
 135 # Naive Bayes, or the bag of letters
 136
 137 What is the probability that this string of letters is a sample of English?
 138
 139 Ignore letter order, just treat each letter individually.
 140
 141 Probability of a text is `\( \prod_i p_i \)`
 142
 143 Letter      | h       | e       | l       | l       | o       | hello
 144 ------------|---------|---------|---------|---------|---------|-------
 145 Probability | 0.06645 | 0.12099 | 0.04134 | 0.04134 | 0.08052 | 1.10648239 × 10<sup>-6</sup>
 146
 147 Letter      | i       | f       | m       | m       | p       | ifmmp
 148 ------------|---------|---------|---------|---------|---------|-------
 149 Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 × 10<sup>-8</sup>
 150
 151 (Implmentation issue: this can often underflow, so we rephrase it as `\( \sum_i \log p_i \)`)
 152
 153 Letter      | h       | e       | l       | l       | o       | hello
 154 ------------|---------|---------|---------|---------|---------|-------
 155 Probability | -1.1774 | -0.9172 | -1.3836 | -1.3836 | -1.0940 | -5.956055
 156
 157
 158 ---
 159
 160 # Frequencies of English
 161
 162 But before then how do we count the letters?
 163
 164 * Read a file into a string
 165 ```python
 166 open()
 167 .read()
 168 ```
 169 * Count them
 170 ```python
 171 import collections
 172 collections.Counter()
 173 ```
 174
 175 Create the `language_models.py` file for this.
 176
 177 ---
 178
 179 # Canonical forms
 180
 181 Counting letters in _War and Peace_ gives all manner of junk.
 182
 183 * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
 184
 185 ```python
 186 [l.lower() for l in text if ...]
 187 ```
 188 ---
 189
 190 # Accents
 191
 192 ```python
 193 >>> 'é' in string.ascii_letters
 194 >>> 'e' in string.ascii_letters
 195 ```
 196
 197 ## Unicode, combining codepoints, and normal forms
 198
 199 Text encodings will bite you when you least expect it.
 200
 201 - **é** : LATIN SMALL LETTER E WITH ACUTE (U+00E9)
 202
 203 - **e** + **&nbsp;&#x301;** : LATIN SMALL LETTER E (U+0065) + COMBINING ACUTE ACCENT (U+0301)
 204
 205 * urlencoding is the other pain point.
 206
 207 ---
 208
 209 # Five minutes on StackOverflow later...
 210
 211 ```python
 212 import unicodedata
 213
 214 def unaccent(text):
 215     """Remove all accents from letters.
 216     It does this by converting the unicode string to decomposed compatibility
 217     form, dropping all the combining accents, then re-encoding the bytes.
 218
 219     >>> unaccent('hello')
 220     'hello'
 221     >>> unaccent('HELLO')
 222     'HELLO'
 223     >>> unaccent('héllo')
 224     'hello'
 225     >>> unaccent('héllö')
 226     'hello'
 227     >>> unaccent('HÉLLÖ')
 228     'HELLO'
 229     """
 230     return unicodedata.normalize('NFKD', text).\
 231         encode('ascii', 'ignore').\
 232         decode('utf-8')
 233 ```
 234
 235 ---
 236
 237 # Find the frequencies of letters in English
 238
 239 1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`.
 240 2. Find the frequencies (`.update()`)
 241 3. Sort by count (read the docs...)
 242 4. Write counts to `count_1l.txt`
 243 ```python
 244 with open('count_1l.txt', 'w') as f:
 245     for each letter...:
 246         f.write('text\t{}\n'.format(count))
 247 ```
 248
 249 ---
 250
 251 # Reading letter probabilities
 252
 253 1. Load the file `count_1l.txt` into a dict, with letters as keys.
 254
 255 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 }$$`
 256     * Return a new dict
 257     * Remember the doctest!
 258
 259 3. Create a dict `Pl` that gives the log probability of a letter
 260
 261 4. Create a function `Pletters` that gives the probability of an iterable of letters
 262     * What preconditions should this function have?
 263     * Remember the doctest!
 264
 265 ---
 266
 267 # Breaking caesar ciphers
 268
 269 New file: `cipherbreak.py`
 270
 271 ## Remember the basic idea
 272
 273 ```
 274 for each key:
 275     decipher with this key
 276     how close is it to English?
 277     remember the best key
 278 ```
 279
 280 Try it on the text in `2013/1a.ciphertext`. Does it work?
 281
 282 ---
 283
 284 # Aside: Logging
 285
 286 Better than scattering `print()`statements through your code
 287
 288 ```python
 289 import logging
 290
 291 logger = logging.getLogger(__name__)
 292 logger.addHandler(logging.FileHandler('cipher.log'))
 293 logger.setLevel(logging.WARNING)
 294
 295         logger.debug('Caesar break attempt using key {0} gives fit of {1} '
 296                       'and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
 297
 298 ```
 299 * Yes, it's ugly.
 300
 301 Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
 302
 303 Use `logger.debug()`, `logger.info()`, etc. to log a message.
 304
 305 ---
 306
 307 # Homework: how much ciphertext do we need?
 308
 309 ## Let's do an experiment to find out
 310
 311 1. Load the whole corpus into a string (sanitised)
 312 2. Select a random chunk of plaintext and a random key
 313 3. Encipher the text
 314 4. Score 1 point if `caesar_cipher_break()` recovers the correct key
 315 5. Repeat many times and with many plaintext lengths
 316
 317 ```python
 318 import csv
 319
 320 def show_results():
 321     with open('caesar_break_parameter_trials.csv', 'w') as f:
 322         writer = csv.DictWriter(f, ['name'] + message_lengths,
 323             quoting=csv.QUOTE_NONNUMERIC)
 324         writer.writeheader()
 325         for scoring in sorted(scores.keys()):
 326             scores[scoring]['name'] = scoring
 327             writer.writerow(scores[scoring])
 328 ```
 329
 330     </textarea>
 331     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 332     </script>
 333
 334     <script type="text/javascript"
 335       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 336
 337     <script type="text/javascript">
 338       var slideshow = remark.create({ ratio: "16:9" });
 339
 340       // Setup MathJax
 341       MathJax.Hub.Config({
 342         tex2jax: {
 343         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 344         }
 345       });
 346       MathJax.Hub.Queue(function() {
 347         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 348             return(elem.SourceElement());
 349         }).parent().addClass('has-jax');
 350       });
 351       MathJax.Hub.Configured();
 352     </script>
 353   </body>
 354 </html>