cipher.py

   1 import string
   2 import collections
   3 import norms
   4
   5 english_counts = collections.defaultdict(int)
   6 with open('count_1l.txt', 'r') as f:
   7     for line in f:
   8         (letter, count) = line.split("\t")
   9         english_counts[letter] = int(count)
  10 normalised_english_counts = norms.normalise(english_counts)
  11
  12
  13 def sanitise(text):
  14     """Remove all non-alphabetic characters and convert the text to lowercase
  15
  16     >>> sanitise('The Quick')
  17     'thequick'
  18     >>> sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')
  19     'thequickbrownfoxjumpedoverthelazydog'
  20     """
  21     sanitised = [c.lower() for c in text if c in string.ascii_letters]
  22     return ''.join(sanitised)
  23
  24 def letter_frequencies(text):
  25     """Count the number of occurrences of each character in text
  26
  27     >>> sorted(letter_frequencies('abcdefabc').items())
  28     [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
  29     >>> sorted(letter_frequencies('the quick brown fox jumped over the lazy dog').items())
  30     [(' ', 8), ('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
  31     >>> sorted(letter_frequencies('The Quick BROWN fox jumped! over... the (9lazy) DOG').items())
  32     [(' ', 8), ('!', 1), ('(', 1), (')', 1), ('.', 3), ('9', 1), ('B', 1), ('D', 1), ('G', 1), ('N', 1), ('O', 2), ('Q', 1), ('R', 1), ('T', 1), ('W', 1), ('a', 1), ('c', 1), ('d', 1), ('e', 4), ('f', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('o', 2), ('p', 1), ('r', 1), ('t', 1), ('u', 2), ('v', 1), ('x', 1), ('y', 1), ('z', 1)]
  33     >>> sorted(letter_frequencies(sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')).items())
  34     [('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
  35     """
  36     counts = collections.defaultdict(int)
  37     for c in text:
  38         counts[c] += 1
  39     return counts
  40
  41 def caesar_encipher_letter(letter, shift):
  42     """Encipher a letter, given a shift amount
  43
  44     >>> caesar_encipher_letter('a', 1)
  45     'b'
  46     >>> caesar_encipher_letter('a', 2)
  47     'c'
  48     >>> caesar_encipher_letter('b', 2)
  49     'd'
  50     >>> caesar_encipher_letter('x', 2)
  51     'z'
  52     >>> caesar_encipher_letter('y', 2)
  53     'a'
  54     >>> caesar_encipher_letter('z', 2)
  55     'b'
  56     >>> caesar_encipher_letter('z', -1)
  57     'y'
  58     >>> caesar_encipher_letter('a', -1)
  59     'z'
  60     """
  61     if letter in string.ascii_letters:
  62         if letter in string.ascii_uppercase:
  63             alphabet_start = ord('A')
  64         else:
  65             alphabet_start = ord('a')
  66         return chr(((ord(letter) - alphabet_start + shift) % 26) + alphabet_start)
  67     else:
  68         return letter
  69
  70 def caesar_decipher_letter(letter, shift):
  71     """Decipher a letter, given a shift amount
  72
  73     >>> caesar_decipher_letter('b', 1)
  74     'a'
  75     >>> caesar_decipher_letter('b', 2)
  76     'z'
  77     """
  78     return caesar_encipher_letter(letter, -shift)
  79
  80 def caesar_encipher(message, shift):
  81     """Encipher a message with the Caesar cipher of given shift
  82
  83     >>> caesar_encipher('abc', 1)
  84     'bcd'
  85     >>> caesar_encipher('abc', 2)
  86     'cde'
  87     >>> caesar_encipher('abcxyz', 2)
  88     'cdezab'
  89     >>> caesar_encipher('ab cx yz', 2)
  90     'cd ez ab'
  91     """
  92     enciphered = [caesar_encipher_letter(l, shift) for l in message]
  93     return ''.join(enciphered)
  94
  95 def caesar_decipher(message, shift):
  96     """Encipher a message with the Caesar cipher of given shift
  97
  98     >>> caesar_decipher('bcd', 1)
  99     'abc'
 100     >>> caesar_decipher('cde', 2)
 101     'abc'
 102     >>> caesar_decipher('cd ez ab', 2)
 103     'ab cx yz'
 104     """
 105     return caesar_encipher(message, -shift)
 106
 107 def caesar_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
 108     sanitised_message = sanitise(message)
 109     best_shift = 0
 110     best_fit = float("inf")
 111     for shift in range(1, 25):
 112         plaintext = caesar_decipher(sanitised_message, shift)
 113         frequencies = message_frequency_scaling(letter_frequencies(plaintext))
 114         fit = metric(target_frequencies, frequencies)
 115         if fit < best_fit:
 116             best_fit = fit
 117             best_shift = shift
 118     return best_shift, best_fit
 119
 120
 121 if __name__ == "__main__":
 122     import doctest
 123     doctest.testmod()