5 from itertools
import zip_longest
, cycle
, permutations
6 from segment
import segment
7 from multiprocessing
import Pool
10 import matplotlib
.pyplot
as plt
13 from language_models
import *
18 # c5a = open('2012/5a.ciphertext', 'r').read()
19 # timeit.timeit('keyword_break(c5a)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break', number=1)
20 # timeit.repeat('keyword_break_mp(c5a, chunksize=500)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break_mp', repeat=5, number=1)
22 transpositions
= collections
.defaultdict(list)
24 transpositions
[transpositions_of(word
)] += [word
]
26 def frequencies(text
):
27 """Count the number of occurrences of each character in text
29 >>> sorted(frequencies('abcdefabc').items())
30 [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
31 >>> sorted(frequencies('the quick brown fox jumped over the lazy ' \
32 'dog').items()) # doctest: +NORMALIZE_WHITESPACE
33 [(' ', 8), ('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1),
34 ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1),
35 ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2),
36 ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
37 >>> sorted(frequencies('The Quick BROWN fox jumped! over... the ' \
38 '(9lazy) DOG').items()) # doctest: +NORMALIZE_WHITESPACE
39 [(' ', 8), ('!', 1), ('(', 1), (')', 1), ('.', 3), ('9', 1), ('B', 1),
40 ('D', 1), ('G', 1), ('N', 1), ('O', 2), ('Q', 1), ('R', 1), ('T', 1),
41 ('W', 1), ('a', 1), ('c', 1), ('d', 1), ('e', 4), ('f', 1), ('h', 2),
42 ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('o', 2), ('p', 1),
43 ('r', 1), ('t', 1), ('u', 2), ('v', 1), ('x', 1), ('y', 1), ('z', 1)]
44 >>> sorted(frequencies(sanitise('The Quick BROWN fox jumped! over... ' \
45 'the (9lazy) DOG')).items()) # doctest: +NORMALIZE_WHITESPACE
46 [('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1),
47 ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1),
48 ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1),
49 ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
50 >>> frequencies('abcdefabcdef')['x']
53 return collections
.Counter(c
for c
in text
)
56 def caesar_break(message
, fitness
=Pletters
):
57 """Breaks a Caesar cipher using frequency analysis
59 >>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrh' \
60 'ecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm') # doctest: +ELLIPSIS
61 (4, -130.849989015...)
62 >>> caesar_break('wxwmaxdgheetgwuxztgptedbgznitgwwhpguxyhkxbmhvvtlbhgtee' \
63 'raxlmhiixweblmxgxwmhmaxybkbgztgwztsxwbgmxgmert') # doctest: +ELLIPSIS
64 (19, -128.82410410...)
65 >>> caesar_break('yltbbqnqnzvguvaxurorgenafsbezqvagbnornfgsbevpnaabjurer' \
66 'svaquvzyvxrnznazlybequrvfohgriraabjtbaruraprur') # doctest: +ELLIPSIS
67 (13, -126.25403935...)
69 sanitised_message
= sanitise(message
)
71 best_fit
= float('-inf')
72 for shift
in range(26):
73 plaintext
= caesar_decipher(sanitised_message
, shift
)
74 fit
= fitness(plaintext
)
75 logger
.debug('Caesar break attempt using key {0} gives fit of {1} '
76 'and decrypt starting: {2}'.format(shift
, fit
, plaintext
[:50]))
80 logger
.info('Caesar break best fit: key {0} gives fit of {1} and '
81 'decrypt starting: {2}'.format(best_shift
, best_fit
,
82 caesar_decipher(sanitised_message
, best_shift
)[:50]))
83 return best_shift
, best_fit
85 def affine_break(message
, fitness
=Pletters
):
86 """Breaks an affine cipher using frequency analysis
88 >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls ' \
89 'omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ' \
90 'ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ' \
91 'ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls ' \
92 'bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai ' \
93 'kxd clm ckuxj.') # doctest: +ELLIPSIS
94 ((15, 22, True), -340.601181913...)
96 sanitised_message
= sanitise(message
)
100 best_fit
= float("-inf")
101 for one_based
in [True, False]:
102 for multiplier
in [x
for x
in range(1, 26, 2) if x
!= 13]:
103 for adder
in range(26):
104 plaintext
= affine_decipher(sanitised_message
,
105 multiplier
, adder
, one_based
)
106 fit
= fitness(plaintext
)
107 logger
.debug('Affine break attempt using key {0}x+{1} ({2}) '
108 'gives fit of {3} and decrypt starting: {4}'.
109 format(multiplier
, adder
, one_based
, fit
,
113 best_multiplier
= multiplier
115 best_one_based
= one_based
116 logger
.info('Affine break best fit with key {0}x+{1} ({2}) gives fit of {3} '
117 'and decrypt starting: {4}'.format(
118 best_multiplier
, best_adder
, best_one_based
, best_fit
,
119 affine_decipher(sanitised_message
, best_multiplier
,
120 best_adder
, best_one_based
)[:50]))
121 return (best_multiplier
, best_adder
, best_one_based
), best_fit
123 def keyword_break(message
, wordlist
=keywords
, fitness
=Pletters
):
124 """Breaks a keyword substitution cipher using a dictionary and
127 >>> keyword_break(keyword_encipher('this is a test message for the ' \
128 'keyword decipherment', 'elephant', 1), \
129 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
130 (('elephant', 1), -52.834575011...)
133 best_wrap_alphabet
= True
134 best_fit
= float("-inf")
135 for wrap_alphabet
in range(3):
136 for keyword
in wordlist
:
137 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
138 fit
= fitness(plaintext
)
139 logger
.debug('Keyword break attempt using key {0} (wrap={1}) '
140 'gives fit of {2} and decrypt starting: {3}'.format(
141 keyword
, wrap_alphabet
, fit
,
142 sanitise(plaintext
)[:50]))
145 best_keyword
= keyword
146 best_wrap_alphabet
= wrap_alphabet
147 logger
.info('Keyword break best fit with key {0} (wrap={1}) gives fit of '
148 '{2} and decrypt starting: {3}'.format(best_keyword
,
149 best_wrap_alphabet
, best_fit
, sanitise(
150 keyword_decipher(message
, best_keyword
,
151 best_wrap_alphabet
))[:50]))
152 return (best_keyword
, best_wrap_alphabet
), best_fit
154 def keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
, chunksize
=500):
155 """Breaks a keyword substitution cipher using a dictionary and
158 >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \
159 'keyword decipherment', 'elephant', 1), \
160 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
161 (('elephant', 1), -52.834575011...)
164 helper_args
= [(message
, word
, wrap
, fitness
)
165 for word
in wordlist
for wrap
in range(3)]
166 # Gotcha: the helper function here needs to be defined at the top level
167 # (limitation of Pool.starmap)
168 breaks
= pool
.starmap(keyword_break_worker
, helper_args
, chunksize
)
169 return max(breaks
, key
=lambda k
: k
[1])
171 def keyword_break_worker(message
, keyword
, wrap_alphabet
, fitness
):
172 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
173 fit
= fitness(plaintext
)
174 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
175 '{2} and decrypt starting: {3}'.format(keyword
,
176 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
177 return (keyword
, wrap_alphabet
), fit
179 def scytale_break(message
, fitness
=Pbigrams
):
180 """Breaks a Scytale cipher
182 >>> scytale_break('tfeulchtrtteehwahsdehneoifeayfsondmwpltmaoalhikotoere' \
183 'dcweatehiplwxsnhooacgorrcrcraotohsgullasenylrendaianeplscdriioto' \
184 'aek') # doctest: +ELLIPSIS
185 (6, -281.276219108...)
188 best_fit
= float("-inf")
189 for key
in range(1, 20):
190 if len(message
) % key
== 0:
191 plaintext
= scytale_decipher(message
, key
)
192 fit
= fitness(sanitise(plaintext
))
193 logger
.debug('Scytale break attempt using key {0} gives fit of '
194 '{1} and decrypt starting: {2}'.format(key
,
195 fit
, sanitise(plaintext
)[:50]))
199 logger
.info('Scytale break best fit with key {0} gives fit of {1} and '
200 'decrypt starting: {2}'.format(best_key
, best_fit
,
201 sanitise(scytale_decipher(message
, best_key
))[:50]))
202 return best_key
, best_fit
205 def column_transposition_break_mp(message
, translist
=transpositions
,
206 fitness
=Pbigrams
, chunksize
=500):
207 """Breaks a column transposition cipher using a dictionary and
208 n-gram frequency analysis
210 # >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
211 # "It is a truth universally acknowledged, that a single man in \
212 # possession of a good fortune, must be in want of a wife. However \
213 # little known the feelings or views of such a man may be on his \
214 # first entering a neighbourhood, this truth is so well fixed in the \
215 # minds of the surrounding families, that he is considered the \
216 # rightful property of some one or other of their daughters."), \
218 # translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
219 # (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
220 # (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
221 # (((2, 0, 5, 3, 1, 4, 6), False), 0.0628106372...)
222 # >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
223 # "It is a truth universally acknowledged, that a single man in \
224 # possession of a good fortune, must be in want of a wife. However \
225 # little known the feelings or views of such a man may be on his \
226 # first entering a neighbourhood, this truth is so well fixed in the \
227 # minds of the surrounding families, that he is considered the \
228 # rightful property of some one or other of their daughters."), \
230 # translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
231 # (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
232 # (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
233 # target_counts=normalised_english_trigram_counts) # doctest: +ELLIPSIS
234 # (((2, 0, 5, 3, 1, 4, 6), False), 0.0592259560...)
237 helper_args
= [(message
, trans
, columnwise
, fitness
)
238 for trans
in translist
.keys()
239 for columnwise
in [True, False]]
240 # Gotcha: the helper function here needs to be defined at the top level
241 # (limitation of Pool.starmap)
242 breaks
= pool
.starmap(column_transposition_break_worker
,
243 helper_args
, chunksize
)
244 return max(breaks
, key
=lambda k
: k
[1])
245 column_transposition_break
= column_transposition_break_mp
247 def column_transposition_break_worker(message
, transposition
, columnwise
,
249 plaintext
= column_transposition_decipher(message
, transposition
, columnwise
=columnwise
)
250 fit
= fitness(sanitise(plaintext
))
251 logger
.debug('Column transposition break attempt using key {0} '
252 'gives fit of {1} and decrypt starting: {2}'.format(
254 sanitise(plaintext
)[:50]))
255 return (transposition
, columnwise
), fit
258 def transposition_break_exhaustive(message
, fitness
=Pbigrams
):
259 best_transposition
= ''
260 best_pw
= float('-inf')
261 for keylength
in range(1, 21):
262 if len(message
) % keylength
== 0:
263 for transposition
in permutations(range(keylength
)):
264 for columnwise
in [True, False]:
265 plaintext
= column_transposition_decipher(message
,
266 transposition
, columnwise
=columnwise
)
267 fit
=fitness(plaintext
)
268 logger
.debug('Column transposition break attempt using key {0} {1} '
269 'gives fit of {2} and decrypt starting: {3}'.format(
270 transposition
, columnwise
, pw
,
271 sanitise(plaintext
)[:50]))
273 best_transposition
= transposition
274 best_columnwise
= columnwise
276 return (best_transposition
, best_columnwise
), best_pw
279 def vigenere_keyword_break(message
, wordlist
=keywords
, fitness
=Pletters
):
280 """Breaks a vigenere cipher using a dictionary and
283 >>> vigenere_keyword_break(vigenere_encipher(sanitise('this is a test ' \
284 'message for the vigenere decipherment'), 'cat'), \
285 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
286 ('cat', -52.947271216...)
289 best_fit
= float("-inf")
290 for keyword
in wordlist
:
291 plaintext
= vigenere_decipher(message
, keyword
)
292 fit
= fitness(plaintext
)
293 logger
.debug('Vigenere break attempt using key {0} '
294 'gives fit of {1} and decrypt starting: {2}'.format(
296 sanitise(plaintext
)[:50]))
299 best_keyword
= keyword
300 logger
.info('Vigenere break best fit with key {0} gives fit '
301 'of {1} and decrypt starting: {2}'.format(best_keyword
,
303 vigenere_decipher(message
, best_keyword
))[:50]))
304 return best_keyword
, best_fit
306 def vigenere_keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
,
308 """Breaks a vigenere cipher using a dictionary and
311 >>> vigenere_keyword_break_mp(vigenere_encipher(sanitise('this is a test ' \
312 'message for the vigenere decipherment'), 'cat'), \
313 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
314 ('cat', -52.947271216...)
317 helper_args
= [(message
, word
, fitness
)
318 for word
in wordlist
]
319 # Gotcha: the helper function here needs to be defined at the top level
320 # (limitation of Pool.starmap)
321 breaks
= pool
.starmap(vigenere_keyword_break_worker
, helper_args
, chunksize
)
322 return max(breaks
, key
=lambda k
: k
[1])
324 def vigenere_keyword_break_worker(message
, keyword
, fitness
):
325 plaintext
= vigenere_decipher(message
, keyword
)
326 fit
= fitness(plaintext
)
327 logger
.debug('Vigenere keyword break attempt using key {0} gives fit of '
328 '{1} and decrypt starting: {2}'.format(keyword
,
329 fit
, sanitise(plaintext
)[:50]))
334 def vigenere_frequency_break(message
, fitness
=Pletters
):
335 """Breaks a Vigenere cipher with frequency analysis
337 >>> vigenere_frequency_break(vigenere_encipher(sanitise("It is time to " \
338 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
339 "afternoon when he left his jacket hanging on the easel in the " \
340 "attic. I jump every time I hear a footstep on the stairs, " \
341 "certain that the theft has been discovered and that I will " \
342 "be caught. The SS officer visits less often now that he is " \
343 "sure"), 'florence')) # doctest: +ELLIPSIS
344 ('florence', -307.5473096791...)
346 best_fit
= float("-inf")
348 sanitised_message
= sanitise(message
)
349 for trial_length
in range(1, 20):
350 splits
= every_nth(sanitised_message
, trial_length
)
351 key
= ''.join([chr(caesar_break(s
)[0] + ord('a')) for s
in splits
])
352 plaintext
= vigenere_decipher(sanitised_message
, key
)
353 fit
= fitness(plaintext
)
354 logger
.debug('Vigenere key length of {0} ({1}) gives fit of {2}'.
355 format(trial_length
, key
, fit
))
359 logger
.info('Vigenere break best fit with key {0} gives fit '
360 'of {1} and decrypt starting: {2}'.format(best_key
,
362 vigenere_decipher(message
, best_key
))[:50]))
363 return best_key
, best_fit
365 def beaufort_frequency_break(message
, fitness
=Pletters
):
366 """Breaks a Beaufort cipher with frequency analysis
368 >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \
369 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
370 "afternoon when he left his jacket hanging on the easel in the " \
371 "attic. I jump every time I hear a footstep on the stairs, " \
372 "certain that the theft has been discovered and that I will " \
373 "be caught. The SS officer visits less often now " \
374 "that he is sure"), 'florence')) # doctest: +ELLIPSIS
375 ('florence', -307.5473096791...)
377 best_fit
= float("-inf")
379 sanitised_message
= sanitise(message
)
380 for trial_length
in range(1, 20):
381 splits
= every_nth(sanitised_message
, trial_length
)
382 key
= ''.join([chr(-caesar_break(s
)[0] % 26 + ord('a')) for s
in splits
])
383 plaintext
= beaufort_decipher(sanitised_message
, key
)
384 fit
= fitness(plaintext
)
385 logger
.debug('Beaufort key length of {0} ({1}) gives fit of {2}'.
386 format(trial_length
, key
, fit
))
390 logger
.info('Beaufort break best fit with key {0} gives fit '
391 'of {1} and decrypt starting: {2}'.format(best_key
,
393 beaufort_decipher(message
, best_key
))[:50]))
394 return best_key
, best_fit
398 def plot_frequency_histogram(freqs
, sort_key
=None):
399 x
= range(len(freqs
.keys()))
400 y
= [freqs
[l
] for l
in sorted(freqs
.keys(), key
=sort_key
)]
402 ax
= f
.add_axes([0.1, 0.1, 0.9, 0.9])
403 ax
.bar(x
, y
, align
='center')
405 ax
.set_xticklabels(sorted(freqs
.keys(), key
=sort_key
))
409 if __name__
== "__main__":