Added transposition cipher slides
[cipher-training.git] / slides / keyword-break.html
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <title>Breaking keyword 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 keyword ciphers
49
50 a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
51 --|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
52 k | e | y | w | o | r | d | a | b | c | f | g | h | i | j | l | m | n | p | q | s | t | u | v | x | z
53
54 ---
55
56 # Duplicate and extend your `affine_break()` function
57
58 * How to cycle through all the keys? What _are_ all the keys?
59
60 * Look at `words.txt`
61
62 ---
63
64 # Test it.
65
66 * `2013/4a.ciphertext`
67 * `2013/4b.ciphertext`
68
69 This will take a while. Fire up a system monitor. What's wrong?
70
71 ---
72
73 # Python, threads, and the GIL
74
75 Thread-safe shared-memory code is hard.
76
77 Python's Global Interpreter Lock prevents shooting yourself in the foot.
78
79 Where you want true parallelism, need different threads (Python processes).
80
81 * Thread-safe shared-memory code is hard.
82
83 The `multiprocessing` library makes this easier.
84
85 But before we get there, a couple of diversions...
86
87 ---
88
89 # map()
90
91 A common task is to apply a function to each item in a sequence, returning a sequence of the results.
92
93 ```python
94 def double(x):
95 return x * 2
96
97 >>> map(double, [1,2,3])
98 [2,4,6]
99 ```
100
101 * `map()` is a higher-order function: its first argument is the function that's applied.
102
103 How can we use this for keyword cipher breaking?
104
105 ---
106
107 # Mapping keyword decipherings
108
109 Define a function that takes a possible key (keyword and cipher type) and returns the key and its fitness.
110
111 * (Also pass in the message and the fitness function)
112
113 Use `map()` and `max()` to find the best key
114
115 ---
116
117 # Arity of print()
118
119 How many arguments does this take?
120
121 How do you write a function that takes this many arguments?
122
123 ---
124
125 # Function arguments
126
127 ## Positional, keyword
128
129 * Common or garden parameters, as you're used to.
130 * `def keyword_encipher(message, keyword, Keyword_wrap_alphabet.from_a):`
131
132 ## Excess positional
133 * `def mean(x, *xs):`
134
135 First number goes in `x`, remaining go in the tuple `xs`
136
137 ## Excess keyword
138
139 * `def myfunc(arg1=0, **kwargs):`
140
141 `kwargs` will be a Dict of the remaining keywords (not `arg1`)
142
143 ---
144
145 # Back to `multiprocessing`
146
147 What does `Pool.starmap()` do?
148
149 ---
150
151 ```python
152 from multiprocessing import Pool
153
154 def keyword_break_mp(message, wordlist=keywords, fitness=Pletters, chunksize=500):
155 helper_args = [??? for word in wordlist] # One tuple for each possible key
156 with Pool() as pool:
157 breaks = pool.starmap(keyword_break_worker, helper_args, chunksize)
158 return max(breaks, key=lambda k: k[1])
159
160 def keyword_break_worker(???):
161 ???
162 return (key, fitness)
163 ```
164
165 * Gotcha: the function in `Pool.starmap()` must be defined at the top level
166 * This is definitely a "feature"
167
168 ---
169
170 # Performance and chunksize
171
172 Try the multiprocessing keyword break. Is it using all the resources?
173
174 Setting `chunksize` is an art.
175
176 ## Map-reduce as a general pattern for multiprocessing
177
178 </textarea>
179 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
180 </script>
181
182 <script type="text/javascript"
183 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
184
185 <script type="text/javascript">
186 var slideshow = remark.create({ ratio: "16:9" });
187
188 // Setup MathJax
189 MathJax.Hub.Config({
190 tex2jax: {
191 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
192 }
193 });
194 MathJax.Hub.Queue(function() {
195 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
196 return(elem.SourceElement());
197 }).parent().addClass('has-jax');
198 });
199 MathJax.Hub.Configured();
200 </script>
201 </body>
202 </html>