cipher/vigenere.py

   1 from enum import Enum
   2 from itertools import starmap, cycle
   3 import multiprocessing
   4 from cipher.caesar import *
   5 from support.utilities import *
   6 from support.language_models import *
   7
   8 from logger import logger
   9
  10 def vigenere_encipher(message, keyword):
  11     """Vigenere encipher
  12
  13     >>> vigenere_encipher('hello', 'abc')
  14     'hfnlp'
  15     """
  16     shifts = [pos(l) for l in sanitise(keyword)]
  17     pairs = zip(message, cycle(shifts))
  18     return cat([caesar_encipher_letter(l, k) for l, k in pairs])
  19
  20 def vigenere_decipher(message, keyword):
  21     """Vigenere decipher
  22
  23     >>> vigenere_decipher('hfnlp', 'abc')
  24     'hello'
  25     """
  26     shifts = [pos(l) for l in sanitise(keyword)]
  27     pairs = zip(message, cycle(shifts))
  28     return cat([caesar_decipher_letter(l, k) for l, k in pairs])
  29
  30
  31 def beaufort_encipher(message, keyword):
  32     """Beaufort encipher
  33
  34     >>> beaufort_encipher('inhisjournaldatedtheidesofoctober', 'arcanaimperii')
  35     'sevsvrusyrrxfayyxuteemazudmpjmmwr'
  36     """
  37     shifts = [pos(l) for l in sanitise(keyword)]
  38     pairs = zip(message, cycle(shifts))
  39     return cat([unpos(k - pos(l)) for l, k in pairs])
  40
  41 beaufort_decipher = beaufort_encipher
  42
  43 beaufort_variant_encipher=vigenere_decipher
  44 beaufort_variant_decipher=vigenere_encipher
  45
  46
  47 def index_of_coincidence_scan(text, max_key_length=20):
  48     """Finds the index of coincidence of the text, using different chunk sizes."""
  49     stext = sanitise(text)
  50     iocs = {}
  51     for i in range(1, max_key_length + 1):
  52         splits = every_nth(stext, i)
  53         mean_ioc = sum(index_of_coincidence(s) for s in splits) / i
  54         iocs[i] = mean_ioc
  55     return iocs
  56
  57 def vigenere_keyword_break_mp(message, wordlist=keywords, fitness=Pletters,
  58                               chunksize=500):
  59     """Breaks a vigenere cipher using a dictionary and frequency analysis.
  60
  61     >>> vigenere_keyword_break_mp(vigenere_encipher(sanitise('this is a test ' \
  62              'message for the vigenere decipherment'), 'cat'), \
  63              wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
  64     ('cat', -52.9472712...)
  65     """
  66     with multiprocessing.Pool() as pool:
  67         helper_args = [(message, word, fitness)
  68                        for word in wordlist]
  69         # Gotcha: the helper function here needs to be defined at the top level
  70         #   (limitation of Pool.starmap)
  71         breaks = pool.starmap(vigenere_keyword_break_worker, helper_args,
  72                               chunksize)
  73         return max(breaks, key=lambda k: k[1])
  74 vigenere_keyword_break = vigenere_keyword_break_mp
  75
  76 def vigenere_keyword_break_worker(message, keyword, fitness):
  77     plaintext = vigenere_decipher(message, keyword)
  78     fit = fitness(plaintext)
  79     logger.debug('Vigenere keyword break attempt using key {0} gives fit of '
  80                  '{1} and decrypt starting: {2}'.format(keyword,
  81                      fit, sanitise(plaintext)[:50]))
  82     return keyword, fit
  83
  84
  85 def vigenere_frequency_break(message, max_key_length=20, fitness=Pletters):
  86     """Breaks a Vigenere cipher with frequency analysis
  87
  88     >>> vigenere_frequency_break(vigenere_encipher(sanitise("It is time to " \
  89             "run. She is ready and so am I. I stole Daniel's pocketbook this " \
  90             "afternoon when he left his jacket hanging on the easel in the " \
  91             "attic. I jump every time I hear a footstep on the stairs, " \
  92             "certain that the theft has been discovered and that I will " \
  93             "be caught. The SS officer visits less often now that he is " \
  94             "sure"), 'florence')) # doctest: +ELLIPSIS
  95     ('florence', -307.5473096...)
  96     """
  97     def worker(message, key_length, fitness):
  98         splits = every_nth(sanitised_message, key_length)
  99         key = cat([unpos(caesar_break(s)[0]) for s in splits])
 100         plaintext = vigenere_decipher(message, key)
 101         fit = fitness(plaintext)
 102         return key, fit
 103     sanitised_message = sanitise(message)
 104     results = starmap(worker, [(sanitised_message, i, fitness)
 105                                for i in range(1, max_key_length+1)])
 106     return max(results, key=lambda k: k[1])
 107
 108
 109 def beaufort_sub_break(message, fitness=Pletters):
 110     """Breaks one chunk of a Beaufort cipher with frequency analysis
 111
 112     >>> beaufort_sub_break('samwpplggnnmmyaazgympjapopnwiywwomwspgpjmefwmawx' \
 113       'jafjhxwwwdigxshnlywiamhyshtasxptwueahhytjwsn') # doctest: +ELLIPSIS
 114     (0, -117.4492...)
 115     >>> beaufort_sub_break('eyprzjjzznxymrygryjqmqhznjrjjapenejznawngnnezgza' \
 116       'dgndknaogpdjneadadazlhkhxkryevrronrmdjnndjlo') # doctest: +ELLIPSIS
 117     (17, -114.9598...)
 118     """
 119     best_shift = 0
 120     best_fit = float('-inf')
 121     for key in range(26):
 122         plaintext = [unpos(key - pos(l)) for l in message]
 123         fit = fitness(plaintext)
 124         logger.debug('Beaufort sub break attempt using key {0} gives fit of {1} '
 125                      'and decrypt starting: {2}'.format(key, fit,
 126                                                         plaintext[:50]))
 127         if fit > best_fit:
 128             best_fit = fit
 129             best_key = key
 130     logger.info('Beaufort sub break best fit: key {0} gives fit of {1} and '
 131                 'decrypt starting: {2}'.format(best_key, best_fit,
 132                     cat([unpos(best_key - pos(l)) for l in message[:50]])))
 133     return best_key, best_fit
 134
 135
 136 def beaufort_frequency_break(message, max_key_length=20, fitness=Pletters):
 137     """Breaks a Beaufort cipher with frequency analysis
 138
 139     >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \
 140             "run. She is ready and so am I. I stole Daniel's pocketbook this " \
 141             "afternoon when he left his jacket hanging on the easel in the " \
 142             "attic. I jump every time I hear a footstep on the stairs, " \
 143             "certain that the theft has been discovered and that I will " \
 144             "be caught. The SS officer visits less often now " \
 145             "that he is sure"), 'florence')) # doctest: +ELLIPSIS
 146     ('florence', -307.5473096791...)
 147     """
 148     def worker(message, key_length, fitness):
 149         splits = every_nth(message, key_length)
 150         key = cat([unpos(beaufort_sub_break(s)[0]) for s in splits])
 151         plaintext = beaufort_decipher(message, key)
 152         fit = fitness(plaintext)
 153         return key, fit
 154     sanitised_message = sanitise(message)
 155     results = starmap(worker, [(sanitised_message, i, fitness)
 156                                for i in range(1, max_key_length+1)])
 157     return max(results, key=lambda k: k[1])
 158
 159
 160 def beaufort_variant_frequency_break(message, max_key_length=20, fitness=Pletters):
 161     """Breaks a Beaufort cipher with frequency analysis
 162
 163     >>> beaufort_variant_frequency_break(beaufort_variant_encipher(sanitise("It is time to " \
 164             "run. She is ready and so am I. I stole Daniel's pocketbook this " \
 165             "afternoon when he left his jacket hanging on the easel in the " \
 166             "attic. I jump every time I hear a footstep on the stairs, " \
 167             "certain that the theft has been discovered and that I will " \
 168             "be caught. The SS officer visits less often now " \
 169             "that he is sure"), 'florence')) # doctest: +ELLIPSIS
 170     ('florence', -307.5473096791...)
 171     """
 172     def worker(message, key_length, fitness):
 173         splits = every_nth(sanitised_message, key_length)
 174         key = cat([unpos(-caesar_break(s)[0]) for s in splits])
 175         plaintext = beaufort_variant_decipher(message, key)
 176         fit = fitness(plaintext)
 177         return key, fit
 178     sanitised_message = sanitise(message)
 179     results = starmap(worker, [(sanitised_message, i, fitness)
 180                                for i in range(1, max_key_length+1)])
 181     return max(results, key=lambda k: k[1])
 182
 183 if __name__ == "__main__":
 184     import doctest