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