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)
44 def index_of_coincidence(text
):
45 stext
= sanitise(text
)
46 counts
= collections
.Counter(stext
)
47 denom
= len(stext
) * (len(text
) - 1) / 26
49 sum(max(counts
[l
] * counts
[l
] - 1, 0) for l
in string
.ascii_lowercase
)
55 transpositions
= collections
.defaultdict(list)
57 transpositions
[transpositions_of(word
)] += [word
]
59 def frequencies(text
):
60 """Count the number of occurrences of each character in text
62 >>> sorted(frequencies('abcdefabc').items())
63 [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
64 >>> sorted(frequencies('the quick brown fox jumped over the lazy ' \
65 'dog').items()) # doctest: +NORMALIZE_WHITESPACE
66 [(' ', 8), ('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1),
67 ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1),
68 ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2),
69 ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
70 >>> sorted(frequencies('The Quick BROWN fox jumped! over... the ' \
71 '(9lazy) DOG').items()) # doctest: +NORMALIZE_WHITESPACE
72 [(' ', 8), ('!', 1), ('(', 1), (')', 1), ('.', 3), ('9', 1), ('B', 1),
73 ('D', 1), ('G', 1), ('N', 1), ('O', 2), ('Q', 1), ('R', 1), ('T', 1),
74 ('W', 1), ('a', 1), ('c', 1), ('d', 1), ('e', 4), ('f', 1), ('h', 2),
75 ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('o', 2), ('p', 1),
76 ('r', 1), ('t', 1), ('u', 2), ('v', 1), ('x', 1), ('y', 1), ('z', 1)]
77 >>> sorted(frequencies(sanitise('The Quick BROWN fox jumped! over... '\
78 'the (9lazy) DOG')).items()) # doctest: +NORMALIZE_WHITESPACE
79 [('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1),
80 ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1),
81 ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1),
82 ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
83 >>> frequencies('abcdefabcdef')['x']
86 return collections
.Counter(c
for c
in text
)
89 def caesar_break(message
, fitness
=Pletters
):
90 """Breaks a Caesar cipher using frequency analysis
92 >>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrh' \
93 'ecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm') # doctest: +ELLIPSIS
94 (4, -130.849989015...)
95 >>> caesar_break('wxwmaxdgheetgwuxztgptedbgznitgwwhpguxyhkxbmhvvtlbhgtee' \
96 'raxlmhiixweblmxgxwmhmaxybkbgztgwztsxwbgmxgmert') # doctest: +ELLIPSIS
97 (19, -128.82410410...)
98 >>> caesar_break('yltbbqnqnzvguvaxurorgenafsbezqvagbnornfgsbevpnaabjurer' \
99 'svaquvzyvxrnznazlybequrvfohgriraabjtbaruraprur') # doctest: +ELLIPSIS
100 (13, -126.25403935...)
102 sanitised_message
= sanitise(message
)
104 best_fit
= float('-inf')
105 for shift
in range(26):
106 plaintext
= caesar_decipher(sanitised_message
, shift
)
107 fit
= fitness(plaintext
)
108 logger
.debug('Caesar break attempt using key {0} gives fit of {1} '
109 'and decrypt starting: {2}'.format(shift
, fit
,
114 logger
.info('Caesar break best fit: key {0} gives fit of {1} and '
115 'decrypt starting: {2}'.format(best_shift
, best_fit
,
116 caesar_decipher(sanitised_message
, best_shift
)[:50]))
117 return best_shift
, best_fit
119 def affine_break(message
, fitness
=Pletters
):
120 """Breaks an affine cipher using frequency analysis
122 >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls ' \
123 'omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ' \
124 'ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ' \
125 'ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls ' \
126 'bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai ' \
127 'kxd clm ckuxj.') # doctest: +ELLIPSIS
128 ((15, 22, True), -340.601181913...)
130 sanitised_message
= sanitise(message
)
133 best_one_based
= True
134 best_fit
= float("-inf")
135 for one_based
in [True, False]:
136 for multiplier
in [x
for x
in range(1, 26, 2) if x
!= 13]:
137 for adder
in range(26):
138 plaintext
= affine_decipher(sanitised_message
,
139 multiplier
, adder
, one_based
)
140 fit
= fitness(plaintext
)
141 logger
.debug('Affine break attempt using key {0}x+{1} ({2}) '
142 'gives fit of {3} and decrypt starting: {4}'.
143 format(multiplier
, adder
, one_based
, fit
,
147 best_multiplier
= multiplier
149 best_one_based
= one_based
150 logger
.info('Affine break best fit with key {0}x+{1} ({2}) gives fit of '
151 '{3} and decrypt starting: {4}'.format(
152 best_multiplier
, best_adder
, best_one_based
, best_fit
,
153 affine_decipher(sanitised_message
, best_multiplier
,
154 best_adder
, best_one_based
)[:50]))
155 return (best_multiplier
, best_adder
, best_one_based
), best_fit
157 def keyword_break(message
, wordlist
=keywords
, fitness
=Pletters
):
158 """Breaks a keyword substitution cipher using a dictionary and
161 >>> keyword_break(keyword_encipher('this is a test message for the ' \
162 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
163 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
164 (('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...)
167 best_wrap_alphabet
= True
168 best_fit
= float("-inf")
169 for wrap_alphabet
in KeywordWrapAlphabet
:
170 for keyword
in wordlist
:
171 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
172 fit
= fitness(plaintext
)
173 logger
.debug('Keyword break attempt using key {0} (wrap={1}) '
174 'gives fit of {2} and decrypt starting: {3}'.format(
175 keyword
, wrap_alphabet
, fit
,
176 sanitise(plaintext
)[:50]))
179 best_keyword
= keyword
180 best_wrap_alphabet
= wrap_alphabet
181 logger
.info('Keyword break best fit with key {0} (wrap={1}) gives fit of '
182 '{2} and decrypt starting: {3}'.format(best_keyword
,
183 best_wrap_alphabet
, best_fit
, sanitise(
184 keyword_decipher(message
, best_keyword
,
185 best_wrap_alphabet
))[:50]))
186 return (best_keyword
, best_wrap_alphabet
), best_fit
188 def keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
,
189 number_of_solutions
=1, chunksize
=500):
190 """Breaks a keyword substitution cipher using a dictionary and
193 >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \
194 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
195 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
196 (('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...)
197 >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \
198 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \
199 wordlist=['cat', 'elephant', 'kangaroo'], \
200 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
201 [(('elephant', <KeywordWrapAlphabet.from_last: 2>), -52.834575011...),
202 (('elephant', <KeywordWrapAlphabet.from_largest: 3>), -52.834575011...)]
205 helper_args
= [(message
, word
, wrap
, fitness
)
207 for wrap
in KeywordWrapAlphabet
]
208 # Gotcha: the helper function here needs to be defined at the top level
209 # (limitation of Pool.starmap)
210 breaks
= pool
.starmap(keyword_break_worker
, helper_args
, chunksize
)
211 if number_of_solutions
== 1:
212 return max(breaks
, key
=lambda k
: k
[1])
214 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
216 def keyword_break_worker(message
, keyword
, wrap_alphabet
, fitness
):
217 plaintext
= keyword_decipher(message
, keyword
, wrap_alphabet
)
218 fit
= fitness(plaintext
)
219 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
220 '{2} and decrypt starting: {3}'.format(keyword
,
221 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
222 return (keyword
, wrap_alphabet
), fit
224 def monoalphabetic_break_hillclimbing(message
, max_iterations
=10000000,
225 alphabet
=None, fitness
=Pletters
):
226 ciphertext
= unaccent(message
).lower()
228 alphabet
= list(string
.ascii_lowercase
)
229 random
.shuffle(alphabet
)
230 alphabet
= cat(alphabet
)
231 return monoalphabetic_break_hillclimbing_worker(ciphertext
, alphabet
,
232 max_iterations
, fitness
)
234 def monoalphabetic_break_hillclimbing_mp(message
, workers
=10,
235 max_iterations
= 10000000, alphabet
=None, fitness
=Pletters
, chunksize
=1):
237 ciphertext
= unaccent(message
).lower()
238 for i
in range(workers
):
240 this_alphabet
= alphabet
242 this_alphabet
= list(string
.ascii_lowercase
)
243 random
.shuffle(this_alphabet
)
244 this_alphabet
= cat(this_alphabet
)
245 worker_args
.append((ciphertext
, this_alphabet
, max_iterations
, fitness
))
247 breaks
= pool
.starmap(monoalphabetic_break_hillclimbing_worker
,
248 worker_args
, chunksize
)
249 return max(breaks
, key
=lambda k
: k
[1])
251 def monoalphabetic_break_hillclimbing_worker(message
, alphabet
,
252 max_iterations
, fitness
):
253 def swap(letters
, i
, j
):
259 return (letters
[:i
] + letters
[j
] + letters
[i
+1:j
] + letters
[i
] +
261 best_alphabet
= alphabet
262 best_fitness
= float('-inf')
263 for i
in range(max_iterations
):
264 alphabet
= swap(alphabet
, random
.randrange(26), random
.randrange(26))
265 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, alphabet
)
266 plaintext
= message
.translate(cipher_translation
)
267 if fitness(plaintext
) > best_fitness
:
268 best_fitness
= fitness(plaintext
)
269 best_alphabet
= alphabet
270 print(i
, best_alphabet
, best_fitness
, plaintext
)
271 return best_alphabet
, best_fitness
274 def vigenere_keyword_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
,
276 """Breaks a vigenere cipher using a dictionary and frequency analysis.
278 >>> vigenere_keyword_break_mp(vigenere_encipher(sanitise('this is a test ' \
279 'message for the vigenere decipherment'), 'cat'), \
280 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
281 ('cat', -52.9472712...)
284 helper_args
= [(message
, word
, fitness
)
285 for word
in wordlist
]
286 # Gotcha: the helper function here needs to be defined at the top level
287 # (limitation of Pool.starmap)
288 breaks
= pool
.starmap(vigenere_keyword_break_worker
, helper_args
,
290 return max(breaks
, key
=lambda k
: k
[1])
291 vigenere_keyword_break
= vigenere_keyword_break_mp
293 def vigenere_keyword_break_worker(message
, keyword
, fitness
):
294 plaintext
= vigenere_decipher(message
, keyword
)
295 fit
= fitness(plaintext
)
296 logger
.debug('Vigenere keyword break attempt using key {0} gives fit of '
297 '{1} and decrypt starting: {2}'.format(keyword
,
298 fit
, sanitise(plaintext
)[:50]))
302 def vigenere_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
303 """Breaks a Vigenere cipher with frequency analysis
305 >>> vigenere_frequency_break(vigenere_encipher(sanitise("It is time to " \
306 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
307 "afternoon when he left his jacket hanging on the easel in the " \
308 "attic. I jump every time I hear a footstep on the stairs, " \
309 "certain that the theft has been discovered and that I will " \
310 "be caught. The SS officer visits less often now that he is " \
311 "sure"), 'florence')) # doctest: +ELLIPSIS
312 ('florence', -307.5473096...)
314 def worker(message
, key_length
, fitness
):
315 splits
= every_nth(sanitised_message
, key_length
)
316 key
= cat([unpos(caesar_break(s
)[0]) for s
in splits
])
317 plaintext
= vigenere_decipher(message
, key
)
318 fit
= fitness(plaintext
)
320 sanitised_message
= sanitise(message
)
321 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
322 for i
in range(1, max_key_length
+1)])
323 return max(results
, key
=lambda k
: k
[1])
326 def beaufort_sub_break(message
, fitness
=Pletters
):
327 """Breaks one chunk of a Beaufort cipher with frequency analysis
329 >>> beaufort_sub_break('samwpplggnnmmyaazgympjapopnwiywwomwspgpjmefwmawx' \
330 'jafjhxwwwdigxshnlywiamhyshtasxptwueahhytjwsn') # doctest: +ELLIPSIS
332 >>> beaufort_sub_break('eyprzjjzznxymrygryjqmqhznjrjjapenejznawngnnezgza' \
333 'dgndknaogpdjneadadazlhkhxkryevrronrmdjnndjlo') # doctest: +ELLIPSIS
337 best_fit
= float('-inf')
338 for key
in range(26):
339 plaintext
= [unpos(key
- pos(l
)) for l
in message
]
340 fit
= fitness(plaintext
)
341 logger
.debug('Beaufort sub break attempt using key {0} gives fit of {1} '
342 'and decrypt starting: {2}'.format(key
, fit
,
347 logger
.info('Beaufort sub break best fit: key {0} gives fit of {1} and '
348 'decrypt starting: {2}'.format(best_key
, best_fit
,
349 cat([unpos(best_key
- pos(l
)) for l
in message
[:50]])))
350 return best_key
, best_fit
353 def beaufort_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
354 """Breaks a Beaufort cipher with frequency analysis
356 >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \
357 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
358 "afternoon when he left his jacket hanging on the easel in the " \
359 "attic. I jump every time I hear a footstep on the stairs, " \
360 "certain that the theft has been discovered and that I will " \
361 "be caught. The SS officer visits less often now " \
362 "that he is sure"), 'florence')) # doctest: +ELLIPSIS
363 ('florence', -307.5473096791...)
365 def worker(message
, key_length
, fitness
):
366 splits
= every_nth(message
, key_length
)
367 key
= cat([unpos(beaufort_sub_break(s
)[0]) for s
in splits
])
368 plaintext
= beaufort_decipher(message
, key
)
369 fit
= fitness(plaintext
)
371 sanitised_message
= sanitise(message
)
372 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
373 for i
in range(1, max_key_length
+1)])
374 return max(results
, key
=lambda k
: k
[1])
377 def beaufort_variant_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
378 """Breaks a Beaufort cipher with frequency analysis
380 >>> beaufort_variant_frequency_break(beaufort_variant_encipher(sanitise("It is time to " \
381 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
382 "afternoon when he left his jacket hanging on the easel in the " \
383 "attic. I jump every time I hear a footstep on the stairs, " \
384 "certain that the theft has been discovered and that I will " \
385 "be caught. The SS officer visits less often now " \
386 "that he is sure"), 'florence')) # doctest: +ELLIPSIS
387 ('florence', -307.5473096791...)
389 def worker(message
, key_length
, fitness
):
390 splits
= every_nth(sanitised_message
, key_length
)
391 key
= cat([unpos(-caesar_break(s
)[0]) for s
in splits
])
392 plaintext
= beaufort_variant_decipher(message
, key
)
393 fit
= fitness(plaintext
)
395 sanitised_message
= sanitise(message
)
396 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
397 for i
in range(1, max_key_length
+1)])
398 return max(results
, key
=lambda k
: k
[1])
400 def polybius_break_mp(message
, column_labels
, row_labels
,
401 letters_to_merge
=None,
402 wordlist
=keywords
, fitness
=Pletters
,
403 number_of_solutions
=1, chunksize
=500):
404 """Breaks a Polybius substitution cipher using a dictionary and
407 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
408 'polybius decipherment', 'elephant', 'abcde', 'abcde'), \
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', 'abcde', column_first=True), \
416 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
417 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', True), \
419 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
420 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=False), \
422 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
423 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
425 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
426 'polybius decipherment', 'elephant', 'abcde', 'pqrst', column_first=True), \
428 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
429 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'pqrst', True), \
432 if letters_to_merge
is None:
433 letters_to_merge
= {'j': 'i'}
435 helper_args
= [(message
, word
, wrap
,
436 column_labels
, row_labels
, column_first
,
440 for wrap
in KeywordWrapAlphabet
441 for column_first
in [False, True]]
442 # Gotcha: the helper function here needs to be defined at the top level
443 # (limitation of Pool.starmap)
444 breaks
= pool
.starmap(polybius_break_worker
, helper_args
, chunksize
)
445 if number_of_solutions
== 1:
446 return max(breaks
, key
=lambda k
: k
[1])
448 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
450 def polybius_break_worker(message
, keyword
, wrap_alphabet
,
451 column_order
, row_order
, column_first
,
454 plaintext
= polybius_decipher(message
, keyword
,
455 column_order
, row_order
,
456 column_first
=column_first
,
457 letters_to_merge
=letters_to_merge
,
458 wrap_alphabet
=wrap_alphabet
)
460 fit
= fitness(plaintext
)
463 logger
.debug('Polybius break attempt using key {0} (wrap={1}, merging {2}), '
464 'columns as {3}, rows as {4} (column_first={5}) '
465 'gives fit of {6} and decrypt starting: '
466 '{7}'.format(keyword
, wrap_alphabet
, letters_to_merge
,
467 column_order
, row_order
, column_first
,
468 fit
, sanitise(plaintext
)[:50]))
469 return (keyword
, wrap_alphabet
, column_order
, row_order
, column_first
), fit
472 def column_transposition_break_mp(message
, translist
=transpositions
,
473 fitness
=Pbigrams
, chunksize
=500):
474 """Breaks a column transposition cipher using a dictionary and
475 n-gram frequency analysis
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']}) # doctest: +ELLIPSIS
488 (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
489 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
490 "It is a truth universally acknowledged, that a single man in \
491 possession of a good fortune, must be in want of a wife. However \
492 little known the feelings or views of such a man may be on his \
493 first entering a neighbourhood, this truth is so well fixed in \
494 the minds of the surrounding families, that he is considered the \
495 rightful property of some one or other of their daughters."), \
497 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
498 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
499 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
500 fitness=Ptrigrams) # doctest: +ELLIPSIS
501 (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
504 helper_args
= [(message
, trans
, fillcolumnwise
, emptycolumnwise
,
506 for trans
in translist
507 for fillcolumnwise
in [True, False]
508 for emptycolumnwise
in [True, False]]
509 # Gotcha: the helper function here needs to be defined at the top level
510 # (limitation of Pool.starmap)
511 breaks
= pool
.starmap(column_transposition_break_worker
,
512 helper_args
, chunksize
)
513 return max(breaks
, key
=lambda k
: k
[1])
514 column_transposition_break
= column_transposition_break_mp
516 def column_transposition_break_worker(message
, transposition
,
517 fillcolumnwise
, emptycolumnwise
, fitness
):
518 plaintext
= column_transposition_decipher(message
, transposition
,
519 fillcolumnwise
=fillcolumnwise
, emptycolumnwise
=emptycolumnwise
)
520 fit
= fitness(sanitise(plaintext
))
521 logger
.debug('Column transposition break attempt using key {0} '
522 'gives fit of {1} and decrypt starting: {2}'.format(
524 sanitise(plaintext
)[:50]))
525 return (transposition
, fillcolumnwise
, emptycolumnwise
), fit
528 def scytale_break_mp(message
, max_key_length
=20,
529 fitness
=Pbigrams
, chunksize
=500):
530 """Breaks a scytale cipher using a range of lengths and
531 n-gram frequency analysis
533 >>> scytale_break_mp(scytale_encipher(sanitise( \
534 "It is a truth universally acknowledged, that a single man in \
535 possession of a good fortune, must be in want of a wife. However \
536 little known the feelings or views of such a man may be on his \
537 first entering a neighbourhood, this truth is so well fixed in \
538 the minds of the surrounding families, that he is considered the \
539 rightful property of some one or other of their daughters."), \
540 5)) # doctest: +ELLIPSIS
542 >>> scytale_break_mp(scytale_encipher(sanitise( \
543 "It is a truth universally acknowledged, that a single man in \
544 possession of a good fortune, must be in want of a wife. However \
545 little known the feelings or views of such a man may be on his \
546 first entering a neighbourhood, this truth is so well fixed in \
547 the minds of the surrounding families, that he is considered the \
548 rightful property of some one or other of their daughters."), \
550 fitness=Ptrigrams) # doctest: +ELLIPSIS
554 helper_args
= [(message
, trans
, False, True, fitness
)
556 [[col
for col
in range(math
.ceil(len(message
)/rows
))]
557 for rows
in range(1,max_key_length
+1)]]
558 # Gotcha: the helper function here needs to be defined at the top level
559 # (limitation of Pool.starmap)
560 breaks
= pool
.starmap(column_transposition_break_worker
,
561 helper_args
, chunksize
)
562 best
= max(breaks
, key
=lambda k
: k
[1])
563 return math
.trunc(len(message
) / len(best
[0][0])), best
[1]
564 scytale_break
= scytale_break_mp
567 def railfence_break(message
, max_key_length
=20,
568 fitness
=Pletters
, chunksize
=500):
569 """Breaks a hill cipher using a matrix of given rank and letter frequencies
574 sanitised_message
= sanitise(message
)
575 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
576 for i
in range(2, max_key_length
+1)])
577 return max(results
, key
=lambda k
: k
[1])
580 def railfence_break(message
, max_key_length
=20,
581 fitness
=Pbigrams
, chunksize
=500):
582 """Breaks a railfence cipher using a range of lengths and
583 n-gram frequency analysis
585 >>> railfence_break(railfence_encipher(sanitise( \
586 "It is a truth universally acknowledged, that a single man in \
587 possession of a good fortune, must be in want of a wife. However \
588 little known the feelings or views of such a man may be on his \
589 first entering a neighbourhood, this truth is so well fixed in \
590 the minds of the surrounding families, that he is considered the \
591 rightful property of some one or other of their daughters."), \
592 7)) # doctest: +ELLIPSIS
593 (7, -709.46467226...)
594 >>> railfence_break(railfence_encipher(sanitise( \
595 "It is a truth universally acknowledged, that a single man in \
596 possession of a good fortune, must be in want of a wife. However \
597 little known the feelings or views of such a man may be on his \
598 first entering a neighbourhood, this truth is so well fixed in \
599 the minds of the surrounding families, that he is considered the \
600 rightful property of some one or other of their daughters."), \
602 fitness=Ptrigrams) # doctest: +ELLIPSIS
605 def worker(message
, height
, fitness
):
606 plaintext
= railfence_decipher(message
, height
)
607 fit
= fitness(plaintext
)
610 sanitised_message
= sanitise(message
)
611 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
612 for i
in range(2, max_key_length
+1)])
613 return max(results
, key
=lambda k
: k
[1])
615 def amsco_break(message
, translist
=transpositions
, patterns
= [(1, 2), (2, 1)],
616 fillstyles
= [AmscoFillStyle
.continuous
,
617 AmscoFillStyle
.same_each_row
,
618 AmscoFillStyle
.reverse_each_row
],
621 """Breaks an AMSCO transposition cipher using a dictionary and
622 n-gram frequency analysis
624 >>> amsco_break(amsco_transposition_encipher(sanitise( \
625 "It is a truth universally acknowledged, that a single man in \
626 possession of a good fortune, must be in want of a wife. However \
627 little known the feelings or views of such a man may be on his \
628 first entering a neighbourhood, this truth is so well fixed in \
629 the minds of the surrounding families, that he is considered the \
630 rightful property of some one or other of their daughters."), \
632 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
633 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
634 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
635 patterns=[(1, 2)]) # doctest: +ELLIPSIS
636 (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
637 >>> amsco_break(amsco_transposition_encipher(sanitise( \
638 "It is a truth universally acknowledged, that a single man in \
639 possession of a good fortune, must be in want of a wife. However \
640 little known the feelings or views of such a man may be on his \
641 first entering a neighbourhood, this truth is so well fixed in \
642 the minds of the surrounding families, that he is considered the \
643 rightful property of some one or other of their daughters."), \
644 'encipher', fillpattern=(2, 1)), \
645 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
646 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
647 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
648 patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
649 (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
652 helper_args
= [(message
, trans
, pattern
, fillstyle
, fitness
)
653 for trans
in translist
654 for pattern
in patterns
655 for fillstyle
in fillstyles
]
656 # Gotcha: the helper function here needs to be defined at the top level
657 # (limitation of Pool.starmap)
658 breaks
= pool
.starmap(amsco_break_worker
, helper_args
, chunksize
)
659 return max(breaks
, key
=lambda k
: k
[1])
661 def amsco_break_worker(message
, transposition
,
662 pattern
, fillstyle
, fitness
):
663 plaintext
= amsco_transposition_decipher(message
, transposition
,
664 fillpattern
=pattern
, fillstyle
=fillstyle
)
665 fit
= fitness(sanitise(plaintext
))
666 logger
.debug('AMSCO transposition break attempt using key {0} and pattern'
667 '{1} ({2}) gives fit of {3} and decrypt starting: '
669 transposition
, pattern
, fillstyle
, fit
,
670 sanitise(plaintext
)[:50]))
671 return (transposition
, pattern
, fillstyle
), fit
674 def hill_break(message
, matrix_size
=2, fitness
=Pletters
,
675 number_of_solutions
=1, chunksize
=500):
677 all_matrices
= [np
.matrix(list(m
))
678 for m
in itertools
.product([list(r
)
679 for r
in itertools
.product(range(26), repeat
=matrix_size
)],
681 valid_matrices
= [m
for m
, d
in
682 zip(all_matrices
, (int(round(linalg
.det(m
))) for m
in all_matrices
))
687 helper_args
= [(message
, matrix
, fitness
)
688 for matrix
in valid_matrices
]
689 # Gotcha: the helper function here needs to be defined at the top level
690 # (limitation of Pool.starmap)
691 breaks
= pool
.starmap(hill_break_worker
, helper_args
, chunksize
)
692 if number_of_solutions
== 1:
693 return max(breaks
, key
=lambda k
: k
[1])
695 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
697 def hill_break_worker(message
, matrix
, fitness
):
698 plaintext
= hill_decipher(matrix
, message
)
699 fit
= fitness(plaintext
)
700 logger
.debug('Hill cipher break attempt using key {0} gives fit of '
701 '{1} and decrypt starting: {2}'.format(matrix
,
702 fit
, sanitise(plaintext
)[:50]))
705 def bifid_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
, max_period
=10,
706 number_of_solutions
=1, chunksize
=500):
707 """Breaks a keyword substitution cipher using a dictionary and
710 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
711 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
712 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
713 (('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...)
714 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
715 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
716 wordlist=['cat', 'elephant', 'kangaroo'], \
717 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
718 [(('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...),
719 (('elephant', <KeywordWrapAlphabet.from_largest: 3>, 0), -52.834575011...)]
722 helper_args
= [(message
, word
, wrap
, period
, fitness
)
724 for wrap
in KeywordWrapAlphabet
725 for period
in range(max_period
+1)]
726 # Gotcha: the helper function here needs to be defined at the top level
727 # (limitation of Pool.starmap)
728 breaks
= pool
.starmap(bifid_break_worker
, helper_args
, chunksize
)
729 if number_of_solutions
== 1:
730 return max(breaks
, key
=lambda k
: k
[1])
732 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
734 def bifid_break_worker(message
, keyword
, wrap_alphabet
, period
, fitness
):
735 plaintext
= bifid_decipher(message
, keyword
, wrap_alphabet
, period
=period
)
736 fit
= fitness(plaintext
)
737 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
738 '{2} and decrypt starting: {3}'.format(keyword
,
739 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
740 return (keyword
, wrap_alphabet
, period
), fit
743 def pocket_enigma_break_by_crib(message
, wheel_spec
, crib
, crib_position
):
744 """Break a pocket enigma using a crib (some plaintext that's expected to
745 be in a certain position). Returns a list of possible starting wheel
746 positions that could produce the crib.
748 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'h', 0)
750 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'he', 0)
752 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'll', 2)
754 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 2)
756 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 3)
758 >>> pocket_enigma_break_by_crib('aaaaa', 1, 'l', 3)
761 pe
= PocketEnigma(wheel
=wheel_spec
)
762 possible_positions
= []
763 for p
in string
.ascii_lowercase
:
765 plaintext
= pe
.decipher(message
)
766 if plaintext
[crib_position
:crib_position
+len(crib
)] == crib
:
767 possible_positions
+= [p
]
768 return possible_positions
771 def plot_frequency_histogram(freqs
, sort_key
=None):
772 x
= range(len(freqs
))
773 y
= [freqs
[l
] for l
in sorted(freqs
, key
=sort_key
)]
775 ax
= f
.add_axes([0.1, 0.1, 0.9, 0.9])
776 ax
.bar(x
, y
, align
='center')
778 ax
.set_xticklabels(sorted(freqs
, key
=sort_key
))
782 if __name__
== "__main__":