cipher/vigenere.py

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