a511e2492667dfa4abad4ada7f15d67a4aa30d75
[cipher-training.git] / 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()