1 """A set of functions to break the ciphers give in ciphers.py.
10 from itertools
import starmap
11 from segment
import segment
12 from multiprocessing
import Pool
14 import matplotlib
.pyplot
as plt
16 # logging.basicConfig(filename="cipher.log", level=logging.INFO)
17 # logger = logging.getLogger(__name__)
19 logger
= logging
.getLogger('cipherbreak')
20 logger
.setLevel(logging
.WARNING
)
21 # logger.setLevel(logging.INFO)
22 # logger.setLevel(logging.DEBUG)
24 # create the logging file handler
25 fh
= logging
.FileHandler("cipher.log")
26 formatter
= logging
.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
27 fh
.setFormatter(formatter
)
29 # add handler to logger object
34 from language_models
import *
39 # c5a = open('2012/5a.ciphertext', 'r').read()
40 # timeit.timeit('keyword_break(c5a)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break', number=1)
41 # 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)
43 transpositions
= collections
.defaultdict(list)
45 transpositions
[transpositions_of(word
)] += [word
]
47 def frequencies(text
):
48 """Count the number of occurrences of each character in text
50 >>> sorted(frequencies('abcdefabc').items())
51 [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
52 >>> sorted(frequencies('the quick brown fox jumped over the lazy ' \
53 'dog').items()) # doctest: +NORMALIZE_WHITESPACE
54 [(' ', 8), ('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1),
55 ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1),
56 ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2),
57 ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
58 >>> sorted(frequencies('The Quick BROWN fox jumped! over... the ' \
59 '(9lazy) DOG').items()) # doctest: +NORMALIZE_WHITESPACE
60 [(' ', 8), ('!', 1), ('(', 1), (')', 1), ('.', 3), ('9', 1), ('B', 1),
61 ('D', 1), ('G', 1), ('N', 1), ('O', 2), ('Q', 1), ('R', 1), ('T', 1),
62 ('W', 1), ('a', 1), ('c', 1), ('d', 1), ('e', 4), ('f', 1), ('h', 2),
63 ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('o', 2), ('p', 1),
64 ('r', 1), ('t', 1), ('u', 2), ('v', 1), ('x', 1), ('y', 1), ('z', 1)]
65 >>> sorted(frequencies(sanitise('The Quick BROWN fox jumped! over... '\
66 'the (9lazy) DOG')).items()) # doctest: +NORMALIZE_WHITESPACE
67 [('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1),
68 ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1),
69 ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1),
70 ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
71 >>> frequencies('abcdefabcdef')['x']
74 return collections
.Counter(c
for c
in text
)
77 def caesar_break(message
, fitness
=Pletters
):
78 """Breaks a Caesar cipher using frequency analysis
80 >>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrh' \
81 'ecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm') # doctest: +ELLIPSIS
82 (4, -130.849989015...)
83 >>> caesar_break('wxwmaxdgheetgwuxztgptedbgznitgwwhpguxyhkxbmhvvtlbhgtee' \
84 'raxlmhiixweblmxgxwmhmaxybkbgztgwztsxwbgmxgmert') # doctest: +ELLIPSIS
85 (19, -128.82410410...)
86 >>> caesar_break('yltbbqnqnzvguvaxurorgenafsbezqvagbnornfgsbevpnaabjurer' \
87 'svaquvzyvxrnznazlybequrvfohgriraabjtbaruraprur') # doctest: +ELLIPSIS
88 (13, -126.25403935...)
90 sanitised_message
= sanitise(message
)
92 best_fit
= float('-inf')
93 for shift
in range(26):
94 plaintext
= caesar_decipher(sanitised_message
, shift
)
95 fit
= fitness(plaintext
)
96 logger
.debug('Caesar break attempt using key {0} gives fit of {1} '
97 'and decrypt starting: {2}'.format(shift
, fit
,
102 logger
.info('Caesar break best fit: key {0} gives fit of {1} and '
103 'decrypt starting: {2}'.format(best_shift
, best_fit
,
104 caesar_decipher(sanitised_message
, best_shift
)[:50]))
105 return best_shift
, best_fit
107 def affine_break(message
, fitness
=Pletters
):
108 """Breaks an affine cipher using frequency analysis
110 >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls ' \
111 'omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ' \
112 'ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ' \
113 'ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls ' \
114 'bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai ' \
115 'kxd clm ckuxj.') # doctest: +ELLIPSIS
116 ((15, 22, True), -340.601181913...)
118 sanitised_message
= sanitise(message
)
121 best_one_based
= True
122 best_fit
= float("-inf")
123 for one_based
in [True, False]:
124 for multiplier
in [x
for x
in range(1, 26, 2) if x
!= 13]:
125 for adder
in range(26):
126 plaintext
= affine_decipher(sanitised_message
,
127 multiplier
, adder
, one_based
)
128 fit
= fitness(plaintext
)
129 logger
.debug('Affine break attempt using key {0}x+{1} ({2}) '
130 'gives fit of {3} and decrypt starting: {4}'.
131 format(multiplier
, adder
, one_based
, fit
,
135 best_multiplier
= multiplier
137 best_one_based
= one_based
138 logger
.info('Affine break best fit with key {0}x+{1} ({2}) gives fit of '
139 '{3} and decrypt starting: {4}'.format(
140 best_multiplier
, best_adder
, best_one_based
, best_fit
,
141 affine_decipher(sanitised_message
, best_multiplier
,
142 best_adder
, best_one_based
)[:50]))
143 return (best_multiplier
, best_adder
, best_one_based
), best_fit
145 def keyword_break(message
, wordlist
=keywords
, fitness
=Pletters
):
146 """Breaks a keyword substitution cipher using a dictionary and
149 >>> keyword_break(keyword_encipher('this is a test message for the ' \
150 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
151 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
152 (('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...)
155 best_wrap_alphabet
= True
156 best_fit
= float("-inf")
157 for wrap_alphabet
in KeywordWrapAlphabet
:
158 for keyword
in wordlist
:
159 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
160 fit
= fitness(plaintext
)
161 logger
.debug('Keyword break attempt using key {0} (wrap={1}) '
162 'gives fit of {2} and decrypt starting: {3}'.format(
163 keyword
, wrap_alphabet
, fit
,
164 sanitise(plaintext
)[:50]))
167 best_keyword
= keyword
168 best_wrap_alphabet
= wrap_alphabet
169 logger
.info('Keyword break best fit with key {0} (wrap={1}) gives fit of '
170 '{2} and decrypt starting: {3}'.format(best_keyword
,
171 best_wrap_alphabet
, best_fit
, sanitise(
172 keyword_decipher(message
, best_keyword
,
173 best_wrap_alphabet
))[:50]))
174 return (best_keyword
, best_wrap_alphabet
), best_fit
176 def keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
,
177 number_of_solutions
=1, chunksize
=500):
178 """Breaks a keyword substitution cipher using a dictionary and
181 >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \
182 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
183 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
184 (('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...)
185 >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \
186 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
187 wordlist=['cat', 'elephant', 'kangaroo'], \
188 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
189 [(('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...),
190 (('elephant', <KeywordWrapAlphabet.from_largest: 3>), -52.834575011...)]
193 helper_args
= [(message
, word
, wrap
, fitness
)
195 for wrap
in KeywordWrapAlphabet
]
196 # Gotcha: the helper function here needs to be defined at the top level
197 # (limitation of Pool.starmap)
198 breaks
= pool
.starmap(keyword_break_worker
, helper_args
, chunksize
)
199 if number_of_solutions
== 1:
200 return max(breaks
, key
=lambda k
: k
[1])
202 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
204 def keyword_break_worker(message
, keyword
, wrap_alphabet
, fitness
):
205 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
206 fit
= fitness(plaintext
)
207 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
208 '{2} and decrypt starting: {3}'.format(keyword
,
209 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
210 return (keyword
, wrap_alphabet
), fit
212 def monoalphabetic_break_hillclimbing(message
, max_iterations
=10000000,
213 alphabet
=None, fitness
=Pletters
):
214 ciphertext
= unaccent(message
).lower()
216 alphabet
= list(string
.ascii_lowercase
)
217 random
.shuffle(alphabet
)
218 alphabet
= cat(alphabet
)
219 return monoalphabetic_break_hillclimbing_worker(ciphertext
, alphabet
,
220 max_iterations
, fitness
)
222 def monoalphabetic_break_hillclimbing_mp(message
, workers
=10,
223 max_iterations
= 10000000, alphabet
=None, fitness
=Pletters
, chunksize
=1):
225 ciphertext
= unaccent(message
).lower()
226 for i
in range(workers
):
228 this_alphabet
= alphabet
230 this_alphabet
= list(string
.ascii_lowercase
)
231 random
.shuffle(this_alphabet
)
232 this_alphabet
= cat(this_alphabet
)
233 worker_args
.append((ciphertext
, this_alphabet
, max_iterations
, fitness
))
235 breaks
= pool
.starmap(monoalphabetic_break_hillclimbing_worker
,
236 worker_args
, chunksize
)
237 return max(breaks
, key
=lambda k
: k
[1])
239 def monoalphabetic_break_hillclimbing_worker(message
, alphabet
,
240 max_iterations
, fitness
):
241 def swap(letters
, i
, j
):
247 return (letters
[:i
] + letters
[j
] + letters
[i
+1:j
] + letters
[i
] +
249 best_alphabet
= alphabet
250 best_fitness
= float('-inf')
251 for i
in range(max_iterations
):
252 alphabet
= swap(alphabet
, random
.randrange(26), random
.randrange(26))
253 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, alphabet
)
254 plaintext
= message
.translate(cipher_translation
)
255 if fitness(plaintext
) > best_fitness
:
256 best_fitness
= fitness(plaintext
)
257 best_alphabet
= alphabet
258 print(i
, best_alphabet
, best_fitness
, plaintext
)
259 return best_alphabet
, best_fitness
262 def vigenere_keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
,
264 """Breaks a vigenere cipher using a dictionary and frequency analysis.
266 >>> vigenere_keyword_break_mp(vigenere_encipher(sanitise('this is a test ' \
267 'message for the vigenere decipherment'), 'cat'), \
268 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
269 ('cat', -52.9472712...)
272 helper_args
= [(message
, word
, fitness
)
273 for word
in wordlist
]
274 # Gotcha: the helper function here needs to be defined at the top level
275 # (limitation of Pool.starmap)
276 breaks
= pool
.starmap(vigenere_keyword_break_worker
, helper_args
,
278 return max(breaks
, key
=lambda k
: k
[1])
279 vigenere_keyword_break
= vigenere_keyword_break_mp
281 def vigenere_keyword_break_worker(message
, keyword
, fitness
):
282 plaintext
= vigenere_decipher(message
, keyword
)
283 fit
= fitness(plaintext
)
284 logger
.debug('Vigenere keyword break attempt using key {0} gives fit of '
285 '{1} and decrypt starting: {2}'.format(keyword
,
286 fit
, sanitise(plaintext
)[:50]))
290 def vigenere_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
291 """Breaks a Vigenere cipher with frequency analysis
293 >>> vigenere_frequency_break(vigenere_encipher(sanitise("It is time to " \
294 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
295 "afternoon when he left his jacket hanging on the easel in the " \
296 "attic. I jump every time I hear a footstep on the stairs, " \
297 "certain that the theft has been discovered and that I will " \
298 "be caught. The SS officer visits less often now that he is " \
299 "sure"), 'florence')) # doctest: +ELLIPSIS
300 ('florence', -307.5473096...)
302 def worker(message
, key_length
, fitness
):
303 splits
= every_nth(sanitised_message
, key_length
)
304 key
= cat([chr(caesar_break(s
)[0] + ord('a')) for s
in splits
])
305 plaintext
= vigenere_decipher(message
, key
)
306 fit
= fitness(plaintext
)
308 sanitised_message
= sanitise(message
)
309 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
310 for i
in range(1, max_key_length
+1)])
311 return max(results
, key
=lambda k
: k
[1])
314 def beaufort_sub_break(message
, fitness
=Pletters
):
315 """Breaks one chunk of a Beaufort cipher with frequency analysis
317 >>> beaufort_sub_break('samwpplggnnmmyaazgympjapopnwiywwomwspgpjmefwmawx' \
318 'jafjhxwwwdigxshnlywiamhyshtasxptwueahhytjwsn') # doctest: +ELLIPSIS
320 >>> beaufort_sub_break('eyprzjjzznxymrygryjqmqhznjrjjapenejznawngnnezgza' \
321 'dgndknaogpdjneadadazlhkhxkryevrronrmdjnndjlo') # doctest: +ELLIPSIS
325 best_fit
= float('-inf')
326 for key
in range(26):
327 plaintext
= [unpos(key
- pos(l
)) for l
in message
]
328 fit
= fitness(plaintext
)
329 logger
.debug('Beaufort sub break attempt using key {0} gives fit of {1} '
330 'and decrypt starting: {2}'.format(key
, fit
,
335 logger
.info('Beaufort sub break best fit: key {0} gives fit of {1} and '
336 'decrypt starting: {2}'.format(best_key
, best_fit
,
337 cat([unpos(best_key
- pos(l
)) for l
in message
[:50]])))
338 return best_key
, best_fit
341 def beaufort_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
342 """Breaks a Beaufort cipher with frequency analysis
344 >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \
345 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
346 "afternoon when he left his jacket hanging on the easel in the " \
347 "attic. I jump every time I hear a footstep on the stairs, " \
348 "certain that the theft has been discovered and that I will " \
349 "be caught. The SS officer visits less often now " \
350 "that he is sure"), 'florence')) # doctest: +ELLIPSIS
351 ('florence', -307.5473096791...)
353 def worker(message
, key_length
, fitness
):
354 splits
= every_nth(message
, key_length
)
355 key
= cat([unpos(beaufort_sub_break(s
)[0]) for s
in splits
])
356 plaintext
= beaufort_decipher(message
, key
)
357 fit
= fitness(plaintext
)
359 sanitised_message
= sanitise(message
)
360 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
361 for i
in range(1, max_key_length
+1)])
362 return max(results
, key
=lambda k
: k
[1])
365 def beaufort_variant_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
366 """Breaks a Beaufort cipher with frequency analysis
368 >>> beaufort_variant_frequency_break(beaufort_variant_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 def worker(message
, key_length
, fitness
):
378 splits
= every_nth(sanitised_message
, key_length
)
379 key
= cat([chr(-caesar_break(s
)[0] % 26 + ord('a'))
381 plaintext
= beaufort_variant_decipher(message
, key
)
382 fit
= fitness(plaintext
)
384 sanitised_message
= sanitise(message
)
385 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
386 for i
in range(1, max_key_length
+1)])
387 return max(results
, key
=lambda k
: k
[1])
389 def polybius_break_mp(message
, column_labels
, row_labels
,
390 letters_to_merge
=None,
391 wordlist
=keywords
, fitness
=Pletters
,
392 number_of_solutions
=1, chunksize
=500):
393 """Breaks a Polybius substitution cipher using a dictionary and
396 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
397 'polybius decipherment', 'elephant', 'abcde', 'abcde'), \
399 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
400 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
402 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
403 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=True), \
405 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
406 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', True), \
408 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
409 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=False), \
411 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
412 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
414 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
415 'polybius decipherment', 'elephant', 'abcde', 'pqrst', column_first=True), \
417 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
418 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'pqrst', True), \
421 if letters_to_merge
is None:
422 letters_to_merge
= {'j': 'i'}
424 helper_args
= [(message
, word
, wrap
,
425 column_labels
, row_labels
, column_first
,
429 for wrap
in KeywordWrapAlphabet
430 for column_first
in [False, True]]
431 # Gotcha: the helper function here needs to be defined at the top level
432 # (limitation of Pool.starmap)
433 breaks
= pool
.starmap(polybius_break_worker
, helper_args
, chunksize
)
434 if number_of_solutions
== 1:
435 return max(breaks
, key
=lambda k
: k
[1])
437 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
439 def polybius_break_worker(message
, keyword
, wrap_alphabet
,
440 column_order
, row_order
, column_first
,
443 plaintext
= polybius_decipher(message
, keyword
,
444 column_order
, row_order
,
445 column_first
=column_first
,
446 letters_to_merge
=letters_to_merge
,
447 wrap_alphabet
=wrap_alphabet
)
449 fit
= fitness(plaintext
)
452 logger
.debug('Polybius break attempt using key {0} (wrap={1}, merging {2}), '
453 'columns as {3}, rows as {4} (column_first={5}) '
454 'gives fit of {6} and decrypt starting: '
455 '{7}'.format(keyword
, wrap_alphabet
, letters_to_merge
,
456 column_order
, row_order
, column_first
,
457 fit
, sanitise(plaintext
)[:50]))
458 return (keyword
, wrap_alphabet
, column_order
, row_order
, column_first
), fit
461 def column_transposition_break_mp(message
, translist
=transpositions
,
462 fitness
=Pbigrams
, chunksize
=500):
463 """Breaks a column transposition cipher using a dictionary and
464 n-gram frequency analysis
466 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
467 "It is a truth universally acknowledged, that a single man in \
468 possession of a good fortune, must be in want of a wife. However \
469 little known the feelings or views of such a man may be on his \
470 first entering a neighbourhood, this truth is so well fixed in \
471 the minds of the surrounding families, that he is considered the \
472 rightful property of some one or other of their daughters."), \
474 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
475 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
476 (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
477 (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
478 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
479 "It is a truth universally acknowledged, that a single man in \
480 possession of a good fortune, must be in want of a wife. However \
481 little known the feelings or views of such a man may be on his \
482 first entering a neighbourhood, this truth is so well fixed in \
483 the minds of the surrounding families, that he is considered the \
484 rightful property of some one or other of their daughters."), \
486 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
487 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
488 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
489 fitness=Ptrigrams) # doctest: +ELLIPSIS
490 (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
493 helper_args
= [(message
, trans
, fillcolumnwise
, emptycolumnwise
,
495 for trans
in translist
496 for fillcolumnwise
in [True, False]
497 for emptycolumnwise
in [True, False]]
498 # Gotcha: the helper function here needs to be defined at the top level
499 # (limitation of Pool.starmap)
500 breaks
= pool
.starmap(column_transposition_break_worker
,
501 helper_args
, chunksize
)
502 return max(breaks
, key
=lambda k
: k
[1])
503 column_transposition_break
= column_transposition_break_mp
505 def column_transposition_break_worker(message
, transposition
,
506 fillcolumnwise
, emptycolumnwise
, fitness
):
507 plaintext
= column_transposition_decipher(message
, transposition
,
508 fillcolumnwise
=fillcolumnwise
, emptycolumnwise
=emptycolumnwise
)
509 fit
= fitness(sanitise(plaintext
))
510 logger
.debug('Column transposition break attempt using key {0} '
511 'gives fit of {1} and decrypt starting: {2}'.format(
513 sanitise(plaintext
)[:50]))
514 return (transposition
, fillcolumnwise
, emptycolumnwise
), fit
517 def scytale_break_mp(message
, max_key_length
=20,
518 fitness
=Pbigrams
, chunksize
=500):
519 """Breaks a scytale cipher using a range of lengths and
520 n-gram frequency analysis
522 >>> scytale_break_mp(scytale_encipher(sanitise( \
523 "It is a truth universally acknowledged, that a single man in \
524 possession of a good fortune, must be in want of a wife. However \
525 little known the feelings or views of such a man may be on his \
526 first entering a neighbourhood, this truth is so well fixed in \
527 the minds of the surrounding families, that he is considered the \
528 rightful property of some one or other of their daughters."), \
529 5)) # doctest: +ELLIPSIS
531 >>> scytale_break_mp(scytale_encipher(sanitise( \
532 "It is a truth universally acknowledged, that a single man in \
533 possession of a good fortune, must be in want of a wife. However \
534 little known the feelings or views of such a man may be on his \
535 first entering a neighbourhood, this truth is so well fixed in \
536 the minds of the surrounding families, that he is considered the \
537 rightful property of some one or other of their daughters."), \
539 fitness=Ptrigrams) # doctest: +ELLIPSIS
543 helper_args
= [(message
, trans
, False, True, fitness
)
545 [[col
for col
in range(math
.ceil(len(message
)/rows
))]
546 for rows
in range(1,max_key_length
+1)]]
547 # Gotcha: the helper function here needs to be defined at the top level
548 # (limitation of Pool.starmap)
549 breaks
= pool
.starmap(column_transposition_break_worker
,
550 helper_args
, chunksize
)
551 best
= max(breaks
, key
=lambda k
: k
[1])
552 return math
.trunc(len(message
) / len(best
[0][0])), best
[1]
553 scytale_break
= scytale_break_mp
556 def railfence_break(message
, max_key_length
=20,
557 fitness
=Pletters
, chunksize
=500):
558 """Breaks a hill cipher using a matrix of given rank and letter frequencies
563 sanitised_message
= sanitise(message
)
564 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
565 for i
in range(2, max_key_length
+1)])
566 return max(results
, key
=lambda k
: k
[1])
569 def railfence_break(message
, max_key_length
=20,
570 fitness
=Pbigrams
, chunksize
=500):
571 """Breaks a railfence cipher using a range of lengths and
572 n-gram frequency analysis
574 >>> railfence_break(railfence_encipher(sanitise( \
575 "It is a truth universally acknowledged, that a single man in \
576 possession of a good fortune, must be in want of a wife. However \
577 little known the feelings or views of such a man may be on his \
578 first entering a neighbourhood, this truth is so well fixed in \
579 the minds of the surrounding families, that he is considered the \
580 rightful property of some one or other of their daughters."), \
581 7)) # doctest: +ELLIPSIS
582 (7, -709.46467226...)
583 >>> railfence_break(railfence_encipher(sanitise( \
584 "It is a truth universally acknowledged, that a single man in \
585 possession of a good fortune, must be in want of a wife. However \
586 little known the feelings or views of such a man may be on his \
587 first entering a neighbourhood, this truth is so well fixed in \
588 the minds of the surrounding families, that he is considered the \
589 rightful property of some one or other of their daughters."), \
591 fitness=Ptrigrams) # doctest: +ELLIPSIS
594 def worker(message
, height
, fitness
):
595 plaintext
= railfence_decipher(message
, height
)
596 fit
= fitness(plaintext
)
599 sanitised_message
= sanitise(message
)
600 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
601 for i
in range(2, max_key_length
+1)])
602 return max(results
, key
=lambda k
: k
[1])
604 def amsco_break(message
, translist
=transpositions
, patterns
= [(1, 2), (2, 1)],
605 fillstyles
= [AmscoFillStyle
.continuous
,
606 AmscoFillStyle
.same_each_row
,
607 AmscoFillStyle
.reverse_each_row
],
610 """Breaks an AMSCO transposition cipher using a dictionary and
611 n-gram frequency analysis
613 >>> amsco_break(amsco_transposition_encipher(sanitise( \
614 "It is a truth universally acknowledged, that a single man in \
615 possession of a good fortune, must be in want of a wife. However \
616 little known the feelings or views of such a man may be on his \
617 first entering a neighbourhood, this truth is so well fixed in \
618 the minds of the surrounding families, that he is considered the \
619 rightful property of some one or other of their daughters."), \
621 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
622 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
623 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
624 patterns=[(1, 2)]) # doctest: +ELLIPSIS
625 (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
626 >>> amsco_break(amsco_transposition_encipher(sanitise( \
627 "It is a truth universally acknowledged, that a single man in \
628 possession of a good fortune, must be in want of a wife. However \
629 little known the feelings or views of such a man may be on his \
630 first entering a neighbourhood, this truth is so well fixed in \
631 the minds of the surrounding families, that he is considered the \
632 rightful property of some one or other of their daughters."), \
633 'encipher', fillpattern=(2, 1)), \
634 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
635 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
636 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
637 patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
638 (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
641 helper_args
= [(message
, trans
, pattern
, fillstyle
, fitness
)
642 for trans
in translist
643 for pattern
in patterns
644 for fillstyle
in fillstyles
]
645 # Gotcha: the helper function here needs to be defined at the top level
646 # (limitation of Pool.starmap)
647 breaks
= pool
.starmap(amsco_break_worker
, helper_args
, chunksize
)
648 return max(breaks
, key
=lambda k
: k
[1])
650 def amsco_break_worker(message
, transposition
,
651 pattern
, fillstyle
, fitness
):
652 plaintext
= amsco_transposition_decipher(message
, transposition
,
653 fillpattern
=pattern
, fillstyle
=fillstyle
)
654 fit
= fitness(sanitise(plaintext
))
655 logger
.debug('AMSCO transposition break attempt using key {0} and pattern'
656 '{1} ({2}) gives fit of {3} and decrypt starting: '
658 transposition
, pattern
, fillstyle
, fit
,
659 sanitise(plaintext
)[:50]))
660 return (transposition
, pattern
, fillstyle
), fit
663 def hill_break(message
, matrix_size
=2, fitness
=Pletters
,
664 number_of_solutions
=1, chunksize
=500):
666 all_matrices
= [np
.matrix(list(m
))
667 for m
in itertools
.product([list(r
)
668 for r
in itertools
.product(range(26), repeat
=matrix_size
)],
670 valid_matrices
= [m
for m
, d
in
671 zip(all_matrices
, (int(round(linalg
.det(m
))) for m
in all_matrices
))
676 helper_args
= [(message
, matrix
, fitness
)
677 for matrix
in valid_matrices
]
678 # Gotcha: the helper function here needs to be defined at the top level
679 # (limitation of Pool.starmap)
680 breaks
= pool
.starmap(hill_break_worker
, helper_args
, chunksize
)
681 if number_of_solutions
== 1:
682 return max(breaks
, key
=lambda k
: k
[1])
684 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
686 def hill_break_worker(message
, matrix
, fitness
):
687 plaintext
= hill_decipher(matrix
, message
)
688 fit
= fitness(plaintext
)
689 logger
.debug('Hill cipher break attempt using key {0} gives fit of '
690 '{1} and decrypt starting: {2}'.format(matrix
,
691 fit
, sanitise(plaintext
)[:50]))
694 def bifid_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
, max_period
=10,
695 number_of_solutions
=1, chunksize
=500):
696 """Breaks a keyword substitution cipher using a dictionary and
699 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
700 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
701 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
702 (('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...)
703 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
704 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
705 wordlist=['cat', 'elephant', 'kangaroo'], \
706 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
707 [(('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...),
708 (('elephant', <KeywordWrapAlphabet.from_largest: 3>, 0), -52.834575011...)]
711 helper_args
= [(message
, word
, wrap
, period
, fitness
)
713 for wrap
in KeywordWrapAlphabet
714 for period
in range(max_period
+1)]
715 # Gotcha: the helper function here needs to be defined at the top level
716 # (limitation of Pool.starmap)
717 breaks
= pool
.starmap(bifid_break_worker
, helper_args
, chunksize
)
718 if number_of_solutions
== 1:
719 return max(breaks
, key
=lambda k
: k
[1])
721 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
723 def bifid_break_worker(message
, keyword
, wrap_alphabet
, period
, fitness
):
724 plaintext
= bifid_decipher(message
, keyword
, wrap_alphabet
, period
=period
)
725 fit
= fitness(plaintext
)
726 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
727 '{2} and decrypt starting: {3}'.format(keyword
,
728 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
729 return (keyword
, wrap_alphabet
, period
), fit
732 def pocket_enigma_break_by_crib(message
, wheel_spec
, crib
, crib_position
):
733 """Break a pocket enigma using a crib (some plaintext that's expected to
734 be in a certain position). Returns a list of possible starting wheel
735 positions that could produce the crib.
737 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'h', 0)
739 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'he', 0)
741 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'll', 2)
743 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 2)
745 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 3)
747 >>> pocket_enigma_break_by_crib('aaaaa', 1, 'l', 3)
750 pe
= PocketEnigma(wheel
=wheel_spec
)
751 possible_positions
= []
752 for p
in string
.ascii_lowercase
:
754 plaintext
= pe
.decipher(message
)
755 if plaintext
[crib_position
:crib_position
+len(crib
)] == crib
:
756 possible_positions
+= [p
]
757 return possible_positions
760 def plot_frequency_histogram(freqs
, sort_key
=None):
761 x
= range(len(freqs
))
762 y
= [freqs
[l
] for l
in sorted(freqs
, key
=sort_key
)]
764 ax
= f
.add_axes([0.1, 0.1, 0.9, 0.9])
765 ax
.bar(x
, y
, align
='center')
767 ax
.set_xticklabels(sorted(freqs
, key
=sort_key
))
771 if __name__
== "__main__":