Deleted unnecessary files
[cipher-training.git] / 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>