cipher.py

   1 import string
   2 import collections
   3 import logging
   4 from itertools import zip_longest, cycle
   5
   6
   7 logger = logging.getLogger(__name__)
   8 logger.addHandler(logging.FileHandler('cipher.log'))
   9 logger.setLevel(logging.WARNING)
  10 #logger.setLevel(logging.INFO)
  11 #logger.setLevel(logging.DEBUG)
  12
  13
  14 modular_division_table = [[0]*26 for x in range(26)]
  15 for a in range(26):
  16     for b in range(26):
  17         c = (a * b) % 26
  18         modular_division_table[b][c] = a
  19
  20 def letters(text):
  21     """Remove all non-alphabetic characters from a text
  22     >>> letters('The Quick')
  23     'TheQuick'
  24     >>> letters('The Quick BROWN fox jumped! over... the (9lazy) DOG')
  25     'TheQuickBROWNfoxjumpedoverthelazyDOG'
  26     """
  27     return ''.join([c for c in text if c in string.ascii_letters])
  28
  29 def sanitise(text):
  30     """Remove all non-alphabetic characters and convert the text to lowercase
  31
  32     >>> sanitise('The Quick')
  33     'thequick'
  34     >>> sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')
  35     'thequickbrownfoxjumpedoverthelazydog'
  36     """
  37     # sanitised = [c.lower() for c in text if c in string.ascii_letters]
  38     # return ''.join(sanitised)
  39     return letters(text).lower()
  40
  41 def ngrams(text, n):
  42     """Returns all n-grams of a text
  43
  44     >>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE
  45     ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn',
  46      'nf', 'fo', 'ox']
  47     >>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE
  48     ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow',
  49      'rown', 'ownf', 'wnfo', 'nfox']
  50     """
  51     return [text[i:i+n] for i in range(len(text)-n+1)]
  52
  53 def every_nth(text, n, fillvalue=''):
  54     """Returns n strings, each of which consists of every nth character,
  55     starting with the 0th, 1st, 2nd, ... (n-1)th character
  56
  57     >>> every_nth(string.ascii_lowercase, 5)
  58     ['afkpuz', 'bglqv', 'chmrw', 'dinsx', 'ejoty']
  59     >>> every_nth(string.ascii_lowercase, 1)
  60     ['abcdefghijklmnopqrstuvwxyz']
  61     >>> every_nth(string.ascii_lowercase, 26) # doctest: +NORMALIZE_WHITESPACE
  62     ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
  63      'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
  64     >>> every_nth(string.ascii_lowercase, 5, fillvalue='!')
  65     ['afkpuz', 'bglqv!', 'chmrw!', 'dinsx!', 'ejoty!']
  66     """
  67     split_text = [text[i:i+n] for i in range(0, len(text), n)]
  68     return [''.join(l) for l in zip_longest(*split_text, fillvalue=fillvalue)]
  69
  70 def combine_every_nth(split_text):
  71     """Reforms a text split into every_nth strings
  72
  73     >>> combine_every_nth(every_nth(string.ascii_lowercase, 5))
  74     'abcdefghijklmnopqrstuvwxyz'
  75     >>> combine_every_nth(every_nth(string.ascii_lowercase, 1))
  76     'abcdefghijklmnopqrstuvwxyz'
  77     >>> combine_every_nth(every_nth(string.ascii_lowercase, 26))
  78     'abcdefghijklmnopqrstuvwxyz'
  79     """
  80     return ''.join([''.join(l)
  81                     for l in zip_longest(*split_text, fillvalue='')])
  82
  83 def chunks(text, n, fillvalue=None):
  84     """Split a text into chunks of n characters
  85
  86     >>> chunks('abcdefghi', 3)
  87     ['abc', 'def', 'ghi']
  88     >>> chunks('abcdefghi', 4)
  89     ['abcd', 'efgh', 'i']
  90     >>> chunks('abcdefghi', 4, fillvalue='!')
  91     ['abcd', 'efgh', 'i!!!']
  92     """
  93     if fillvalue:
  94         padding = fillvalue[0] * (n - len(text) % n)
  95     else:
  96         padding = ''
  97     return [(text+padding)[i:i+n] for i in range(0, len(text), n)]
  98
  99 def transpose(items, transposition):
 100     """Moves items around according to the given transposition
 101
 102     >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
 103     ['a', 'b', 'c', 'd']
 104     >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
 105     ['d', 'b', 'c', 'a']
 106     >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
 107     [13, 12, 14, 11, 15, 10]
 108     """
 109     transposed = [''] * len(transposition)
 110     for p, t in enumerate(transposition):
 111        transposed[p] = items[t]
 112     return transposed
 113
 114 def untranspose(items, transposition):
 115     """Undoes a transpose
 116
 117     >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
 118     ['a', 'b', 'c', 'd']
 119     >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
 120     ['a', 'b', 'c', 'd']
 121     >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
 122     [10, 11, 12, 13, 14, 15]
 123     """
 124     transposed = [''] * len(transposition)
 125     for p, t in enumerate(transposition):
 126        transposed[t] = items[p]
 127     return transposed
 128
 129 def deduplicate(text):
 130     return list(collections.OrderedDict.fromkeys(text))
 131
 132
 133 def caesar_encipher_letter(letter, shift):
 134     """Encipher a letter, given a shift amount
 135
 136     >>> caesar_encipher_letter('a', 1)
 137     'b'
 138     >>> caesar_encipher_letter('a', 2)
 139     'c'
 140     >>> caesar_encipher_letter('b', 2)
 141     'd'
 142     >>> caesar_encipher_letter('x', 2)
 143     'z'
 144     >>> caesar_encipher_letter('y', 2)
 145     'a'
 146     >>> caesar_encipher_letter('z', 2)
 147     'b'
 148     >>> caesar_encipher_letter('z', -1)
 149     'y'
 150     >>> caesar_encipher_letter('a', -1)
 151     'z'
 152     """
 153     if letter in string.ascii_letters:
 154         if letter in string.ascii_uppercase:
 155             alphabet_start = ord('A')
 156         else:
 157             alphabet_start = ord('a')
 158         return chr(((ord(letter) - alphabet_start + shift) % 26) +
 159                    alphabet_start)
 160     else:
 161         return letter
 162
 163 def caesar_decipher_letter(letter, shift):
 164     """Decipher a letter, given a shift amount
 165
 166     >>> caesar_decipher_letter('b', 1)
 167     'a'
 168     >>> caesar_decipher_letter('b', 2)
 169     'z'
 170     """
 171     return caesar_encipher_letter(letter, -shift)
 172
 173 def caesar_encipher(message, shift):
 174     """Encipher a message with the Caesar cipher of given shift
 175
 176     >>> caesar_encipher('abc', 1)
 177     'bcd'
 178     >>> caesar_encipher('abc', 2)
 179     'cde'
 180     >>> caesar_encipher('abcxyz', 2)
 181     'cdezab'
 182     >>> caesar_encipher('ab cx yz', 2)
 183     'cd ez ab'
 184     """
 185     enciphered = [caesar_encipher_letter(l, shift) for l in message]
 186     return ''.join(enciphered)
 187
 188 def caesar_decipher(message, shift):
 189     """Encipher a message with the Caesar cipher of given shift
 190
 191     >>> caesar_decipher('bcd', 1)
 192     'abc'
 193     >>> caesar_decipher('cde', 2)
 194     'abc'
 195     >>> caesar_decipher('cd ez ab', 2)
 196     'ab cx yz'
 197     """
 198     return caesar_encipher(message, -shift)
 199
 200 def affine_encipher_letter(letter, multiplier=1, adder=0, one_based=True):
 201     """Encipher a letter, given a multiplier and adder
 202
 203     >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
 204             for l in string.ascii_uppercase])
 205     'HKNQTWZCFILORUXADGJMPSVYBE'
 206     >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
 207             for l in string.ascii_uppercase])
 208     'FILORUXADGJMPSVYBEHKNQTWZC'
 209     """
 210     if letter in string.ascii_letters:
 211         if letter in string.ascii_uppercase:
 212             alphabet_start = ord('A')
 213         else:
 214             alphabet_start = ord('a')
 215         letter_number = ord(letter) - alphabet_start
 216         if one_based: letter_number += 1
 217         cipher_number = (letter_number * multiplier + adder) % 26
 218         if one_based: cipher_number -= 1
 219         return chr(cipher_number % 26 + alphabet_start)
 220     else:
 221         return letter
 222
 223 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
 224     """Encipher a letter, given a multiplier and adder
 225
 226     >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
 227             for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
 228     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 229     >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
 230             for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
 231     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 232     """
 233     if letter in string.ascii_letters:
 234         if letter in string.ascii_uppercase:
 235             alphabet_start = ord('A')
 236         else:
 237             alphabet_start = ord('a')
 238         cipher_number = ord(letter) - alphabet_start
 239         if one_based: cipher_number += 1
 240         plaintext_number = ( modular_division_table[multiplier]
 241                                                    [(cipher_number - adder) % 26] )
 242         if one_based: plaintext_number -= 1
 243         return chr(plaintext_number % 26 + alphabet_start)
 244     else:
 245         return letter
 246
 247 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
 248     """Encipher a message
 249
 250     >>> affine_encipher('hours passed during which jerico tried every ' \
 251            'trick he could think of', 15, 22, True)
 252     'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
 253     """
 254     enciphered = [affine_encipher_letter(l, multiplier, adder, one_based)
 255                   for l in message]
 256     return ''.join(enciphered)
 257
 258 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
 259     """Decipher a message
 260
 261     >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
 262            'jfaoe ls omytd jlaxe mh', 15, 22, True)
 263     'hours passed during which jerico tried every trick he could think of'
 264     """
 265     enciphered = [affine_decipher_letter(l, multiplier, adder, one_based)
 266                   for l in message]
 267     return ''.join(enciphered)
 268
 269
 270 def keyword_cipher_alphabet_of(keyword, wrap_alphabet=0):
 271     """Find the cipher alphabet given a keyword.
 272     wrap_alphabet controls how the rest of the alphabet is added
 273     after the keyword.
 274     0 : from 'a'
 275     1 : from the last letter in the sanitised keyword
 276     2 : from the largest letter in the sanitised keyword
 277
 278     >>> keyword_cipher_alphabet_of('bayes')
 279     'bayescdfghijklmnopqrtuvwxz'
 280     >>> keyword_cipher_alphabet_of('bayes', 0)
 281     'bayescdfghijklmnopqrtuvwxz'
 282     >>> keyword_cipher_alphabet_of('bayes', 1)
 283     'bayestuvwxzcdfghijklmnopqr'
 284     >>> keyword_cipher_alphabet_of('bayes', 2)
 285     'bayeszcdfghijklmnopqrtuvwx'
 286     """
 287     if wrap_alphabet == 0:
 288         cipher_alphabet = ''.join(deduplicate(sanitise(keyword) +
 289                                               string.ascii_lowercase))
 290     else:
 291         if wrap_alphabet == 1:
 292             last_keyword_letter = deduplicate(sanitise(keyword))[-1]
 293         else:
 294             last_keyword_letter = sorted(sanitise(keyword))[-1]
 295         last_keyword_position = string.ascii_lowercase.find(
 296             last_keyword_letter) + 1
 297         cipher_alphabet = ''.join(
 298             deduplicate(sanitise(keyword) +
 299                         string.ascii_lowercase[last_keyword_position:] +
 300                         string.ascii_lowercase))
 301     return cipher_alphabet
 302
 303
 304 def keyword_encipher(message, keyword, wrap_alphabet=0):
 305     """Enciphers a message with a keyword substitution cipher.
 306     wrap_alphabet controls how the rest of the alphabet is added
 307     after the keyword.
 308     0 : from 'a'
 309     1 : from the last letter in the sanitised keyword
 310     2 : from the largest letter in the sanitised keyword
 311
 312     >>> keyword_encipher('test message', 'bayes')
 313     'rsqr ksqqbds'
 314     >>> keyword_encipher('test message', 'bayes', 0)
 315     'rsqr ksqqbds'
 316     >>> keyword_encipher('test message', 'bayes', 1)
 317     'lskl dskkbus'
 318     >>> keyword_encipher('test message', 'bayes', 2)
 319     'qspq jsppbcs'
 320     """
 321     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 322     cipher_translation = ''.maketrans(string.ascii_lowercase, cipher_alphabet)
 323     return message.lower().translate(cipher_translation)
 324
 325 def keyword_decipher(message, keyword, wrap_alphabet=0):
 326     """Deciphers a message with a keyword substitution cipher.
 327     wrap_alphabet controls how the rest of the alphabet is added
 328     after the keyword.
 329     0 : from 'a'
 330     1 : from the last letter in the sanitised keyword
 331     2 : from the largest letter in the sanitised keyword
 332
 333     >>> keyword_decipher('rsqr ksqqbds', 'bayes')
 334     'test message'
 335     >>> keyword_decipher('rsqr ksqqbds', 'bayes', 0)
 336     'test message'
 337     >>> keyword_decipher('lskl dskkbus', 'bayes', 1)
 338     'test message'
 339     >>> keyword_decipher('qspq jsppbcs', 'bayes', 2)
 340     'test message'
 341     """
 342     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 343     cipher_translation = ''.maketrans(cipher_alphabet, string.ascii_lowercase)
 344     return message.lower().translate(cipher_translation)
 345
 346 def scytale_encipher(message, rows):
 347     """Enciphers using the scytale transposition cipher.
 348     Message is padded with spaces to allow all rows to be the same length.
 349
 350     >>> scytale_encipher('thequickbrownfox', 3)
 351     'tcnhkfeboqrxuo iw '
 352     >>> scytale_encipher('thequickbrownfox', 4)
 353     'tubnhirfecooqkwx'
 354     >>> scytale_encipher('thequickbrownfox', 5)
 355     'tubn hirf ecoo qkwx '
 356     >>> scytale_encipher('thequickbrownfox', 6)
 357     'tqcrnxhukof eibwo '
 358     >>> scytale_encipher('thequickbrownfox', 7)
 359     'tqcrnx hukof  eibwo  '
 360     """
 361     if len(message) % rows != 0:
 362         message += ' '*(rows - len(message) % rows)
 363     row_length = round(len(message) / rows)
 364     slices = [message[i:i+row_length]
 365               for i in range(0, len(message), row_length)]
 366     return ''.join([''.join(r) for r in zip_longest(*slices, fillvalue='')])
 367
 368 def scytale_decipher(message, rows):
 369     """Deciphers using the scytale transposition cipher.
 370     Assumes the message is padded so that all rows are the same length.
 371
 372     >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
 373     'thequickbrownfox  '
 374     >>> scytale_decipher('tubnhirfecooqkwx', 4)
 375     'thequickbrownfox'
 376     >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
 377     'thequickbrownfox    '
 378     >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
 379     'thequickbrownfox  '
 380     >>> scytale_decipher('tqcrnx hukof  eibwo  ', 7)
 381     'thequickbrownfox     '
 382     """
 383     cols = round(len(message) / rows)
 384     columns = [message[i:i+rows] for i in range(0, cols * rows, rows)]
 385     return ''.join([''.join(c) for c in zip_longest(*columns, fillvalue='')])
 386
 387
 388 def transpositions_of(keyword):
 389     """Finds the transpostions given by a keyword. For instance, the keyword
 390     'clever' rearranges to 'celrv', so the first column (0) stays first, the
 391     second column (1) moves to third, the third column (2) moves to second,
 392     and so on.
 393
 394     If passed a tuple, assume it's already a transposition and just return it.
 395
 396     >>> transpositions_of('clever')
 397     (0, 2, 1, 4, 3)
 398     >>> transpositions_of('fred')
 399     (3, 2, 0, 1)
 400     >>> transpositions_of((3, 2, 0, 1))
 401     (3, 2, 0, 1)
 402     """
 403     if isinstance(keyword, tuple):
 404         return keyword
 405     else:
 406         key = deduplicate(keyword)
 407         transpositions = tuple(key.index(l) for l in sorted(key))
 408         return transpositions
 409
 410 def column_transposition_encipher(message, keyword, fillvalue=' ',
 411       columnwise=False):
 412     """Enciphers using the column transposition cipher.
 413     Message is padded to allow all rows to be the same length.
 414
 415     >>> column_transposition_encipher('hellothere', 'clever')
 416     'hleolteher'
 417     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
 418     'hleolthre!e!'
 419     >>> column_transposition_encipher('hellothere', 'clever', columnwise=True)
 420     'htleehoelr'
 421     """
 422     transpositions = transpositions_of(keyword)
 423     columns = every_nth(message, len(transpositions), fillvalue=fillvalue)
 424     transposed_columns = transpose(columns, transpositions)
 425     if columnwise:
 426         return ''.join(transposed_columns)
 427     else:
 428         return combine_every_nth(transposed_columns)
 429
 430 def column_transposition_decipher(message, keyword, fillvalue=' ',
 431       columnwise=False):
 432     """Deciphers using the column transposition cipher.
 433     Message is padded to allow all rows to be the same length.
 434
 435     >>> column_transposition_decipher('hleolteher', 'clever')
 436     'hellothere'
 437     >>> column_transposition_decipher('hleolthre!e!', 'cleverly', fillvalue='?')
 438     'hellothere!!'
 439     >>> column_transposition_decipher('htleehoelr', 'clever', columnwise=True)
 440     'hellothere'
 441     """
 442     transpositions = transpositions_of(keyword)
 443     if columnwise:
 444         columns = chunks(message, int(len(message) / len(transpositions)))
 445     else:
 446         columns = every_nth(message, len(transpositions), fillvalue=fillvalue)
 447     untransposed_columns = untranspose(columns, transpositions)
 448     return combine_every_nth(untransposed_columns)
 449
 450
 451 def vigenere_encipher(message, keyword):
 452     """Vigenere encipher
 453
 454     >>> vigenere_encipher('hello', 'abc')
 455     'hfnlp'
 456     """
 457     shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
 458     pairs = zip(message, cycle(shifts))
 459     return ''.join([caesar_encipher_letter(l, k) for l, k in pairs])
 460
 461 def vigenere_decipher(message, keyword):
 462     """Vigenere decipher
 463
 464     >>> vigenere_decipher('hfnlp', 'abc')
 465     'hello'
 466     """
 467     shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
 468     pairs = zip(message, cycle(shifts))
 469     return ''.join([caesar_decipher_letter(l, k) for l, k in pairs])
 470
 471 beaufort_encipher=vigenere_decipher
 472 beaufort_decipher=vigenere_encipher
 473
 474
 475 if __name__ == "__main__":
 476     import doctest
 477     doctest.testmod()