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