4 <title>Breaking keyword ciphers
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
46 <textarea id=
"source">
48 # Breaking keyword ciphers
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
56 # Duplicate and extend your `affine_break()` function
58 * How to cycle through all the keys? What _are_ all the keys?
66 * `
2013/
4a.ciphertext`
67 * `
2013/
4b.ciphertext`
69 This will take a while. Fire up a system monitor. What's wrong?
73 # Python, threads, and the GIL
75 Thread-safe shared-memory code is hard.
77 Python's Global Interpreter Lock prevents shooting yourself in the foot.
79 Where you want true parallelism, need different threads (Python processes).
81 * Thread-safe shared-memory code is hard.
83 The `multiprocessing` library makes this easier.
85 But before we get there, a couple of diversions...
91 Three cipher breaking tasks so far.
93 All working on the same principle:
96 find a way to enumerate all the possible keys
97 initialise 'best so far'
99 decipher message with this key
101 if it's better than the best so far:
105 Repetition of code is a bad smell.
107 Separate the 'try all keys, keep the best' logic from the 'score this one key' logic.
113 A common task is to apply a function to each item in a sequence, returning a sequence of the results.
119 >>> map(double, [
1,
2,
3])
123 * `map()` is a higher-order function: its first argument is the function that's applied.
125 How can we use this for keyword cipher breaking?
129 # Mapping keyword decipherings
131 Define a function that takes a possible key (keyword and cipher type) and returns the key and its fitness.
133 * (Also pass in the message and the fitness function)
135 Use `map()` and `max()` to find the best key
141 How many arguments does this take?
143 How do you write a function that takes this many arguments?
149 ## Positional, keyword
151 * Common or garden parameters, as you're used to.
152 * `def keyword_encipher(message, keyword, Keyword_wrap_alphabet.from_a):`
155 * `def mean(x, *xs):`
157 First number goes in `x`, remaining go in the tuple `xs`
161 * `def myfunc(arg1=
0, **kwargs):`
163 `kwargs` will be a Dict of the remaining keywords (not `arg1`)
167 # Back to `multiprocessing`
169 What does `Pool.starmap()` do?
174 from multiprocessing import Pool
176 def keyword_break_mp(message, wordlist=keywords, fitness=Pletters, chunksize=
500):
177 helper_args = [??? for word in wordlist] # One tuple for each possible key
179 breaks = pool.starmap(keyword_break_worker, helper_args, chunksize)
180 return max(breaks, key=lambda k: k[
1])
182 def keyword_break_worker(???):
184 return (key, fitness)
187 * Gotcha: the function in `Pool.starmap()` must be defined at the top level
188 * This is definitely a
"feature"
192 # Performance and chunksize
194 Try the multiprocessing keyword break. Is it using all the resources?
196 Setting `chunksize` is an art.
198 ## Map-reduce as a general pattern for multiprocessing
201 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
204 <script type=
"text/javascript"
205 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
207 <script type=
"text/javascript">
208 var slideshow = remark.create({ ratio:
"16:9" });
213 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
216 MathJax.Hub.Queue(function() {
217 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
218 return(elem.SourceElement());
219 }).parent().addClass('has-jax');
221 MathJax.Hub.Configured();