5 from itertools
import zip_longest
, cycle
, chain
6 from language_models
import *
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)
15 modular_division_table
= [[0]*26 for _
in range(26)]
19 modular_division_table
[b
][c
] = a
23 """Returns all n-grams of a text
25 >>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE
26 ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn',
28 >>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE
29 ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow',
30 'rown', 'ownf', 'wnfo', 'nfox']
32 return [text
[i
:i
+n
] for i
in range(len(text
)-n
+1)]
34 def every_nth(text
, n
, fillvalue
=''):
35 """Returns n strings, each of which consists of every nth character,
36 starting with the 0th, 1st, 2nd, ... (n-1)th character
38 >>> every_nth(string.ascii_lowercase, 5)
39 ['afkpuz', 'bglqv', 'chmrw', 'dinsx', 'ejoty']
40 >>> every_nth(string.ascii_lowercase, 1)
41 ['abcdefghijklmnopqrstuvwxyz']
42 >>> every_nth(string.ascii_lowercase, 26) # doctest: +NORMALIZE_WHITESPACE
43 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
44 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
45 >>> every_nth(string.ascii_lowercase, 5, fillvalue='!')
46 ['afkpuz', 'bglqv!', 'chmrw!', 'dinsx!', 'ejoty!']
48 split_text
= [text
[i
:i
+n
] for i
in range(0, len(text
), n
)]
49 return [''.join(l
) for l
in zip_longest(*split_text
, fillvalue
=fillvalue
)]
51 def combine_every_nth(split_text
):
52 """Reforms a text split into every_nth strings
54 >>> combine_every_nth(every_nth(string.ascii_lowercase, 5))
55 'abcdefghijklmnopqrstuvwxyz'
56 >>> combine_every_nth(every_nth(string.ascii_lowercase, 1))
57 'abcdefghijklmnopqrstuvwxyz'
58 >>> combine_every_nth(every_nth(string.ascii_lowercase, 26))
59 'abcdefghijklmnopqrstuvwxyz'
61 return ''.join([''.join(l
)
62 for l
in zip_longest(*split_text
, fillvalue
='')])
64 def chunks(text
, n
, fillvalue
=None):
65 """Split a text into chunks of n characters
67 >>> chunks('abcdefghi', 3)
69 >>> chunks('abcdefghi', 4)
71 >>> chunks('abcdefghi', 4, fillvalue='!')
72 ['abcd', 'efgh', 'i!!!']
75 padding
= fillvalue
[0] * (n
- len(text
) % n
)
78 return [(text
+padding
)[i
:i
+n
] for i
in range(0, len(text
), n
)]
80 def transpose(items
, transposition
):
81 """Moves items around according to the given transposition
83 >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
85 >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
87 >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
88 [13, 12, 14, 11, 15, 10]
90 transposed
= [''] * len(transposition
)
91 for p
, t
in enumerate(transposition
):
92 transposed
[p
] = items
[t
]
95 def untranspose(items
, transposition
):
98 >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
100 >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
102 >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
103 [10, 11, 12, 13, 14, 15]
105 transposed
= [''] * len(transposition
)
106 for p
, t
in enumerate(transposition
):
107 transposed
[t
] = items
[p
]
110 def deduplicate(text
):
111 return list(collections
.OrderedDict
.fromkeys(text
))
114 def caesar_encipher_letter(letter
, shift
):
115 """Encipher a letter, given a shift amount
117 >>> caesar_encipher_letter('a', 1)
119 >>> caesar_encipher_letter('a', 2)
121 >>> caesar_encipher_letter('b', 2)
123 >>> caesar_encipher_letter('x', 2)
125 >>> caesar_encipher_letter('y', 2)
127 >>> caesar_encipher_letter('z', 2)
129 >>> caesar_encipher_letter('z', -1)
131 >>> caesar_encipher_letter('a', -1)
134 if letter
in string
.ascii_letters
:
135 if letter
in string
.ascii_uppercase
:
136 alphabet_start
= ord('A')
138 alphabet_start
= ord('a')
139 return chr(((ord(letter
) - alphabet_start
+ shift
) % 26) +
144 def caesar_decipher_letter(letter
, shift
):
145 """Decipher a letter, given a shift amount
147 >>> caesar_decipher_letter('b', 1)
149 >>> caesar_decipher_letter('b', 2)
152 return caesar_encipher_letter(letter
, -shift
)
154 def caesar_encipher(message
, shift
):
155 """Encipher a message with the Caesar cipher of given shift
157 >>> caesar_encipher('abc', 1)
159 >>> caesar_encipher('abc', 2)
161 >>> caesar_encipher('abcxyz', 2)
163 >>> caesar_encipher('ab cx yz', 2)
166 enciphered
= [caesar_encipher_letter(l
, shift
) for l
in message
]
167 return ''.join(enciphered
)
169 def caesar_decipher(message
, shift
):
170 """Encipher a message with the Caesar cipher of given shift
172 >>> caesar_decipher('bcd', 1)
174 >>> caesar_decipher('cde', 2)
176 >>> caesar_decipher('cd ez ab', 2)
179 return caesar_encipher(message
, -shift
)
181 def affine_encipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
182 """Encipher a letter, given a multiplier and adder
184 >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
185 for l in string.ascii_uppercase])
186 'HKNQTWZCFILORUXADGJMPSVYBE'
187 >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
188 for l in string.ascii_uppercase])
189 'FILORUXADGJMPSVYBEHKNQTWZC'
191 if letter
in string
.ascii_letters
:
192 if letter
in string
.ascii_uppercase
:
193 alphabet_start
= ord('A')
195 alphabet_start
= ord('a')
196 letter_number
= ord(letter
) - alphabet_start
197 if one_based
: letter_number
+= 1
198 cipher_number
= (letter_number
* multiplier
+ adder
) % 26
199 if one_based
: cipher_number
-= 1
200 return chr(cipher_number
% 26 + alphabet_start
)
204 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
205 """Encipher a letter, given a multiplier and adder
207 >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
208 for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
209 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
210 >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
211 for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
212 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
214 if letter
in string
.ascii_letters
:
215 if letter
in string
.ascii_uppercase
:
216 alphabet_start
= ord('A')
218 alphabet_start
= ord('a')
219 cipher_number
= ord(letter
) - alphabet_start
220 if one_based
: cipher_number
+= 1
222 modular_division_table
[multiplier
]
223 [(cipher_number
- adder
) % 26] )
224 if one_based
: plaintext_number
-= 1
225 return chr(plaintext_number
% 26 + alphabet_start
)
229 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
230 """Encipher a message
232 >>> affine_encipher('hours passed during which jerico tried every ' \
233 'trick he could think of', 15, 22, True)
234 'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
236 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
)
238 return ''.join(enciphered
)
240 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
241 """Decipher a message
243 >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
244 'jfaoe ls omytd jlaxe mh', 15, 22, True)
245 'hours passed during which jerico tried every trick he could think of'
247 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
)
249 return ''.join(enciphered
)
252 def keyword_cipher_alphabet_of(keyword
, wrap_alphabet
=0):
253 """Find the cipher alphabet given a keyword.
254 wrap_alphabet controls how the rest of the alphabet is added
257 1 : from the last letter in the sanitised keyword
258 2 : from the largest letter in the sanitised keyword
260 >>> keyword_cipher_alphabet_of('bayes')
261 'bayescdfghijklmnopqrtuvwxz'
262 >>> keyword_cipher_alphabet_of('bayes', 0)
263 'bayescdfghijklmnopqrtuvwxz'
264 >>> keyword_cipher_alphabet_of('bayes', 1)
265 'bayestuvwxzcdfghijklmnopqr'
266 >>> keyword_cipher_alphabet_of('bayes', 2)
267 'bayeszcdfghijklmnopqrtuvwx'
269 if wrap_alphabet
== 0:
270 cipher_alphabet
= ''.join(deduplicate(sanitise(keyword
) +
271 string
.ascii_lowercase
))
273 if wrap_alphabet
== 1:
274 last_keyword_letter
= deduplicate(sanitise(keyword
))[-1]
276 last_keyword_letter
= sorted(sanitise(keyword
))[-1]
277 last_keyword_position
= string
.ascii_lowercase
.find(
278 last_keyword_letter
) + 1
279 cipher_alphabet
= ''.join(
280 deduplicate(sanitise(keyword
) +
281 string
.ascii_lowercase
[last_keyword_position
:] +
282 string
.ascii_lowercase
))
283 return cipher_alphabet
286 def keyword_encipher(message
, keyword
, wrap_alphabet
=0):
287 """Enciphers a message with a keyword substitution cipher.
288 wrap_alphabet controls how the rest of the alphabet is added
291 1 : from the last letter in the sanitised keyword
292 2 : from the largest letter in the sanitised keyword
294 >>> keyword_encipher('test message', 'bayes')
296 >>> keyword_encipher('test message', 'bayes', 0)
298 >>> keyword_encipher('test message', 'bayes', 1)
300 >>> keyword_encipher('test message', 'bayes', 2)
303 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
304 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, cipher_alphabet
)
305 return message
.lower().translate(cipher_translation
)
307 def keyword_decipher(message
, keyword
, wrap_alphabet
=0):
308 """Deciphers a message with a keyword substitution cipher.
309 wrap_alphabet controls how the rest of the alphabet is added
312 1 : from the last letter in the sanitised keyword
313 2 : from the largest letter in the sanitised keyword
315 >>> keyword_decipher('rsqr ksqqbds', 'bayes')
317 >>> keyword_decipher('rsqr ksqqbds', 'bayes', 0)
319 >>> keyword_decipher('lskl dskkbus', 'bayes', 1)
321 >>> keyword_decipher('qspq jsppbcs', 'bayes', 2)
324 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
325 cipher_translation
= ''.maketrans(cipher_alphabet
, string
.ascii_lowercase
)
326 return message
.lower().translate(cipher_translation
)
329 def vigenere_encipher(message
, keyword
):
332 >>> vigenere_encipher('hello', 'abc')
335 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
336 pairs
= zip(message
, cycle(shifts
))
337 return ''.join([caesar_encipher_letter(l
, k
) for l
, k
in pairs
])
339 def vigenere_decipher(message
, keyword
):
342 >>> vigenere_decipher('hfnlp', 'abc')
345 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
346 pairs
= zip(message
, cycle(shifts
))
347 return ''.join([caesar_decipher_letter(l
, k
) for l
, k
in pairs
])
349 beaufort_encipher
=vigenere_decipher
350 beaufort_decipher
=vigenere_encipher
353 def transpositions_of(keyword
):
354 """Finds the transpostions given by a keyword. For instance, the keyword
355 'clever' rearranges to 'celrv', so the first column (0) stays first, the
356 second column (1) moves to third, the third column (2) moves to second,
359 If passed a tuple, assume it's already a transposition and just return it.
361 >>> transpositions_of('clever')
363 >>> transpositions_of('fred')
365 >>> transpositions_of((3, 2, 0, 1))
368 if isinstance(keyword
, tuple):
371 key
= deduplicate(keyword
)
372 transpositions
= tuple(key
.index(l
) for l
in sorted(key
))
373 return transpositions
375 def pad(message_len
, group_len
, fillvalue
):
376 padding_length
= group_len
- message_len
% group_len
377 if padding_length
== group_len
: padding_length
= 0
379 for i
in range(padding_length
):
380 if callable(fillvalue
):
381 padding
+= fillvalue()
386 def column_transposition_encipher(message
, keyword
, fillvalue
=' ',
387 fillcolumnwise
=False,
388 emptycolumnwise
=False):
389 """Enciphers using the column transposition cipher.
390 Message is padded to allow all rows to be the same length.
392 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
394 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
396 >>> column_transposition_encipher('hellothere', 'abcdef')
398 >>> column_transposition_encipher('hellothere', 'abcde')
400 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
402 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
404 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
406 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
408 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
410 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
412 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
414 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
416 >>> column_transposition_encipher('hellothere', 'cleverly')
418 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
420 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
423 transpositions
= transpositions_of(keyword
)
424 message
+= pad(len(message
), len(transpositions
), fillvalue
)
426 rows
= every_nth(message
, len(message
) // len(transpositions
))
428 rows
= chunks(message
, len(transpositions
))
429 transposed
= [transpose(r
, transpositions
) for r
in rows
]
431 return combine_every_nth(transposed
)
433 return ''.join(chain(*transposed
))
435 def column_transposition_decipher(message
, keyword
, fillvalue
=' ',
436 fillcolumnwise
=False,
437 emptycolumnwise
=False):
438 """Deciphers using the column transposition cipher.
439 Message is padded to allow all rows to be the same length.
441 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
443 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
445 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
447 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
449 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
451 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
453 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
455 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
458 transpositions
= transpositions_of(keyword
)
459 message
+= pad(len(message
), len(transpositions
), '*')
461 rows
= every_nth(message
, len(message
) // len(transpositions
))
463 rows
= chunks(message
, len(transpositions
))
464 untransposed
= [untranspose(r
, transpositions
) for r
in rows
]
466 return combine_every_nth(untransposed
)
468 return ''.join(chain(*untransposed
))
470 def scytale_encipher(message
, rows
, fillvalue
=' '):
471 """Enciphers using the scytale transposition cipher.
472 Message is padded with spaces to allow all rows to be the same length.
474 >>> scytale_encipher('thequickbrownfox', 3)
476 >>> scytale_encipher('thequickbrownfox', 4)
478 >>> scytale_encipher('thequickbrownfox', 5)
480 >>> scytale_encipher('thequickbrownfox', 6)
482 >>> scytale_encipher('thequickbrownfox', 7)
485 transpositions
= [i
for i
in range(math
.ceil(len(message
) / rows
))]
486 return column_transposition_encipher(message
, transpositions
,
487 fillcolumnwise
=False, emptycolumnwise
=True)
489 def scytale_decipher(message
, rows
):
490 """Deciphers using the scytale transposition cipher.
491 Assumes the message is padded so that all rows are the same length.
493 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
495 >>> scytale_decipher('tubnhirfecooqkwx', 4)
497 >>> scytale_decipher('tubnhirfecooqkwx', 5)
499 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
501 >>> scytale_decipher('tqcrnxhukof eibwo ', 7)
504 transpositions
= [i
for i
in range(math
.ceil(len(message
) / rows
))]
505 return column_transposition_decipher(message
, transpositions
,
506 fillcolumnwise
=False, emptycolumnwise
=True)
509 if __name__
== "__main__":