cipher.py

   1 import string
   2 import collections
   3 import norms
   4 import logging
   5
   6 logger = logging.getLogger(__name__)
   7 logger.addHandler(logging.FileHandler('cipher.log'))
   8 logger.setLevel(logging.WARNING)
   9 #logger.setLevel(logging.INFO)
  10
  11 english_counts = collections.defaultdict(int)
  12 with open('count_1l.txt', 'r') as f:
  13     for line in f:
  14         (letter, count) = line.split("\t")
  15         english_counts[letter] = int(count)
  16 normalised_english_counts = norms.normalise(english_counts)
  17
  18 keywords = []
  19 with open('words.txt', 'r') as f:
  20     keywords = [line.rstrip() for line in f]
  21
  22
  23 modular_division_table = [[0]*26 for x in range(26)]
  24 for a in range(26):
  25     for b in range(26):
  26         c = (a * b) % 26
  27         modular_division_table[b][c] = a
  28
  29 modular_division_table_one_based = [[0]*27 for x in range(27)]
  30 for a in range(27):
  31     for b in range(27):
  32         c = ((a * b)-1) % 26 + 1
  33         modular_division_table_one_based[b][c] = a
  34
  35
  36
  37 def sanitise(text):
  38     """Remove all non-alphabetic characters and convert the text to lowercase
  39
  40     >>> sanitise('The Quick')
  41     'thequick'
  42     >>> sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')
  43     'thequickbrownfoxjumpedoverthelazydog'
  44     """
  45     sanitised = [c.lower() for c in text if c in string.ascii_letters]
  46     return ''.join(sanitised)
  47
  48 def ngrams(text, n):
  49     """Returns all n-grams of a text
  50
  51     >>> ngrams(sanitise('the quick brown fox'), 2)
  52     [('t', 'h'), ('h', 'e'), ('e', 'q'), ('q', 'u'), ('u', 'i'), ('i', 'c'), ('c', 'k'), ('k', 'b'), ('b', 'r'), ('r', 'o'), ('o', 'w'), ('w', 'n'), ('n', 'f'), ('f', 'o'), ('o', 'x')]
  53     >>> ngrams(sanitise('the quick brown fox'), 4)
  54     [('t', 'h', 'e', 'q'), ('h', 'e', 'q', 'u'), ('e', 'q', 'u', 'i'), ('q', 'u', 'i', 'c'), ('u', 'i', 'c', 'k'), ('i', 'c', 'k', 'b'), ('c', 'k', 'b', 'r'), ('k', 'b', 'r', 'o'), ('b', 'r', 'o', 'w'), ('r', 'o', 'w', 'n'), ('o', 'w', 'n', 'f'), ('w', 'n', 'f', 'o'), ('n', 'f', 'o', 'x')]
  55     """
  56     return [tuple(text[i:i+n]) for i in range(len(text)-n+1)]
  57
  58 def letter_frequencies(text):
  59     """Count the number of occurrences of each character in text
  60
  61     >>> sorted(letter_frequencies('abcdefabc').items())
  62     [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
  63     >>> sorted(letter_frequencies('the quick brown fox jumped over the lazy dog').items())
  64     [(' ', 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)]
  65     >>> sorted(letter_frequencies('The Quick BROWN fox jumped! over... the (9lazy) DOG').items())
  66     [(' ', 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)]
  67     >>> sorted(letter_frequencies(sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')).items())
  68     [('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)]
  69     """
  70     counts = collections.defaultdict(int)
  71     for c in text:
  72         counts[c] += 1
  73     return counts
  74
  75 def deduplicate(text):
  76     return list(collections.OrderedDict.fromkeys(text))
  77
  78
  79
  80 def caesar_encipher_letter(letter, shift):
  81     """Encipher a letter, given a shift amount
  82
  83     >>> caesar_encipher_letter('a', 1)
  84     'b'
  85     >>> caesar_encipher_letter('a', 2)
  86     'c'
  87     >>> caesar_encipher_letter('b', 2)
  88     'd'
  89     >>> caesar_encipher_letter('x', 2)
  90     'z'
  91     >>> caesar_encipher_letter('y', 2)
  92     'a'
  93     >>> caesar_encipher_letter('z', 2)
  94     'b'
  95     >>> caesar_encipher_letter('z', -1)
  96     'y'
  97     >>> caesar_encipher_letter('a', -1)
  98     'z'
  99     """
 100     if letter in string.ascii_letters:
 101         if letter in string.ascii_uppercase:
 102             alphabet_start = ord('A')
 103         else:
 104             alphabet_start = ord('a')
 105         return chr(((ord(letter) - alphabet_start + shift) % 26) + alphabet_start)
 106     else:
 107         return letter
 108
 109 def caesar_decipher_letter(letter, shift):
 110     """Decipher a letter, given a shift amount
 111
 112     >>> caesar_decipher_letter('b', 1)
 113     'a'
 114     >>> caesar_decipher_letter('b', 2)
 115     'z'
 116     """
 117     return caesar_encipher_letter(letter, -shift)
 118
 119 def caesar_encipher(message, shift):
 120     """Encipher a message with the Caesar cipher of given shift
 121
 122     >>> caesar_encipher('abc', 1)
 123     'bcd'
 124     >>> caesar_encipher('abc', 2)
 125     'cde'
 126     >>> caesar_encipher('abcxyz', 2)
 127     'cdezab'
 128     >>> caesar_encipher('ab cx yz', 2)
 129     'cd ez ab'
 130     """
 131     enciphered = [caesar_encipher_letter(l, shift) for l in message]
 132     return ''.join(enciphered)
 133
 134 def caesar_decipher(message, shift):
 135     """Encipher a message with the Caesar cipher of given shift
 136
 137     >>> caesar_decipher('bcd', 1)
 138     'abc'
 139     >>> caesar_decipher('cde', 2)
 140     'abc'
 141     >>> caesar_decipher('cd ez ab', 2)
 142     'ab cx yz'
 143     """
 144     return caesar_encipher(message, -shift)
 145
 146 def affine_encipher_letter(letter, multiplier=1, adder=0, one_based=True):
 147     """Encipher a letter, given a multiplier and adder
 148
 149     >>> ''.join([affine_encipher_letter(l, 3, 5, True) for l in string.ascii_uppercase])
 150     'HKNQTWZCFILORUXADGJMPSVYBE'
 151     >>> ''.join([affine_encipher_letter(l, 3, 5, False) for l in string.ascii_uppercase])
 152     'FILORUXADGJMPSVYBEHKNQTWZC'
 153     """
 154     if letter in string.ascii_letters:
 155         if letter in string.ascii_uppercase:
 156             alphabet_start = ord('A')
 157         else:
 158             alphabet_start = ord('a')
 159         letter_number = ord(letter) - alphabet_start
 160         if one_based: letter_number += 1
 161         raw_cipher_number = (letter_number * multiplier + adder)
 162         cipher_number = 0
 163         if one_based:
 164             cipher_number = (raw_cipher_number - 1) % 26
 165         else:
 166             cipher_number = raw_cipher_number % 26
 167         return chr(cipher_number + alphabet_start)
 168     else:
 169         return letter
 170
 171 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
 172     """Encipher a letter, given a multiplier and adder
 173
 174     >>> ''.join([affine_decipher_letter(l, 3, 5, True) for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
 175     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 176     >>> ''.join([affine_decipher_letter(l, 3, 5, False) for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
 177     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 178     """
 179     if letter in string.ascii_letters:
 180         if letter in string.ascii_uppercase:
 181             alphabet_start = ord('A')
 182         else:
 183             alphabet_start = ord('a')
 184         cipher_number = ord(letter) - alphabet_start
 185         if one_based: cipher_number += 1
 186         plaintext_number = 0
 187         if one_based:
 188             plaintext_number = (modular_division_table_one_based[multiplier][(cipher_number - adder + 26) % 26] - 1) % 26
 189         else:
 190             #plaintext_number = (modular_division_table[multiplier][cipher_number] - adder) % 26
 191             plaintext_number = modular_division_table[multiplier][(cipher_number - adder + 26) % 26]
 192         return chr(plaintext_number + alphabet_start)
 193     else:
 194         return letter
 195
 196 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
 197     """Encipher a message
 198
 199     >>> affine_encipher('hours passed during which jerico tried every trick he could think of', 15, 22, True)
 200     'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
 201     """
 202
 203     enciphered = [affine_encipher_letter(l, multiplier, adder, one_based) for l in message]
 204     return ''.join(enciphered)
 205
 206 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
 207     """Decipher a message
 208
 209     >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh', 15, 22, True)
 210     'hours passed during which jerico tried every trick he could think of'
 211     """
 212     enciphered = [affine_decipher_letter(l, multiplier, adder, one_based) for l in message]
 213     return ''.join(enciphered)
 214
 215
 216 def keyword_encipher(message, keyword):
 217     cipher_alphabet = ''.join(deduplicate(sanitise(keyword) + string.ascii_lowercase))
 218     cipher_translation = ''.maketrans(string.ascii_lowercase, cipher_alphabet)
 219     return message.lower().translate(cipher_translation)
 220
 221 def keyword_decipher(message, keyword):
 222     cipher_alphabet = ''.join(deduplicate(sanitise(keyword) + string.ascii_lowercase))
 223     cipher_translation = ''.maketrans(cipher_alphabet, string.ascii_lowercase)
 224     return message.lower().translate(cipher_translation)
 225
 226
 227 def caesar_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
 228     """Breaks a Caesar cipher using frequency analysis
 229
 230     >>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrhecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm')
 231     (4, 0.3186395289018361)
 232     >>> caesar_break('wxwmaxdgheetgwuxztgptedbgznitgwwhpguxyhkxbmhvvtlbhgteeraxlmhiixweblmxgxwmhmaxybkbgztgwztsxwbgmxgmert')
 233     (19, 0.4215290123583277)
 234     >>> caesar_break('yltbbqnqnzvguvaxurorgenafsbezqvagbnornfgsbevpnaabjurersvaquvzyvxrnznazlybequrvfohgriraabjtbaruraprur')
 235     (13, 0.31602920807545154)
 236     """
 237     sanitised_message = sanitise(message)
 238     best_shift = 0
 239     best_fit = float("inf")
 240     for shift in range(26):
 241         plaintext = caesar_decipher(sanitised_message, shift)
 242         frequencies = message_frequency_scaling(letter_frequencies(plaintext))
 243         fit = metric(target_frequencies, frequencies)
 244         logger.info('Caesar break attempt using key {0} gives fit of {1} and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
 245         if fit < best_fit:
 246             best_fit = fit
 247             best_shift = shift
 248     logger.info('Caesar break best fit: key {0} gives fit of {1} and decrypt starting: {2}'.format(best_shift, best_fit, caesar_decipher(sanitised_message, best_shift)[:50]))
 249     return best_shift, best_fit
 250
 251 def affine_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
 252     """Breaks an affine cipher using frequency analysis
 253
 254     >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai kxd clm ckuxj.')
 255     ((15, 22, True), 0.2357036181865554)
 256     """
 257     sanitised_message = sanitise(message)
 258     best_multiplier = 0
 259     best_adder = 0
 260     best_one_based = True
 261     best_fit = float("inf")
 262     for one_based in [True, False]:
 263         for multiplier in range(1, 26, 2):
 264             for adder in range(26):
 265                 plaintext = affine_decipher(sanitised_message, multiplier, adder, one_based)
 266                 frequencies = message_frequency_scaling(letter_frequencies(plaintext))
 267                 fit = metric(target_frequencies, frequencies)
 268                 logger.info('Affine break attempt using key {0}x+{1} ({2}) gives fit of {3} and decrypt starting: {4}'.format(multiplier, adder, one_based, fit, plaintext[:50]))
 269                 if fit < best_fit:
 270                     best_fit = fit
 271                     best_multiplier = multiplier
 272                     best_adder = adder
 273                     best_one_based = one_based
 274     logger.info('Affine break best fit with key {0}x+{1} ({2}) gives fit of {3} and decrypt starting: {4}'.format(best_multiplier, best_adder, best_one_based, best_fit, affine_decipher(sanitised_message, best_multiplier, best_adder, best_one_based)[:50]))
 275     return (best_multiplier, best_adder, best_one_based), best_fit
 276
 277
 278 def keyword_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
 279     best_keyword = ''
 280     best_fit = float("inf")
 281     for keyword in keywords:
 282         plaintext = keyword_decipher(message, keyword)
 283         frequencies = message_frequency_scaling(letter_frequencies(plaintext))
 284         fit = metric(target_frequencies, frequencies)
 285         logger.info('Keyword break attempt using key {0} gives fit of {1} and decrypt starting: {2}'.format(keyword, fit, plaintext[:50]))
 286         if fit < best_fit:
 287             best_fit = fit
 288             best_keyword = keyword
 289     logger.info('Keyword break best fit with key {0} gives fit of {1} and decrypt starting: {2}'.format(best_keyword, best_fit, keyword_decipher(message, best_keyword)[:50]))
 290     return best_keyword, best_fit
 291
 292
 293 if __name__ == "__main__":
 294     import doctest
 295     doctest.testmod()