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_frequency_break(message
, max_key_length
=20, fitness
=Pletters
):
315 """Breaks a Beaufort cipher with frequency analysis
317 >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \
318 "run. She is ready and so am I. I stole Daniel's pocketbook this " \
319 "afternoon when he left his jacket hanging on the easel in the " \
320 "attic. I jump every time I hear a footstep on the stairs, " \
321 "certain that the theft has been discovered and that I will " \
322 "be caught. The SS officer visits less often now " \
323 "that he is sure"), 'florence')) # doctest: +ELLIPSIS
324 ('florence', -307.5473096791...)
326 def worker(message
, key_length
, fitness
):
327 splits
= every_nth(sanitised_message
, key_length
)
328 key
= cat([chr(-caesar_break(s
)[0] % 26 + ord('a'))
330 plaintext
= beaufort_decipher(message
, key
)
331 fit
= fitness(plaintext
)
333 sanitised_message
= sanitise(message
)
334 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
335 for i
in range(1, max_key_length
+1)])
336 return max(results
, key
=lambda k
: k
[1])
339 def polybius_break_mp(message
, column_labels
, row_labels
,
340 letters_to_merge
=None,
341 wordlist
=keywords
, fitness
=Pletters
,
342 number_of_solutions
=1, chunksize
=500):
343 """Breaks a Polybius substitution cipher using a dictionary and
346 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
347 'polybius decipherment', 'elephant', 'abcde', 'abcde'), \
349 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
350 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
352 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
353 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=True), \
355 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
356 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', True), \
358 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
359 'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=False), \
361 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
362 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
364 >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
365 'polybius decipherment', 'elephant', 'abcde', 'pqrst', column_first=True), \
367 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
368 (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'pqrst', True), \
371 if letters_to_merge
is None:
372 letters_to_merge
= {'j': 'i'}
374 helper_args
= [(message
, word
, wrap
,
375 column_labels
, row_labels
, column_first
,
379 for wrap
in KeywordWrapAlphabet
380 for column_first
in [False, True]]
381 # Gotcha: the helper function here needs to be defined at the top level
382 # (limitation of Pool.starmap)
383 breaks
= pool
.starmap(polybius_break_worker
, helper_args
, chunksize
)
384 if number_of_solutions
== 1:
385 return max(breaks
, key
=lambda k
: k
[1])
387 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
389 def polybius_break_worker(message
, keyword
, wrap_alphabet
,
390 column_order
, row_order
, column_first
,
393 plaintext
= polybius_decipher(message
, keyword
,
394 column_order
, row_order
,
395 column_first
=column_first
,
396 letters_to_merge
=letters_to_merge
,
397 wrap_alphabet
=wrap_alphabet
)
399 fit
= fitness(plaintext
)
402 logger
.debug('Polybius break attempt using key {0} (wrap={1}, merging {2}), '
403 'columns as {3}, rows as {4} (column_first={5}) '
404 'gives fit of {6} and decrypt starting: '
405 '{7}'.format(keyword
, wrap_alphabet
, letters_to_merge
,
406 column_order
, row_order
, column_first
,
407 fit
, sanitise(plaintext
)[:50]))
408 return (keyword
, wrap_alphabet
, column_order
, row_order
, column_first
), fit
411 def column_transposition_break_mp(message
, translist
=transpositions
,
412 fitness
=Pbigrams
, chunksize
=500):
413 """Breaks a column transposition cipher using a dictionary and
414 n-gram frequency analysis
416 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
417 "It is a truth universally acknowledged, that a single man in \
418 possession of a good fortune, must be in want of a wife. However \
419 little known the feelings or views of such a man may be on his \
420 first entering a neighbourhood, this truth is so well fixed in \
421 the minds of the surrounding families, that he is considered the \
422 rightful property of some one or other of their daughters."), \
424 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
425 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
426 (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
427 (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
428 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
429 "It is a truth universally acknowledged, that a single man in \
430 possession of a good fortune, must be in want of a wife. However \
431 little known the feelings or views of such a man may be on his \
432 first entering a neighbourhood, this truth is so well fixed in \
433 the minds of the surrounding families, that he is considered the \
434 rightful property of some one or other of their daughters."), \
436 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
437 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
438 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
439 fitness=Ptrigrams) # doctest: +ELLIPSIS
440 (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
443 helper_args
= [(message
, trans
, fillcolumnwise
, emptycolumnwise
,
445 for trans
in translist
446 for fillcolumnwise
in [True, False]
447 for emptycolumnwise
in [True, False]]
448 # Gotcha: the helper function here needs to be defined at the top level
449 # (limitation of Pool.starmap)
450 breaks
= pool
.starmap(column_transposition_break_worker
,
451 helper_args
, chunksize
)
452 return max(breaks
, key
=lambda k
: k
[1])
453 column_transposition_break
= column_transposition_break_mp
455 def column_transposition_break_worker(message
, transposition
,
456 fillcolumnwise
, emptycolumnwise
, fitness
):
457 plaintext
= column_transposition_decipher(message
, transposition
,
458 fillcolumnwise
=fillcolumnwise
, emptycolumnwise
=emptycolumnwise
)
459 fit
= fitness(sanitise(plaintext
))
460 logger
.debug('Column transposition break attempt using key {0} '
461 'gives fit of {1} and decrypt starting: {2}'.format(
463 sanitise(plaintext
)[:50]))
464 return (transposition
, fillcolumnwise
, emptycolumnwise
), fit
467 def scytale_break_mp(message
, max_key_length
=20,
468 fitness
=Pbigrams
, chunksize
=500):
469 """Breaks a scytale cipher using a range of lengths and
470 n-gram frequency analysis
472 >>> scytale_break_mp(scytale_encipher(sanitise( \
473 "It is a truth universally acknowledged, that a single man in \
474 possession of a good fortune, must be in want of a wife. However \
475 little known the feelings or views of such a man may be on his \
476 first entering a neighbourhood, this truth is so well fixed in \
477 the minds of the surrounding families, that he is considered the \
478 rightful property of some one or other of their daughters."), \
479 5)) # doctest: +ELLIPSIS
481 >>> scytale_break_mp(scytale_encipher(sanitise( \
482 "It is a truth universally acknowledged, that a single man in \
483 possession of a good fortune, must be in want of a wife. However \
484 little known the feelings or views of such a man may be on his \
485 first entering a neighbourhood, this truth is so well fixed in \
486 the minds of the surrounding families, that he is considered the \
487 rightful property of some one or other of their daughters."), \
489 fitness=Ptrigrams) # doctest: +ELLIPSIS
493 helper_args
= [(message
, trans
, False, True, fitness
)
495 [[col
for col
in range(math
.ceil(len(message
)/rows
))]
496 for rows
in range(1,max_key_length
+1)]]
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 best
= max(breaks
, key
=lambda k
: k
[1])
502 return math
.trunc(len(message
) / len(best
[0][0])), best
[1]
503 scytale_break
= scytale_break_mp
506 def railfence_break(message
, max_key_length
=20,
507 fitness
=Pletters
, chunksize
=500):
508 """Breaks a hill cipher using a matrix of given rank and letter frequencies
513 sanitised_message
= sanitise(message
)
514 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
515 for i
in range(2, max_key_length
+1)])
516 return max(results
, key
=lambda k
: k
[1])
519 def railfence_break(message
, max_key_length
=20,
520 fitness
=Pbigrams
, chunksize
=500):
521 """Breaks a railfence cipher using a range of lengths and
522 n-gram frequency analysis
524 >>> railfence_break(railfence_encipher(sanitise( \
525 "It is a truth universally acknowledged, that a single man in \
526 possession of a good fortune, must be in want of a wife. However \
527 little known the feelings or views of such a man may be on his \
528 first entering a neighbourhood, this truth is so well fixed in \
529 the minds of the surrounding families, that he is considered the \
530 rightful property of some one or other of their daughters."), \
531 7)) # doctest: +ELLIPSIS
532 (7, -709.46467226...)
533 >>> railfence_break(railfence_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."), \
541 fitness=Ptrigrams) # doctest: +ELLIPSIS
544 def worker(message
, height
, fitness
):
545 plaintext
= railfence_decipher(message
, height
)
546 fit
= fitness(plaintext
)
549 sanitised_message
= sanitise(message
)
550 results
= starmap(worker
, [(sanitised_message
, i
, fitness
)
551 for i
in range(2, max_key_length
+1)])
552 return max(results
, key
=lambda k
: k
[1])
554 def amsco_break(message
, translist
=transpositions
, patterns
= [(1, 2), (2, 1)],
555 fillstyles
= [AmscoFillStyle
.continuous
,
556 AmscoFillStyle
.same_each_row
,
557 AmscoFillStyle
.reverse_each_row
],
560 """Breaks an AMSCO transposition cipher using a dictionary and
561 n-gram frequency analysis
563 >>> amsco_break(amsco_transposition_encipher(sanitise( \
564 "It is a truth universally acknowledged, that a single man in \
565 possession of a good fortune, must be in want of a wife. However \
566 little known the feelings or views of such a man may be on his \
567 first entering a neighbourhood, this truth is so well fixed in \
568 the minds of the surrounding families, that he is considered the \
569 rightful property of some one or other of their daughters."), \
571 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
572 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
573 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
574 patterns=[(1, 2)]) # doctest: +ELLIPSIS
575 (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
576 >>> amsco_break(amsco_transposition_encipher(sanitise( \
577 "It is a truth universally acknowledged, that a single man in \
578 possession of a good fortune, must be in want of a wife. However \
579 little known the feelings or views of such a man may be on his \
580 first entering a neighbourhood, this truth is so well fixed in \
581 the minds of the surrounding families, that he is considered the \
582 rightful property of some one or other of their daughters."), \
583 'encipher', fillpattern=(2, 1)), \
584 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
585 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
586 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
587 patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
588 (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
591 helper_args
= [(message
, trans
, pattern
, fillstyle
, fitness
)
592 for trans
in translist
593 for pattern
in patterns
594 for fillstyle
in fillstyles
]
595 # Gotcha: the helper function here needs to be defined at the top level
596 # (limitation of Pool.starmap)
597 breaks
= pool
.starmap(amsco_break_worker
, helper_args
, chunksize
)
598 return max(breaks
, key
=lambda k
: k
[1])
600 def amsco_break_worker(message
, transposition
,
601 pattern
, fillstyle
, fitness
):
602 plaintext
= amsco_transposition_decipher(message
, transposition
,
603 fillpattern
=pattern
, fillstyle
=fillstyle
)
604 fit
= fitness(sanitise(plaintext
))
605 logger
.debug('AMSCO transposition break attempt using key {0} and pattern'
606 '{1} ({2}) gives fit of {3} and decrypt starting: '
608 transposition
, pattern
, fillstyle
, fit
,
609 sanitise(plaintext
)[:50]))
610 return (transposition
, pattern
, fillstyle
), fit
613 def hill_break(message
, matrix_size
=2, fitness
=Pletters
,
614 number_of_solutions
=1, chunksize
=500):
616 all_matrices
= [np
.matrix(list(m
))
617 for m
in itertools
.product([list(r
)
618 for r
in itertools
.product(range(26), repeat
=matrix_size
)],
620 valid_matrices
= [m
for m
, d
in
621 zip(all_matrices
, (int(round(linalg
.det(m
))) for m
in all_matrices
))
626 helper_args
= [(message
, matrix
, fitness
)
627 for matrix
in valid_matrices
]
628 # Gotcha: the helper function here needs to be defined at the top level
629 # (limitation of Pool.starmap)
630 breaks
= pool
.starmap(hill_break_worker
, helper_args
, chunksize
)
631 if number_of_solutions
== 1:
632 return max(breaks
, key
=lambda k
: k
[1])
634 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
636 def hill_break_worker(message
, matrix
, fitness
):
637 plaintext
= hill_decipher(matrix
, message
)
638 fit
= fitness(plaintext
)
639 logger
.debug('Hill cipher break attempt using key {0} gives fit of '
640 '{1} and decrypt starting: {2}'.format(matrix
,
641 fit
, sanitise(plaintext
)[:50]))
644 def bifid_break_mp(message
, wordlist
=keywords
, fitness
=Pletters
, max_period
=10,
645 number_of_solutions
=1, chunksize
=500):
646 """Breaks a keyword substitution cipher using a dictionary and
649 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
650 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
651 wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
652 (('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...)
653 >>> bifid_break_mp(bifid_encipher('this is a test message for the ' \
654 'keyword decipherment', 'elephant', wrap_alphabet=KeywordWrapAlphabet.from_last), \
655 wordlist=['cat', 'elephant', 'kangaroo'], \
656 number_of_solutions=2) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
657 [(('elephant', <KeywordWrapAlphabet.from_last: 2>, 0), -52.834575011...),
658 (('elephant', <KeywordWrapAlphabet.from_largest: 3>, 0), -52.834575011...)]
661 helper_args
= [(message
, word
, wrap
, period
, fitness
)
663 for wrap
in KeywordWrapAlphabet
664 for period
in range(max_period
+1)]
665 # Gotcha: the helper function here needs to be defined at the top level
666 # (limitation of Pool.starmap)
667 breaks
= pool
.starmap(bifid_break_worker
, helper_args
, chunksize
)
668 if number_of_solutions
== 1:
669 return max(breaks
, key
=lambda k
: k
[1])
671 return sorted(breaks
, key
=lambda k
: k
[1], reverse
=True)[:number_of_solutions
]
673 def bifid_break_worker(message
, keyword
, wrap_alphabet
, period
, fitness
):
674 plaintext
= bifid_decipher(message
, keyword
, wrap_alphabet
, period
=period
)
675 fit
= fitness(plaintext
)
676 logger
.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of '
677 '{2} and decrypt starting: {3}'.format(keyword
,
678 wrap_alphabet
, fit
, sanitise(plaintext
)[:50]))
679 return (keyword
, wrap_alphabet
, period
), fit
682 def pocket_enigma_break_by_crib(message
, wheel_spec
, crib
, crib_position
):
683 """Break a pocket enigma using a crib (some plaintext that's expected to
684 be in a certain position). Returns a list of possible starting wheel
685 positions that could produce the crib.
687 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'h', 0)
689 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'he', 0)
691 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'll', 2)
693 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 2)
695 >>> pocket_enigma_break_by_crib('kzpjlzmoga', 1, 'l', 3)
697 >>> pocket_enigma_break_by_crib('aaaaa', 1, 'l', 3)
700 pe
= PocketEnigma(wheel
=wheel_spec
)
701 possible_positions
= []
702 for p
in string
.ascii_lowercase
:
704 plaintext
= pe
.decipher(message
)
705 if plaintext
[crib_position
:crib_position
+len(crib
)] == crib
:
706 possible_positions
+= [p
]
707 return possible_positions
710 def plot_frequency_histogram(freqs
, sort_key
=None):
711 x
= range(len(freqs
))
712 y
= [freqs
[l
] for l
in sorted(freqs
, key
=sort_key
)]
714 ax
= f
.add_axes([0.1, 0.1, 0.9, 0.9])
715 ax
.bar(x
, y
, align
='center')
717 ax
.set_xticklabels(sorted(freqs
, key
=sort_key
))
721 if __name__
== "__main__":