Up to first breaking of caesar ciphers
[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 .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
201 3. Sort by count (`sorted(, key=)` ; `.items()`, `.keys()`, `.values()`, `.get()`)
202 4. Write counts to `count_1l.txt`
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
319 # Reading letter probabilities
320
321 1. Load the file `count_1l.txt` into a dict, with letters as keys.
322
323 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 }$$`
324 * Return a new dict
325 * Remember the doctest!
326
327 3. Create a dict `Pl` that gives the log probability of a letter
328
329 4. Create a function `Pletters` that gives the probability of an iterable of letters
330 * What preconditions should this function have?
331 * Remember the doctest!
332
333 ---
334
335 # Breaking caesar ciphers (at last!)
336
337 ## Remember the basic idea
338
339 ```
340 for each key:
341 decipher with this key
342 how close is it to English?
343 remember the best key
344 ```
345
346 Try it on the text in `2013/1a.ciphertext`. Does it work?
347
348 ---
349
350
351 </textarea>
352 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
353 </script>
354
355 <script type="text/javascript"
356 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
357
358 <script type="text/javascript">
359 var slideshow = remark.create({ ratio: "16:9" });
360
361 // Setup MathJax
362 MathJax.Hub.Config({
363 tex2jax: {
364 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
365 }
366 });
367 MathJax.Hub.Queue(function() {
368 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
369 return(elem.SourceElement());
370 }).parent().addClass('has-jax');
371 });
372 MathJax.Hub.Configured();
373 </script>
374 </body>
375 </html>