cipherbreak.py

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