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 transpose(items, transposition):
  84     """Moves items around according to the given transposition
  85
  86     >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
  87     ['a', 'b', 'c', 'd']
  88     >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
  89     ['d', 'b', 'c', 'a']
  90     >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
  91     [13, 12, 14, 11, 15, 10]
  92     """
  93     transposed = [''] * len(transposition)
  94     for p, t in enumerate(transposition):
  95        transposed[p] = items[t]
  96     return transposed
  97
  98 def untranspose(items, transposition):
  99     """Undoes a transpose
 100
 101     >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
 102     ['a', 'b', 'c', 'd']
 103     >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
 104     ['a', 'b', 'c', 'd']
 105     >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
 106     [10, 11, 12, 13, 14, 15]
 107     """
 108     transposed = [''] * len(transposition)
 109     for p, t in enumerate(transposition):
 110        transposed[t] = items[p]
 111     return transposed
 112
 113
 114
 115 def deduplicate(text):
 116     return list(collections.OrderedDict.fromkeys(text))
 117
 118
 119
 120 def caesar_encipher_letter(letter, shift):
 121     """Encipher a letter, given a shift amount
 122
 123     >>> caesar_encipher_letter('a', 1)
 124     'b'
 125     >>> caesar_encipher_letter('a', 2)
 126     'c'
 127     >>> caesar_encipher_letter('b', 2)
 128     'd'
 129     >>> caesar_encipher_letter('x', 2)
 130     'z'
 131     >>> caesar_encipher_letter('y', 2)
 132     'a'
 133     >>> caesar_encipher_letter('z', 2)
 134     'b'
 135     >>> caesar_encipher_letter('z', -1)
 136     'y'
 137     >>> caesar_encipher_letter('a', -1)
 138     'z'
 139     """
 140     if letter in string.ascii_letters:
 141         if letter in string.ascii_uppercase:
 142             alphabet_start = ord('A')
 143         else:
 144             alphabet_start = ord('a')
 145         return chr(((ord(letter) - alphabet_start + shift) % 26) +
 146                    alphabet_start)
 147     else:
 148         return letter
 149
 150 def caesar_decipher_letter(letter, shift):
 151     """Decipher a letter, given a shift amount
 152
 153     >>> caesar_decipher_letter('b', 1)
 154     'a'
 155     >>> caesar_decipher_letter('b', 2)
 156     'z'
 157     """
 158     return caesar_encipher_letter(letter, -shift)
 159
 160 def caesar_encipher(message, shift):
 161     """Encipher a message with the Caesar cipher of given shift
 162
 163     >>> caesar_encipher('abc', 1)
 164     'bcd'
 165     >>> caesar_encipher('abc', 2)
 166     'cde'
 167     >>> caesar_encipher('abcxyz', 2)
 168     'cdezab'
 169     >>> caesar_encipher('ab cx yz', 2)
 170     'cd ez ab'
 171     """
 172     enciphered = [caesar_encipher_letter(l, shift) for l in message]
 173     return ''.join(enciphered)
 174
 175 def caesar_decipher(message, shift):
 176     """Encipher a message with the Caesar cipher of given shift
 177
 178     >>> caesar_decipher('bcd', 1)
 179     'abc'
 180     >>> caesar_decipher('cde', 2)
 181     'abc'
 182     >>> caesar_decipher('cd ez ab', 2)
 183     'ab cx yz'
 184     """
 185     return caesar_encipher(message, -shift)
 186
 187 def affine_encipher_letter(letter, multiplier=1, adder=0, one_based=True):
 188     """Encipher a letter, given a multiplier and adder
 189
 190     >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
 191             for l in string.ascii_uppercase])
 192     'HKNQTWZCFILORUXADGJMPSVYBE'
 193     >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
 194             for l in string.ascii_uppercase])
 195     'FILORUXADGJMPSVYBEHKNQTWZC'
 196     """
 197     if letter in string.ascii_letters:
 198         if letter in string.ascii_uppercase:
 199             alphabet_start = ord('A')
 200         else:
 201             alphabet_start = ord('a')
 202         letter_number = ord(letter) - alphabet_start
 203         if one_based: letter_number += 1
 204         cipher_number = (letter_number * multiplier + adder) % 26
 205         if one_based: cipher_number -= 1
 206         return chr(cipher_number % 26 + alphabet_start)
 207     else:
 208         return letter
 209
 210 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
 211     """Encipher a letter, given a multiplier and adder
 212
 213     >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
 214             for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
 215     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 216     >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
 217             for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
 218     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 219     """
 220     if letter in string.ascii_letters:
 221         if letter in string.ascii_uppercase:
 222             alphabet_start = ord('A')
 223         else:
 224             alphabet_start = ord('a')
 225         cipher_number = ord(letter) - alphabet_start
 226         if one_based: cipher_number += 1
 227         plaintext_number = ( modular_division_table[multiplier]
 228                                                    [(cipher_number - adder) % 26] )
 229         if one_based: plaintext_number -= 1
 230         return chr(plaintext_number % 26 + alphabet_start)
 231     else:
 232         return letter
 233
 234 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
 235     """Encipher a message
 236
 237     >>> affine_encipher('hours passed during which jerico tried every ' \
 238            'trick he could think of', 15, 22, True)
 239     'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
 240     """
 241     enciphered = [affine_encipher_letter(l, multiplier, adder, one_based)
 242                   for l in message]
 243     return ''.join(enciphered)
 244
 245 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
 246     """Decipher a message
 247
 248     >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
 249            'jfaoe ls omytd jlaxe mh', 15, 22, True)
 250     'hours passed during which jerico tried every trick he could think of'
 251     """
 252     enciphered = [affine_decipher_letter(l, multiplier, adder, one_based)
 253                   for l in message]
 254     return ''.join(enciphered)
 255
 256
 257 def keyword_cipher_alphabet_of(keyword, wrap_alphabet=0):
 258     """Find the cipher alphabet given a keyword.
 259     wrap_alphabet controls how the rest of the alphabet is added
 260     after the keyword.
 261     0 : from 'a'
 262     1 : from the last letter in the sanitised keyword
 263     2 : from the largest letter in the sanitised keyword
 264
 265     >>> keyword_cipher_alphabet_of('bayes')
 266     'bayescdfghijklmnopqrtuvwxz'
 267     >>> keyword_cipher_alphabet_of('bayes', 0)
 268     'bayescdfghijklmnopqrtuvwxz'
 269     >>> keyword_cipher_alphabet_of('bayes', 1)
 270     'bayestuvwxzcdfghijklmnopqr'
 271     >>> keyword_cipher_alphabet_of('bayes', 2)
 272     'bayeszcdfghijklmnopqrtuvwx'
 273     """
 274     if wrap_alphabet == 0:
 275         cipher_alphabet = ''.join(deduplicate(sanitise(keyword) +
 276                                               string.ascii_lowercase))
 277     else:
 278         if wrap_alphabet == 1:
 279             last_keyword_letter = deduplicate(sanitise(keyword))[-1]
 280         else:
 281             last_keyword_letter = sorted(sanitise(keyword))[-1]
 282         last_keyword_position = string.ascii_lowercase.find(
 283             last_keyword_letter) + 1
 284         cipher_alphabet = ''.join(
 285             deduplicate(sanitise(keyword) +
 286                         string.ascii_lowercase[last_keyword_position:] +
 287                         string.ascii_lowercase))
 288     return cipher_alphabet
 289
 290
 291 def keyword_encipher(message, keyword, wrap_alphabet=0):
 292     """Enciphers a message with a keyword substitution cipher.
 293     wrap_alphabet controls how the rest of the alphabet is added
 294     after the keyword.
 295     0 : from 'a'
 296     1 : from the last letter in the sanitised keyword
 297     2 : from the largest letter in the sanitised keyword
 298
 299     >>> keyword_encipher('test message', 'bayes')
 300     'rsqr ksqqbds'
 301     >>> keyword_encipher('test message', 'bayes', 0)
 302     'rsqr ksqqbds'
 303     >>> keyword_encipher('test message', 'bayes', 1)
 304     'lskl dskkbus'
 305     >>> keyword_encipher('test message', 'bayes', 2)
 306     'qspq jsppbcs'
 307     """
 308     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 309     cipher_translation = ''.maketrans(string.ascii_lowercase, cipher_alphabet)
 310     return message.lower().translate(cipher_translation)
 311
 312 def keyword_decipher(message, keyword, wrap_alphabet=0):
 313     """Deciphers a message with a keyword substitution cipher.
 314     wrap_alphabet controls how the rest of the alphabet is added
 315     after the keyword.
 316     0 : from 'a'
 317     1 : from the last letter in the sanitised keyword
 318     2 : from the largest letter in the sanitised keyword
 319
 320     >>> keyword_decipher('rsqr ksqqbds', 'bayes')
 321     'test message'
 322     >>> keyword_decipher('rsqr ksqqbds', 'bayes', 0)
 323     'test message'
 324     >>> keyword_decipher('lskl dskkbus', 'bayes', 1)
 325     'test message'
 326     >>> keyword_decipher('qspq jsppbcs', 'bayes', 2)
 327     'test message'
 328     """
 329     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 330     cipher_translation = ''.maketrans(cipher_alphabet, string.ascii_lowercase)
 331     return message.lower().translate(cipher_translation)
 332
 333 def scytale_encipher(message, rows):
 334     """Enciphers using the scytale transposition cipher.
 335     Message is padded with spaces to allow all rows to be the same length.
 336
 337     >>> scytale_encipher('thequickbrownfox', 3)
 338     'tcnhkfeboqrxuo iw '
 339     >>> scytale_encipher('thequickbrownfox', 4)
 340     'tubnhirfecooqkwx'
 341     >>> scytale_encipher('thequickbrownfox', 5)
 342     'tubn hirf ecoo qkwx '
 343     >>> scytale_encipher('thequickbrownfox', 6)
 344     'tqcrnxhukof eibwo '
 345     >>> scytale_encipher('thequickbrownfox', 7)
 346     'tqcrnx hukof  eibwo  '
 347     """
 348     if len(message) % rows != 0:
 349         message += ' '*(rows - len(message) % rows)
 350     row_length = round(len(message) / rows)
 351     slices = [message[i:i+row_length]
 352               for i in range(0, len(message), row_length)]
 353     return ''.join([''.join(r) for r in zip_longest(*slices, fillvalue='')])
 354
 355 def scytale_decipher(message, rows):
 356     """Deciphers using the scytale transposition cipher.
 357     Assumes the message is padded so that all rows are the same length.
 358
 359     >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
 360     'thequickbrownfox  '
 361     >>> scytale_decipher('tubnhirfecooqkwx', 4)
 362     'thequickbrownfox'
 363     >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
 364     'thequickbrownfox    '
 365     >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
 366     'thequickbrownfox  '
 367     >>> scytale_decipher('tqcrnx hukof  eibwo  ', 7)
 368     'thequickbrownfox     '
 369     """
 370     cols = round(len(message) / rows)
 371     columns = [message[i:i+rows] for i in range(0, cols * rows, rows)]
 372     return ''.join([''.join(c) for c in zip_longest(*columns, fillvalue='')])
 373
 374
 375 def transpositions_of(keyword):
 376     """Finds the transpostions given by a keyword. For instance, the keyword
 377     'clever' rearranges to 'celrv', so the first column (0) stays first, the
 378     second column (1) moves to third, the third column (2) moves to second,
 379     and so on.
 380
 381     If passed a tuple, assume it's already a transposition and just return it.
 382
 383     >>> transpositions_of('clever')
 384     (0, 2, 1, 4, 3)
 385     >>> transpositions_of('fred')
 386     (3, 2, 0, 1)
 387     >>> transpositions_of((3, 2, 0, 1))
 388     (3, 2, 0, 1)
 389     """
 390     if isinstance(keyword, tuple):
 391         return keyword
 392     else:
 393         key = deduplicate(keyword)
 394         transpositions = tuple(key.index(l) for l in sorted(key))
 395         return transpositions
 396
 397 def column_transposition_encipher(message, keyword, fillvalue=' '):
 398     """Enciphers using the column transposition cipher.
 399     Message is padded to allow all rows to be the same length.
 400
 401     >>> column_transposition_encipher('hellothere', 'clever')
 402     'hleolteher'
 403     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
 404     'hleolthre!e!'
 405     """
 406     return column_transposition_worker(message, keyword, encipher=True,
 407                                        fillvalue=fillvalue)
 408
 409 def column_transposition_decipher(message, keyword, fillvalue=' '):
 410     """Deciphers using the column transposition cipher.
 411     Message is padded to allow all rows to be the same length.
 412
 413     >>> column_transposition_decipher('hleolteher', 'clever')
 414     'hellothere'
 415     >>> column_transposition_decipher('hleolthre!e!', 'cleverly', fillvalue='?')
 416     'hellothere!!'
 417     """
 418     return column_transposition_worker(message, keyword, encipher=False,
 419                                        fillvalue=fillvalue)
 420
 421 def column_transposition_worker(message, keyword,
 422                                 encipher=True, fillvalue=' '):
 423     """Does the actual work of the column transposition cipher.
 424     Message is padded with spaces to allow all rows to be the same length.
 425
 426     >>> column_transposition_worker('hellothere', 'clever')
 427     'hleolteher'
 428     >>> column_transposition_worker('hellothere', 'clever', encipher=True)
 429     'hleolteher'
 430     >>> column_transposition_worker('hleolteher', 'clever', encipher=False)
 431     'hellothere'
 432     """
 433     transpositions = transpositions_of(keyword)
 434     columns = every_nth(message, len(transpositions), fillvalue=fillvalue)
 435     if encipher:
 436         transposed_columns = transpose(columns, transpositions)
 437     else:
 438         transposed_columns = untranspose(columns, transpositions)
 439     return combine_every_nth(transposed_columns)
 440
 441 def vigenere_encipher(message, keyword):
 442     """Vigenere encipher
 443
 444     >>> vigenere_encipher('hello', 'abc')
 445     'hfnlp'
 446     """
 447     shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
 448     pairs = zip(message, cycle(shifts))
 449     return ''.join([caesar_encipher_letter(l, k) for l, k in pairs])
 450
 451 def vigenere_decipher(message, keyword):
 452     """Vigenere decipher
 453
 454     >>> vigenere_decipher('hfnlp', 'abc')
 455     'hello'
 456     """
 457     shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
 458     pairs = zip(message, cycle(shifts))
 459     return ''.join([caesar_decipher_letter(l, k) for l, k in pairs])
 460
 461
 462
 463 if __name__ == "__main__":
 464     import doctest
 465     doctest.testmod()