cipher.py

   1 """A set of ciphers with implementations for both enciphering and deciphering
   2 them. See cipherbreak for automatic breaking of these ciphers
   3 """
   4
   5 import string
   6 import collections
   7 from enum import Enum
   8 from language_models import unaccent, sanitise
   9
  10
  11 modular_division_table = [[0]*26 for _ in range(26)]
  12 for a in range(26):
  13     for b in range(26):
  14         c = (a * b) % 26
  15         modular_division_table[b][c] = a
  16
  17
  18 def deduplicate(text):
  19     """If a string contains duplicate letters, remove all but the first. Retain
  20     the order of the letters.
  21
  22     >>> deduplicate('cat')
  23     ['c', 'a', 't']
  24     >>> deduplicate('happy')
  25     ['h', 'a', 'p', 'y']
  26     >>> deduplicate('cattca')
  27     ['c', 'a', 't']
  28     """
  29     return list(collections.OrderedDict.fromkeys(text))
  30
  31
  32 def caesar_encipher_letter(accented_letter, shift):
  33     """Encipher a letter, given a shift amount
  34
  35     >>> caesar_encipher_letter('a', 1)
  36     'b'
  37     >>> caesar_encipher_letter('a', 2)
  38     'c'
  39     >>> caesar_encipher_letter('b', 2)
  40     'd'
  41     >>> caesar_encipher_letter('x', 2)
  42     'z'
  43     >>> caesar_encipher_letter('y', 2)
  44     'a'
  45     >>> caesar_encipher_letter('z', 2)
  46     'b'
  47     >>> caesar_encipher_letter('z', -1)
  48     'y'
  49     >>> caesar_encipher_letter('a', -1)
  50     'z'
  51     >>> caesar_encipher_letter('A', 1)
  52     'B'
  53     >>> caesar_encipher_letter('é', 1)
  54     'f'
  55     """
  56     letter = unaccent(accented_letter)
  57     if letter in string.ascii_letters:
  58         if letter in string.ascii_uppercase:
  59             alphabet_start = ord('A')
  60         else:
  61             alphabet_start = ord('a')
  62         return chr(((ord(letter) - alphabet_start + shift) % 26) +
  63                    alphabet_start)
  64     else:
  65         return letter
  66
  67 def caesar_decipher_letter(letter, shift):
  68     """Decipher a letter, given a shift amount
  69
  70     >>> caesar_decipher_letter('b', 1)
  71     'a'
  72     >>> caesar_decipher_letter('b', 2)
  73     'z'
  74     """
  75     return caesar_encipher_letter(letter, -shift)
  76
  77 def caesar_encipher(message, shift):
  78     """Encipher a message with the Caesar cipher of given shift
  79
  80     >>> caesar_encipher('abc', 1)
  81     'bcd'
  82     >>> caesar_encipher('abc', 2)
  83     'cde'
  84     >>> caesar_encipher('abcxyz', 2)
  85     'cdezab'
  86     >>> caesar_encipher('ab cx yz', 2)
  87     'cd ez ab'
  88     >>> caesar_encipher('Héllo World!', 2)
  89     'Jgnnq Yqtnf!'
  90     """
  91     enciphered = [caesar_encipher_letter(l, shift) for l in message]
  92     return ''.join(enciphered)
  93
  94 def caesar_decipher(message, shift):
  95     """Decipher a message with the Caesar cipher of given shift
  96
  97     >>> caesar_decipher('bcd', 1)
  98     'abc'
  99     >>> caesar_decipher('cde', 2)
 100     'abc'
 101     >>> caesar_decipher('cd ez ab', 2)
 102     'ab cx yz'
 103     >>> caesar_decipher('Jgnnq Yqtnf!', 2)
 104     'Hello World!'
 105     """
 106     return caesar_encipher(message, -shift)
 107
 108 def affine_encipher_letter(accented_letter, multiplier=1, adder=0,
 109                            one_based=True):
 110     """Encipher a letter, given a multiplier and adder
 111     >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
 112             for l in string.ascii_uppercase])
 113     'HKNQTWZCFILORUXADGJMPSVYBE'
 114     >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
 115             for l in string.ascii_uppercase])
 116     'FILORUXADGJMPSVYBEHKNQTWZC'
 117     """
 118     letter = unaccent(accented_letter)
 119     if letter in string.ascii_letters:
 120         if letter in string.ascii_uppercase:
 121             alphabet_start = ord('A')
 122         else:
 123             alphabet_start = ord('a')
 124         letter_number = ord(letter) - alphabet_start
 125         if one_based: letter_number += 1
 126         cipher_number = (letter_number * multiplier + adder) % 26
 127         if one_based: cipher_number -= 1
 128         return chr(cipher_number % 26 + alphabet_start)
 129     else:
 130         return letter
 131
 132 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
 133     """Encipher a letter, given a multiplier and adder
 134
 135     >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
 136             for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
 137     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 138     >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
 139             for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
 140     'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 141     """
 142     if letter in string.ascii_letters:
 143         if letter in string.ascii_uppercase:
 144             alphabet_start = ord('A')
 145         else:
 146             alphabet_start = ord('a')
 147         cipher_number = ord(letter) - alphabet_start
 148         if one_based: cipher_number += 1
 149         plaintext_number = (
 150             modular_division_table[multiplier]
 151                                   [(cipher_number - adder) % 26]
 152                             )
 153         if one_based: plaintext_number -= 1
 154         return chr(plaintext_number % 26 + alphabet_start)
 155     else:
 156         return letter
 157
 158 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
 159     """Encipher a message
 160
 161     >>> affine_encipher('hours passed during which jerico tried every ' \
 162            'trick he could think of', 15, 22, True)
 163     'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
 164     """
 165     enciphered = [affine_encipher_letter(l, multiplier, adder, one_based)
 166                   for l in message]
 167     return ''.join(enciphered)
 168
 169 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
 170     """Decipher a message
 171
 172     >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
 173            'jfaoe ls omytd jlaxe mh', 15, 22, True)
 174     'hours passed during which jerico tried every trick he could think of'
 175     """
 176     enciphered = [affine_decipher_letter(l, multiplier, adder, one_based)
 177                   for l in message]
 178     return ''.join(enciphered)
 179
 180
 181 class KeywordWrapAlphabet(Enum):
 182     """Ways of wrapping the alphabet for keyword-based substitution ciphers."""
 183     from_a = 1
 184     from_last = 2
 185     from_largest = 3
 186
 187
 188 def keyword_cipher_alphabet_of(keyword,
 189         wrap_alphabet=KeywordWrapAlphabet.from_a):
 190     """Find the cipher alphabet given a keyword.
 191     wrap_alphabet controls how the rest of the alphabet is added
 192     after the keyword.
 193
 194     >>> keyword_cipher_alphabet_of('bayes')
 195     'bayescdfghijklmnopqrtuvwxz'
 196     >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_a)
 197     'bayescdfghijklmnopqrtuvwxz'
 198     >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_last)
 199     'bayestuvwxzcdfghijklmnopqr'
 200     >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_largest)
 201     'bayeszcdfghijklmnopqrtuvwx'
 202     """
 203     if wrap_alphabet == KeywordWrapAlphabet.from_a:
 204         cipher_alphabet = ''.join(deduplicate(sanitise(keyword) +
 205                                               string.ascii_lowercase))
 206     else:
 207         if wrap_alphabet == KeywordWrapAlphabet.from_last:
 208             last_keyword_letter = deduplicate(sanitise(keyword))[-1]
 209         else:
 210             last_keyword_letter = sorted(sanitise(keyword))[-1]
 211         last_keyword_position = string.ascii_lowercase.find(
 212             last_keyword_letter) + 1
 213         cipher_alphabet = ''.join(
 214             deduplicate(sanitise(keyword) +
 215                         string.ascii_lowercase[last_keyword_position:] +
 216                         string.ascii_lowercase))
 217     return cipher_alphabet
 218
 219
 220 def keyword_encipher(message, keyword,
 221                      wrap_alphabet=KeywordWrapAlphabet.from_a):
 222     """Enciphers a message with a keyword substitution cipher.
 223     wrap_alphabet controls how the rest of the alphabet is added
 224     after the keyword.
 225     0 : from 'a'
 226     1 : from the last letter in the sanitised keyword
 227     2 : from the largest letter in the sanitised keyword
 228
 229     >>> keyword_encipher('test message', 'bayes')
 230     'rsqr ksqqbds'
 231     >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_a)
 232     'rsqr ksqqbds'
 233     >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_last)
 234     'lskl dskkbus'
 235     >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_largest)
 236     'qspq jsppbcs'
 237     """
 238     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 239     cipher_translation = ''.maketrans(string.ascii_lowercase, cipher_alphabet)
 240     return unaccent(message).lower().translate(cipher_translation)
 241
 242 def keyword_decipher(message, keyword,
 243                      wrap_alphabet=KeywordWrapAlphabet.from_a):
 244     """Deciphers a message with a keyword substitution cipher.
 245     wrap_alphabet controls how the rest of the alphabet is added
 246     after the keyword.
 247     0 : from 'a'
 248     1 : from the last letter in the sanitised keyword
 249     2 : from the largest letter in the sanitised keyword
 250
 251     >>> keyword_decipher('rsqr ksqqbds', 'bayes')
 252     'test message'
 253     >>> keyword_decipher('rsqr ksqqbds', 'bayes', KeywordWrapAlphabet.from_a)
 254     'test message'
 255     >>> keyword_decipher('lskl dskkbus', 'bayes', KeywordWrapAlphabet.from_last)
 256     'test message'
 257     >>> keyword_decipher('qspq jsppbcs', 'bayes', KeywordWrapAlphabet.from_largest)
 258     'test message'
 259     """
 260     cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
 261     cipher_translation = ''.maketrans(cipher_alphabet, string.ascii_lowercase)
 262     return message.lower().translate(cipher_translation)
 263
 264 if __name__ == "__main__":
 265     import doctest
 266     doctest.testmod()