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