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([unpos(caesar_break(s
)[0]) 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([unpos(-caesar_break(s
)[0]) for s
in splits
])
380 plaintext
= beaufort_variant_decipher(message
, key
)
381 fit
= fitness(plaintext
)
383 sanitised_message
= sanitise(message
)
384 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
385 for i
in range(1, max_key_length
+1)])
386 return max(results
, key
=lambda k
: k
[1])
388 def polybius_break_mp(message
, column_labels
, row_labels
,
389 letters_to_merge
=None,
390 wordlist
=keywords
, fitness
=Pletters
,
391 number_of_solutions
=1, chunksize
=500):
392 """Breaks a Polybius substitution cipher using a dictionary and
395 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
396 'polybius decipherment', 'elephant', 'abcde', 'abcde'), \
398 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
399 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
401 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
402 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=True), \
404 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
405 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', True), \
407 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
408 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=False), \
410 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
411 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
413 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
414 'polybius decipherment', 'elephant', 'abcde', 'pqrst', column_first=True), \
416 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
417 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'pqrst', True), \
420 if letters_to_merge
is None:
421 letters_to_merge
= {'j': 'i'}
423 helper_args
= [(message
, word
, wrap
,
424 column_labels
, row_labels
, column_first
,
428 for wrap
in KeywordWrapAlphabet
429 for column_first
in [False, True]]
430 # Gotcha: the helper function here needs to be defined at the top level
431 # (limitation of Pool.starmap)
432 breaks
= pool
.starmap(polybius_break_worker
, helper_args
, chunksize
)
433 if number_of_solutions
== 1:
434 return max(breaks
, key
=lambda k
: k
[1])
436 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
438 def polybius_break_worker(message
, keyword
, wrap_alphabet
,
439 column_order
, row_order
, column_first
,
442 plaintext
= polybius_decipher(message
, keyword
,
443 column_order
, row_order
,
444 column_first
=column_first
,
445 letters_to_merge
=letters_to_merge
,
446 wrap_alphabet
=wrap_alphabet
)
448 fit
= fitness(plaintext
)
451 logger
.debug('Polybius break attempt using key {0} (wrap={1}, merging {2}), '
452 'columns as {3}, rows as {4} (column_first={5}) '
453 'gives fit of {6} and decrypt starting: '
454 '{7}'.format(keyword
, wrap_alphabet
, letters_to_merge
,
455 column_order
, row_order
, column_first
,
456 fit
, sanitise(plaintext
)[:50]))
457 return (keyword
, wrap_alphabet
, column_order
, row_order
, column_first
), fit
460 def column_transposition_break_mp(message
, translist
=transpositions
,
461 fitness
=Pbigrams
, chunksize
=500):
462 """Breaks a column transposition cipher using a dictionary and
463 n-gram frequency analysis
465 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
466 "It is a truth universally acknowledged, that a single man in \
467 possession of a good fortune, must be in want of a wife. However \
468 little known the feelings or views of such a man may be on his \
469 first entering a neighbourhood, this truth is so well fixed in \
470 the minds of the surrounding families, that he is considered the \
471 rightful property of some one or other of their daughters."), \
473 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
474 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
475 (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
476 (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
477 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
478 "It is a truth universally acknowledged, that a single man in \
479 possession of a good fortune, must be in want of a wife. However \
480 little known the feelings or views of such a man may be on his \
481 first entering a neighbourhood, this truth is so well fixed in \
482 the minds of the surrounding families, that he is considered the \
483 rightful property of some one or other of their daughters."), \
485 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
486 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
487 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
488 fitness=Ptrigrams) # doctest: +ELLIPSIS
489 (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
492 helper_args
= [(message
, trans
, fillcolumnwise
, emptycolumnwise
,
494 for trans
in translist
495 for fillcolumnwise
in [True, False]
496 for emptycolumnwise
in [True, False]]
497 # Gotcha: the helper function here needs to be defined at the top level
498 # (limitation of Pool.starmap)
499 breaks
= pool
.starmap(column_transposition_break_worker
,
500 helper_args
, chunksize
)
501 return max(breaks
, key
=lambda k
: k
[1])
502 column_transposition_break
= column_transposition_break_mp
504 def column_transposition_break_worker(message
, transposition
,
505 fillcolumnwise
, emptycolumnwise
, fitness
):
506 plaintext
= column_transposition_decipher(message
, transposition
,
507 fillcolumnwise
=fillcolumnwise
, emptycolumnwise
=emptycolumnwise
)
508 fit
= fitness(sanitise(plaintext
))
509 logger
.debug('Column transposition break attempt using key {0} '
510 'gives fit of {1} and decrypt starting: {2}'.format(
512 sanitise(plaintext
)[:50]))
513 return (transposition
, fillcolumnwise
, emptycolumnwise
), fit
516 def scytale_break_mp(message
, max_key_length
=20,
517 fitness
=Pbigrams
, chunksize
=500):
518 """Breaks a scytale cipher using a range of lengths and
519 n-gram frequency analysis
521 >>> scytale_break_mp(scytale_encipher(sanitise( \
522 "It is a truth universally acknowledged, that a single man in \
523 possession of a good fortune, must be in want of a wife. However \
524 little known the feelings or views of such a man may be on his \
525 first entering a neighbourhood, this truth is so well fixed in \
526 the minds of the surrounding families, that he is considered the \
527 rightful property of some one or other of their daughters."), \
528 5)) # doctest: +ELLIPSIS
530 >>> scytale_break_mp(scytale_encipher(sanitise( \
531 "It is a truth universally acknowledged, that a single man in \
532 possession of a good fortune, must be in want of a wife. However \
533 little known the feelings or views of such a man may be on his \
534 first entering a neighbourhood, this truth is so well fixed in \
535 the minds of the surrounding families, that he is considered the \
536 rightful property of some one or other of their daughters."), \
538 fitness=Ptrigrams) # doctest: +ELLIPSIS
542 helper_args
= [(message
, trans
, False, True, fitness
)
544 [[col
for col
in range(math
.ceil(len(message
)/rows
))]
545 for rows
in range(1,max_key_length
+1)]]
546 # Gotcha: the helper function here needs to be defined at the top level
547 # (limitation of Pool.starmap)
548 breaks
= pool
.starmap(column_transposition_break_worker
,
549 helper_args
, chunksize
)
550 best
= max(breaks
, key
=lambda k
: k
[1])
551 return math
.trunc(len(message
) / len(best
[0][0])), best
[1]
552 scytale_break
= scytale_break_mp
555 def railfence_break(message
, max_key_length
=20,
556 fitness
=Pletters
, chunksize
=500):
557 """Breaks a hill cipher using a matrix of given rank and letter frequencies
562 sanitised_message
= sanitise(message
)
563 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
564 for i
in range(2, max_key_length
+1)])
565 return max(results
, key
=lambda k
: k
[1])
568 def railfence_break(message
, max_key_length
=20,
569 fitness
=Pbigrams
, chunksize
=500):
570 """Breaks a railfence cipher using a range of lengths and
571 n-gram frequency analysis
573 >>> railfence_break(railfence_encipher(sanitise( \
574 "It is a truth universally acknowledged, that a single man in \
575 possession of a good fortune, must be in want of a wife. However \
576 little known the feelings or views of such a man may be on his \
577 first entering a neighbourhood, this truth is so well fixed in \
578 the minds of the surrounding families, that he is considered the \
579 rightful property of some one or other of their daughters."), \
580 7)) # doctest: +ELLIPSIS
581 (7, -709.46467226...)
582 >>> railfence_break(railfence_encipher(sanitise( \
583 "It is a truth universally acknowledged, that a single man in \
584 possession of a good fortune, must be in want of a wife. However \
585 little known the feelings or views of such a man may be on his \
586 first entering a neighbourhood, this truth is so well fixed in \
587 the minds of the surrounding families, that he is considered the \
588 rightful property of some one or other of their daughters."), \
590 fitness=Ptrigrams) # doctest: +ELLIPSIS
593 def worker(message
, height
, fitness
):
594 plaintext
= railfence_decipher(message
, height
)
595 fit
= fitness(plaintext
)
598 sanitised_message
= sanitise(message
)
599 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
600 for i
in range(2, max_key_length
+1)])
601 return max(results
, key
=lambda k
: k
[1])
603 def amsco_break(message
, translist
=transpositions
, patterns
= [(1, 2), (2, 1)],
604 fillstyles
= [AmscoFillStyle
.continuous
,
605 AmscoFillStyle
.same_each_row
,
606 AmscoFillStyle
.reverse_each_row
],
609 """Breaks an AMSCO transposition cipher using a dictionary and
610 n-gram frequency analysis
612 >>> amsco_break(amsco_transposition_encipher(sanitise( \
613 "It is a truth universally acknowledged, that a single man in \
614 possession of a good fortune, must be in want of a wife. However \
615 little known the feelings or views of such a man may be on his \
616 first entering a neighbourhood, this truth is so well fixed in \
617 the minds of the surrounding families, that he is considered the \
618 rightful property of some one or other of their daughters."), \
620 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
621 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
622 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
623 patterns=[(1, 2)]) # doctest: +ELLIPSIS
624 (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
625 >>> amsco_break(amsco_transposition_encipher(sanitise( \
626 "It is a truth universally acknowledged, that a single man in \
627 possession of a good fortune, must be in want of a wife. However \
628 little known the feelings or views of such a man may be on his \
629 first entering a neighbourhood, this truth is so well fixed in \
630 the minds of the surrounding families, that he is considered the \
631 rightful property of some one or other of their daughters."), \
632 'encipher', fillpattern=(2, 1)), \
633 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
634 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
635 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
636 patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
637 (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
640 helper_args
= [(message
, trans
, pattern
, fillstyle
, fitness
)
641 for trans
in translist
642 for pattern
in patterns
643 for fillstyle
in fillstyles
]
644 # Gotcha: the helper function here needs to be defined at the top level
645 # (limitation of Pool.starmap)
646 breaks
= pool
.starmap(amsco_break_worker
, helper_args
, chunksize
)
647 return max(breaks
, key
=lambda k
: k
[1])
649 def amsco_break_worker(message
, transposition
,
650 pattern
, fillstyle
, fitness
):
651 plaintext
= amsco_transposition_decipher(message
, transposition
,
652 fillpattern
=pattern
, fillstyle
=fillstyle
)
653 fit
= fitness(sanitise(plaintext
))
654 logger
.debug('AMSCO transposition break attempt using key {0} and pattern'
655 '{1} ({2}) gives fit of {3} and decrypt starting: '
657 transposition
, pattern
, fillstyle
, fit
,
658 sanitise(plaintext
)[:50]))
659 return (transposition
, pattern
, fillstyle
), fit
662 def hill_break(message
, matrix_size
=2, fitness
=Pletters
,
663 number_of_solutions
=1, chunksize
=500):
665 all_matrices
= [np
.matrix(list(m
))
666 for m
in itertools
.product([list(r
)
667 for r
in itertools
.product(range(26), repeat
=matrix_size
)],
669 valid_matrices
= [m
for m
, d
in
670 zip(all_matrices
, (int(round(linalg
.det(m
))) for m
in all_matrices
))
675 helper_args
= [(message
, matrix
, fitness
)
676 for matrix
in valid_matrices
]
677 # Gotcha: the helper function here needs to be defined at the top level
678 # (limitation of Pool.starmap)
679 breaks
= pool
.starmap(hill_break_worker
, helper_args
, chunksize
)
680 if number_of_solutions
== 1:
681 return max(breaks
, key
=lambda k
: k
[1])
683 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
685 def hill_break_worker(message
, matrix
, fitness
):
686 plaintext
= hill_decipher(matrix
, message
)
687 fit
= fitness(plaintext
)
688 logger
.debug('Hill cipher break attempt using key {0} gives fit of '
689 '{1} and decrypt starting: {2}'.format(matrix
,
690 fit
, sanitise(plaintext
)[:50]))
693 def bifid_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
, max_period
=10,
694 number_of_solutions
=1, chunksize
=500):
695 """Breaks a keyword substitution cipher using a dictionary and
698 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
699 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
700 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
701 (('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...)
702 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
703 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
704 wordlist=['cat', 'elephant', 'kangaroo'], \
705 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
706 [(('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...),
707 (('elephant', <KeywordWrapAlphabet.from_largest: 3>, 0), -52.834575011...)]
710 helper_args
= [(message
, word
, wrap
, period
, fitness
)
712 for wrap
in KeywordWrapAlphabet
713 for period
in range(max_period
+1)]
714 # Gotcha: the helper function here needs to be defined at the top level
715 # (limitation of Pool.starmap)
716 breaks
= pool
.starmap(bifid_break_worker
, helper_args
, chunksize
)
717 if number_of_solutions
== 1:
718 return max(breaks
, key
=lambda k
: k
[1])
720 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
722 def bifid_break_worker(message
, keyword
, wrap_alphabet
, period
, fitness
):
723 plaintext
= bifid_decipher(message
, keyword
, wrap_alphabet
, period
=period
)
724 fit
= fitness(plaintext
)
725 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
726 '{2} and decrypt starting: {3}'.format(keyword
,
727 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
728 return (keyword
, wrap_alphabet
, period
), fit
731 def pocket_enigma_break_by_crib(message
, wheel_spec
, crib
, crib_position
):
732 """Break a pocket enigma using a crib (some plaintext that's expected to
733 be in a certain position). Returns a list of possible starting wheel
734 positions that could produce the crib.
736 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'h', 0)
738 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'he', 0)
740 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'll', 2)
742 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 2)
744 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 3)
746 >>> pocket_enigma_break_by_crib('aaaaa', 1, 'l', 3)
749 pe
= PocketEnigma(wheel
=wheel_spec
)
750 possible_positions
= []
751 for p
in string
.ascii_lowercase
:
753 plaintext
= pe
.decipher(message
)
754 if plaintext
[crib_position
:crib_position
+len(crib
)] == crib
:
755 possible_positions
+= [p
]
756 return possible_positions
759 def plot_frequency_histogram(freqs
, sort_key
=None):
760 x
= range(len(freqs
))
761 y
= [freqs
[l
] for l
in sorted(freqs
, key
=sort_key
)]
763 ax
= f
.add_axes([0.1, 0.1, 0.9, 0.9])
764 ax
.bar(x
, y
, align
='center')
766 ax
.set_xticklabels(sorted(freqs
, key
=sort_key
))
770 if __name__
== "__main__":