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