4 from itertools
import zip_longest
, cycle
, chain
5 from language_models
import *
8 modular_division_table
= [[0]*26 for _
in range(26)]
12 modular_division_table
[b
][c
] = a
15 def every_nth(text
, n
, fillvalue
=''):
16 """Returns n strings, each of which consists of every nth character,
17 starting with the 0th, 1st, 2nd, ... (n-1)th character
19 >>> every_nth(string.ascii_lowercase, 5)
20 ['afkpuz', 'bglqv', 'chmrw', 'dinsx', 'ejoty']
21 >>> every_nth(string.ascii_lowercase, 1)
22 ['abcdefghijklmnopqrstuvwxyz']
23 >>> every_nth(string.ascii_lowercase, 26) # doctest: +NORMALIZE_WHITESPACE
24 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
25 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
26 >>> every_nth(string.ascii_lowercase, 5, fillvalue='!')
27 ['afkpuz', 'bglqv!', 'chmrw!', 'dinsx!', 'ejoty!']
29 split_text
= [text
[i
:i
+n
] for i
in range(0, len(text
), n
)]
30 return [''.join(l
) for l
in zip_longest(*split_text
, fillvalue
=fillvalue
)]
32 def combine_every_nth(split_text
):
33 """Reforms a text split into every_nth strings
35 >>> combine_every_nth(every_nth(string.ascii_lowercase, 5))
36 'abcdefghijklmnopqrstuvwxyz'
37 >>> combine_every_nth(every_nth(string.ascii_lowercase, 1))
38 'abcdefghijklmnopqrstuvwxyz'
39 >>> combine_every_nth(every_nth(string.ascii_lowercase, 26))
40 'abcdefghijklmnopqrstuvwxyz'
42 return ''.join([''.join(l
)
43 for l
in zip_longest(*split_text
, fillvalue
='')])
45 def chunks(text
, n
, fillvalue
=None):
46 """Split a text into chunks of n characters
48 >>> chunks('abcdefghi', 3)
50 >>> chunks('abcdefghi', 4)
52 >>> chunks('abcdefghi', 4, fillvalue='!')
53 ['abcd', 'efgh', 'i!!!']
56 padding
= fillvalue
[0] * (n
- len(text
) % n
)
59 return [(text
+padding
)[i
:i
+n
] for i
in range(0, len(text
), n
)]
61 def transpose(items
, transposition
):
62 """Moves items around according to the given transposition
64 >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
66 >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
68 >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
69 [13, 12, 14, 11, 15, 10]
71 transposed
= [''] * len(transposition
)
72 for p
, t
in enumerate(transposition
):
73 transposed
[p
] = items
[t
]
76 def untranspose(items
, transposition
):
79 >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
81 >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
83 >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
84 [10, 11, 12, 13, 14, 15]
86 transposed
= [''] * len(transposition
)
87 for p
, t
in enumerate(transposition
):
88 transposed
[t
] = items
[p
]
91 def deduplicate(text
):
92 return list(collections
.OrderedDict
.fromkeys(text
))
95 def caesar_encipher_letter(accented_letter
, shift
):
96 """Encipher a letter, given a shift amount
98 >>> caesar_encipher_letter('a', 1)
100 >>> caesar_encipher_letter('a', 2)
102 >>> caesar_encipher_letter('b', 2)
104 >>> caesar_encipher_letter('x', 2)
106 >>> caesar_encipher_letter('y', 2)
108 >>> caesar_encipher_letter('z', 2)
110 >>> caesar_encipher_letter('z', -1)
112 >>> caesar_encipher_letter('a', -1)
114 >>> caesar_encipher_letter('A', 1)
116 >>> caesar_encipher_letter('é', 1)
119 letter
= unaccent(accented_letter
)
120 if letter
in string
.ascii_letters
:
121 if letter
in string
.ascii_uppercase
:
122 alphabet_start
= ord('A')
124 alphabet_start
= ord('a')
125 return chr(((ord(letter
) - alphabet_start
+ shift
) % 26) +
130 def caesar_decipher_letter(letter
, shift
):
131 """Decipher a letter, given a shift amount
133 >>> caesar_decipher_letter('b', 1)
135 >>> caesar_decipher_letter('b', 2)
138 return caesar_encipher_letter(letter
, -shift
)
140 def caesar_encipher(message
, shift
):
141 """Encipher a message with the Caesar cipher of given shift
143 >>> caesar_encipher('abc', 1)
145 >>> caesar_encipher('abc', 2)
147 >>> caesar_encipher('abcxyz', 2)
149 >>> caesar_encipher('ab cx yz', 2)
151 >>> caesar_encipher('Héllo World!', 2)
154 enciphered
= [caesar_encipher_letter(l
, shift
) for l
in message
]
155 return ''.join(enciphered
)
157 def caesar_decipher(message
, shift
):
158 """Decipher a message with the Caesar cipher of given shift
160 >>> caesar_decipher('bcd', 1)
162 >>> caesar_decipher('cde', 2)
164 >>> caesar_decipher('cd ez ab', 2)
166 >>> caesar_decipher('Jgnnq Yqtnf!', 2)
169 return caesar_encipher(message
, -shift
)
171 def affine_encipher_letter(accented_letter
, multiplier
=1, adder
=0, one_based
=True):
172 """Encipher a letter, given a multiplier and adder
174 >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
175 for l in string.ascii_uppercase])
176 'HKNQTWZCFILORUXADGJMPSVYBE'
177 >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
178 for l in string.ascii_uppercase])
179 'FILORUXADGJMPSVYBEHKNQTWZC'
181 letter
= unaccent(accented_letter
)
182 if letter
in string
.ascii_letters
:
183 if letter
in string
.ascii_uppercase
:
184 alphabet_start
= ord('A')
186 alphabet_start
= ord('a')
187 letter_number
= ord(letter
) - alphabet_start
188 if one_based
: letter_number
+= 1
189 cipher_number
= (letter_number
* multiplier
+ adder
) % 26
190 if one_based
: cipher_number
-= 1
191 return chr(cipher_number
% 26 + alphabet_start
)
195 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
196 """Encipher a letter, given a multiplier and adder
198 >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
199 for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
200 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
201 >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
202 for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
203 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
205 if letter
in string
.ascii_letters
:
206 if letter
in string
.ascii_uppercase
:
207 alphabet_start
= ord('A')
209 alphabet_start
= ord('a')
210 cipher_number
= ord(letter
) - alphabet_start
211 if one_based
: cipher_number
+= 1
213 modular_division_table
[multiplier
]
214 [(cipher_number
- adder
) % 26] )
215 if one_based
: plaintext_number
-= 1
216 return chr(plaintext_number
% 26 + alphabet_start
)
220 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
221 """Encipher a message
223 >>> affine_encipher('hours passed during which jerico tried every ' \
224 'trick he could think of', 15, 22, True)
225 'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
227 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
)
229 return ''.join(enciphered
)
231 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
232 """Decipher a message
234 >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
235 'jfaoe ls omytd jlaxe mh', 15, 22, True)
236 'hours passed during which jerico tried every trick he could think of'
238 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
)
240 return ''.join(enciphered
)
243 def keyword_cipher_alphabet_of(keyword
, wrap_alphabet
=0):
244 """Find the cipher alphabet given a keyword.
245 wrap_alphabet controls how the rest of the alphabet is added
248 1 : from the last letter in the sanitised keyword
249 2 : from the largest letter in the sanitised keyword
251 >>> keyword_cipher_alphabet_of('bayes')
252 'bayescdfghijklmnopqrtuvwxz'
253 >>> keyword_cipher_alphabet_of('bayes', 0)
254 'bayescdfghijklmnopqrtuvwxz'
255 >>> keyword_cipher_alphabet_of('bayes', 1)
256 'bayestuvwxzcdfghijklmnopqr'
257 >>> keyword_cipher_alphabet_of('bayes', 2)
258 'bayeszcdfghijklmnopqrtuvwx'
260 if wrap_alphabet
== 0:
261 cipher_alphabet
= ''.join(deduplicate(sanitise(keyword
) +
262 string
.ascii_lowercase
))
264 if wrap_alphabet
== 1:
265 last_keyword_letter
= deduplicate(sanitise(keyword
))[-1]
267 last_keyword_letter
= sorted(sanitise(keyword
))[-1]
268 last_keyword_position
= string
.ascii_lowercase
.find(
269 last_keyword_letter
) + 1
270 cipher_alphabet
= ''.join(
271 deduplicate(sanitise(keyword
) +
272 string
.ascii_lowercase
[last_keyword_position
:] +
273 string
.ascii_lowercase
))
274 return cipher_alphabet
277 def keyword_encipher(message
, keyword
, wrap_alphabet
=0):
278 """Enciphers a message with a keyword substitution cipher.
279 wrap_alphabet controls how the rest of the alphabet is added
282 1 : from the last letter in the sanitised keyword
283 2 : from the largest letter in the sanitised keyword
285 >>> keyword_encipher('test message', 'bayes')
287 >>> keyword_encipher('test message', 'bayes', 0)
289 >>> keyword_encipher('test message', 'bayes', 1)
291 >>> keyword_encipher('test message', 'bayes', 2)
294 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
295 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, cipher_alphabet
)
296 return unaccent(message
).lower().translate(cipher_translation
)
298 def keyword_decipher(message
, keyword
, wrap_alphabet
=0):
299 """Deciphers a message with a keyword substitution cipher.
300 wrap_alphabet controls how the rest of the alphabet is added
303 1 : from the last letter in the sanitised keyword
304 2 : from the largest letter in the sanitised keyword
306 >>> keyword_decipher('rsqr ksqqbds', 'bayes')
308 >>> keyword_decipher('rsqr ksqqbds', 'bayes', 0)
310 >>> keyword_decipher('lskl dskkbus', 'bayes', 1)
312 >>> keyword_decipher('qspq jsppbcs', 'bayes', 2)
315 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
316 cipher_translation
= ''.maketrans(cipher_alphabet
, string
.ascii_lowercase
)
317 return message
.lower().translate(cipher_translation
)
320 def vigenere_encipher(message
, keyword
):
323 >>> vigenere_encipher('hello', 'abc')
326 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
327 pairs
= zip(message
, cycle(shifts
))
328 return ''.join([caesar_encipher_letter(l
, k
) for l
, k
in pairs
])
330 def vigenere_decipher(message
, keyword
):
333 >>> vigenere_decipher('hfnlp', 'abc')
336 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
337 pairs
= zip(message
, cycle(shifts
))
338 return ''.join([caesar_decipher_letter(l
, k
) for l
, k
in pairs
])
340 beaufort_encipher
=vigenere_decipher
341 beaufort_decipher
=vigenere_encipher
344 def transpositions_of(keyword
):
345 """Finds the transpostions given by a keyword. For instance, the keyword
346 'clever' rearranges to 'celrv', so the first column (0) stays first, the
347 second column (1) moves to third, the third column (2) moves to second,
350 If passed a tuple, assume it's already a transposition and just return it.
352 >>> transpositions_of('clever')
354 >>> transpositions_of('fred')
356 >>> transpositions_of((3, 2, 0, 1))
359 if isinstance(keyword
, tuple):
362 key
= deduplicate(keyword
)
363 transpositions
= tuple(key
.index(l
) for l
in sorted(key
))
364 return transpositions
366 def pad(message_len
, group_len
, fillvalue
):
367 padding_length
= group_len
- message_len
% group_len
368 if padding_length
== group_len
: padding_length
= 0
370 for i
in range(padding_length
):
371 if callable(fillvalue
):
372 padding
+= fillvalue()
377 def column_transposition_encipher(message
, keyword
, fillvalue
=' ',
378 fillcolumnwise
=False,
379 emptycolumnwise
=False):
380 """Enciphers using the column transposition cipher.
381 Message is padded to allow all rows to be the same length.
383 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
385 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
387 >>> column_transposition_encipher('hellothere', 'abcdef')
389 >>> column_transposition_encipher('hellothere', 'abcde')
391 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
393 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
395 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
397 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
399 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
401 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
403 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
405 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
407 >>> column_transposition_encipher('hellothere', 'cleverly')
409 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
411 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
414 transpositions
= transpositions_of(keyword
)
415 message
+= pad(len(message
), len(transpositions
), fillvalue
)
417 rows
= every_nth(message
, len(message
) // len(transpositions
))
419 rows
= chunks(message
, len(transpositions
))
420 transposed
= [transpose(r
, transpositions
) for r
in rows
]
422 return combine_every_nth(transposed
)
424 return ''.join(chain(*transposed
))
426 def column_transposition_decipher(message
, keyword
, fillvalue
=' ',
427 fillcolumnwise
=False,
428 emptycolumnwise
=False):
429 """Deciphers using the column transposition cipher.
430 Message is padded to allow all rows to be the same length.
432 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
434 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
436 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
438 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
440 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
442 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
444 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
446 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
449 transpositions
= transpositions_of(keyword
)
450 message
+= pad(len(message
), len(transpositions
), '*')
452 rows
= every_nth(message
, len(message
) // len(transpositions
))
454 rows
= chunks(message
, len(transpositions
))
455 untransposed
= [untranspose(r
, transpositions
) for r
in rows
]
457 return combine_every_nth(untransposed
)
459 return ''.join(chain(*untransposed
))
461 def scytale_encipher(message
, rows
, fillvalue
=' '):
462 """Enciphers using the scytale transposition cipher.
463 Message is padded with spaces to allow all rows to be the same length.
465 >>> scytale_encipher('thequickbrownfox', 3)
467 >>> scytale_encipher('thequickbrownfox', 4)
469 >>> scytale_encipher('thequickbrownfox', 5)
471 >>> scytale_encipher('thequickbrownfox', 6)
473 >>> scytale_encipher('thequickbrownfox', 7)
476 transpositions
= [i
for i
in range(math
.ceil(len(message
) / rows
))]
477 return column_transposition_encipher(message
, transpositions
,
478 fillcolumnwise
=False, emptycolumnwise
=True)
480 def scytale_decipher(message
, rows
):
481 """Deciphers using the scytale transposition cipher.
482 Assumes the message is padded so that all rows are the same length.
484 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
486 >>> scytale_decipher('tubnhirfecooqkwx', 4)
488 >>> scytale_decipher('tubnhirfecooqkwx', 5)
490 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
492 >>> scytale_decipher('tqcrnxhukof eibwo ', 7)
495 transpositions
= [i
for i
in range(math
.ceil(len(message
) / rows
))]
496 return column_transposition_decipher(message
, transpositions
,
497 fillcolumnwise
=False, emptycolumnwise
=True)
500 if __name__
== "__main__":