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 Use `logger.debug()`, `logger.info()`, etc. to log a message.
 279
 280 ---
 281
 282 # How much ciphertext do we need?
 283
 284 ## Let's do an experiment to find out
 285
 286 1. Load the whole corpus into a string (sanitised)
 287 2. Select a random chunk of plaintext and a random key
 288 3. Encipher the text
 289 4. Score 1 point if `caesar_cipher_break()` recovers the correct key
 290 5. Repeat many times and with many plaintext lengths
 291
 292
 293     </textarea>
 294     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 295     </script>
 296
 297     <script type="text/javascript"
 298       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 299
 300     <script type="text/javascript">
 301       var slideshow = remark.create({ ratio: "16:9" });
 302
 303       // Setup MathJax
 304       MathJax.Hub.Config({
 305         tex2jax: {
 306         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 307         }
 308       });
 309       MathJax.Hub.Queue(function() {
 310         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 311             return(elem.SourceElement());
 312         }).parent().addClass('has-jax');
 313       });
 314       MathJax.Hub.Configured();
 315     </script>
 316   </body>
 317 </html>