cipher.py

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