cipher.py

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