More on keyword breaking
[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 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>