1 """A set of ciphers with implementations for both enciphering and deciphering
2 them. See cipherbreak for automatic breaking of these ciphers
8 from itertools
import zip_longest
, cycle
, chain
9 from language_models
import unaccent
, sanitise
12 modular_division_table
= [[0]*26 for _
in range(26)]
16 modular_division_table
[b
][c
] = a
19 def every_nth(text
, n
, fillvalue
=''):
20 """Returns n strings, each of which consists of every nth character,
21 starting with the 0th, 1st, 2nd, ... (n-1)th character
23 >>> every_nth(string.ascii_lowercase, 5)
24 ['afkpuz', 'bglqv', 'chmrw', 'dinsx', 'ejoty']
25 >>> every_nth(string.ascii_lowercase, 1)
26 ['abcdefghijklmnopqrstuvwxyz']
27 >>> every_nth(string.ascii_lowercase, 26) # doctest: +NORMALIZE_WHITESPACE
28 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
29 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
30 >>> every_nth(string.ascii_lowercase, 5, fillvalue='!')
31 ['afkpuz', 'bglqv!', 'chmrw!', 'dinsx!', 'ejoty!']
33 split_text
= chunks(text
, n
, fillvalue
)
34 return [''.join(l
) for l
in zip_longest(*split_text
, fillvalue
=fillvalue
)]
36 def combine_every_nth(split_text
):
37 """Reforms a text split into every_nth strings
39 >>> combine_every_nth(every_nth(string.ascii_lowercase, 5))
40 'abcdefghijklmnopqrstuvwxyz'
41 >>> combine_every_nth(every_nth(string.ascii_lowercase, 1))
42 'abcdefghijklmnopqrstuvwxyz'
43 >>> combine_every_nth(every_nth(string.ascii_lowercase, 26))
44 'abcdefghijklmnopqrstuvwxyz'
46 return ''.join([''.join(l
)
47 for l
in zip_longest(*split_text
, fillvalue
='')])
49 def chunks(text
, n
, fillvalue
=None):
50 """Split a text into chunks of n characters
52 >>> chunks('abcdefghi', 3)
54 >>> chunks('abcdefghi', 4)
56 >>> chunks('abcdefghi', 4, fillvalue='!')
57 ['abcd', 'efgh', 'i!!!']
60 padding
= fillvalue
[0] * (n
- len(text
) % n
)
63 return [(text
+padding
)[i
:i
+n
] for i
in range(0, len(text
), n
)]
65 def transpose(items
, transposition
):
66 """Moves items around according to the given transposition
68 >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
70 >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
72 >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
73 [13, 12, 14, 11, 15, 10]
75 transposed
= [''] * len(transposition
)
76 for p
, t
in enumerate(transposition
):
77 transposed
[p
] = items
[t
]
80 def untranspose(items
, transposition
):
83 >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
85 >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
87 >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
88 [10, 11, 12, 13, 14, 15]
90 transposed
= [''] * len(transposition
)
91 for p
, t
in enumerate(transposition
):
92 transposed
[t
] = items
[p
]
95 def deduplicate(text
):
96 """If a string contains duplicate letters, remove all but the first. Retain
97 the order of the letters.
99 >>> deduplicate('cat')
101 >>> deduplicate('happy')
103 >>> deduplicate('cattca')
106 return list(collections
.OrderedDict
.fromkeys(text
))
109 def caesar_encipher_letter(accented_letter
, shift
):
110 """Encipher a letter, given a shift amount
112 >>> caesar_encipher_letter('a', 1)
114 >>> caesar_encipher_letter('a', 2)
116 >>> caesar_encipher_letter('b', 2)
118 >>> caesar_encipher_letter('x', 2)
120 >>> caesar_encipher_letter('y', 2)
122 >>> caesar_encipher_letter('z', 2)
124 >>> caesar_encipher_letter('z', -1)
126 >>> caesar_encipher_letter('a', -1)
128 >>> caesar_encipher_letter('A', 1)
130 >>> caesar_encipher_letter('é', 1)
133 letter
= unaccent(accented_letter
)
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)
165 >>> caesar_encipher('Héllo World!', 2)
168 enciphered
= [caesar_encipher_letter(l
, shift
) for l
in message
]
169 return ''.join(enciphered
)
171 def caesar_decipher(message
, shift
):
172 """Decipher a message with the Caesar cipher of given shift
174 >>> caesar_decipher('bcd', 1)
176 >>> caesar_decipher('cde', 2)
178 >>> caesar_decipher('cd ez ab', 2)
180 >>> caesar_decipher('Jgnnq Yqtnf!', 2)
183 return caesar_encipher(message
, -shift
)
185 def affine_encipher_letter(accented_letter
, multiplier
=1, adder
=0,
187 """Encipher a letter, given a multiplier and adder
188 >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
189 for l in string.ascii_uppercase])
190 'HKNQTWZCFILORUXADGJMPSVYBE'
191 >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
192 for l in string.ascii_uppercase])
193 'FILORUXADGJMPSVYBEHKNQTWZC'
195 letter
= unaccent(accented_letter
)
196 if letter
in string
.ascii_letters
:
197 if letter
in string
.ascii_uppercase
:
198 alphabet_start
= ord('A')
200 alphabet_start
= ord('a')
201 letter_number
= ord(letter
) - alphabet_start
202 if one_based
: letter_number
+= 1
203 cipher_number
= (letter_number
* multiplier
+ adder
) % 26
204 if one_based
: cipher_number
-= 1
205 return chr(cipher_number
% 26 + alphabet_start
)
209 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
210 """Encipher a letter, given a multiplier and adder
212 >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
213 for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
214 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
215 >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
216 for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
217 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
219 if letter
in string
.ascii_letters
:
220 if letter
in string
.ascii_uppercase
:
221 alphabet_start
= ord('A')
223 alphabet_start
= ord('a')
224 cipher_number
= ord(letter
) - alphabet_start
225 if one_based
: cipher_number
+= 1
227 modular_division_table
[multiplier
]
228 [(cipher_number
- adder
) % 26]
230 if one_based
: plaintext_number
-= 1
231 return chr(plaintext_number
% 26 + alphabet_start
)
235 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
236 """Encipher a message
238 >>> affine_encipher('hours passed during which jerico tried every ' \
239 'trick he could think of', 15, 22, True)
240 'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
242 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
)
244 return ''.join(enciphered
)
246 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
247 """Decipher a message
249 >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
250 'jfaoe ls omytd jlaxe mh', 15, 22, True)
251 'hours passed during which jerico tried every trick he could think of'
253 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
)
255 return ''.join(enciphered
)
258 class KeywordWrapAlphabet(Enum
):
259 """Ways of wrapping the alphabet for keyword-based substitution ciphers."""
265 def keyword_cipher_alphabet_of(keyword
,
266 wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
267 """Find the cipher alphabet given a keyword.
268 wrap_alphabet controls how the rest of the alphabet is added
271 >>> keyword_cipher_alphabet_of('bayes')
272 'bayescdfghijklmnopqrtuvwxz'
273 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_a)
274 'bayescdfghijklmnopqrtuvwxz'
275 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_last)
276 'bayestuvwxzcdfghijklmnopqr'
277 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_largest)
278 'bayeszcdfghijklmnopqrtuvwx'
280 if wrap_alphabet
== KeywordWrapAlphabet
.from_a
:
281 cipher_alphabet
= ''.join(deduplicate(sanitise(keyword
) +
282 string
.ascii_lowercase
))
284 if wrap_alphabet
== KeywordWrapAlphabet
.from_last
:
285 last_keyword_letter
= deduplicate(sanitise(keyword
))[-1]
287 last_keyword_letter
= sorted(sanitise(keyword
))[-1]
288 last_keyword_position
= string
.ascii_lowercase
.find(
289 last_keyword_letter
) + 1
290 cipher_alphabet
= ''.join(
291 deduplicate(sanitise(keyword
) +
292 string
.ascii_lowercase
[last_keyword_position
:] +
293 string
.ascii_lowercase
))
294 return cipher_alphabet
297 def keyword_encipher(message
, keyword
,
298 wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
299 """Enciphers 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_encipher('test message', 'bayes')
308 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_a)
310 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_last)
312 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_largest)
315 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
316 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, cipher_alphabet
)
317 return unaccent(message
).lower().translate(cipher_translation
)
319 def keyword_decipher(message
, keyword
,
320 wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
321 """Deciphers a message with a keyword substitution cipher.
322 wrap_alphabet controls how the rest of the alphabet is added
325 1 : from the last letter in the sanitised keyword
326 2 : from the largest letter in the sanitised keyword
328 >>> keyword_decipher('rsqr ksqqbds', 'bayes')
330 >>> keyword_decipher('rsqr ksqqbds', 'bayes', KeywordWrapAlphabet.from_a)
332 >>> keyword_decipher('lskl dskkbus', 'bayes', KeywordWrapAlphabet.from_last)
334 >>> keyword_decipher('qspq jsppbcs', 'bayes', KeywordWrapAlphabet.from_largest)
337 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
338 cipher_translation
= ''.maketrans(cipher_alphabet
, string
.ascii_lowercase
)
339 return message
.lower().translate(cipher_translation
)
342 def vigenere_encipher(message
, keyword
):
345 >>> vigenere_encipher('hello', 'abc')
348 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
349 pairs
= zip(message
, cycle(shifts
))
350 return ''.join([caesar_encipher_letter(l
, k
) for l
, k
in pairs
])
352 def vigenere_decipher(message
, keyword
):
355 >>> vigenere_decipher('hfnlp', 'abc')
358 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
359 pairs
= zip(message
, cycle(shifts
))
360 return ''.join([caesar_decipher_letter(l
, k
) for l
, k
in pairs
])
362 beaufort_encipher
= vigenere_decipher
363 beaufort_decipher
= vigenere_encipher
366 def transpositions_of(keyword
):
367 """Finds the transpostions given by a keyword. For instance, the keyword
368 'clever' rearranges to 'celrv', so the first column (0) stays first, the
369 second column (1) moves to third, the third column (2) moves to second,
372 If passed a tuple, assume it's already a transposition and just return it.
374 >>> transpositions_of('clever')
376 >>> transpositions_of('fred')
378 >>> transpositions_of((3, 2, 0, 1))
381 if isinstance(keyword
, tuple):
384 key
= deduplicate(keyword
)
385 transpositions
= tuple(key
.index(l
) for l
in sorted(key
))
386 return transpositions
388 def pad(message_len
, group_len
, fillvalue
):
389 """Returns the padding required to extend a message of message_len to an
390 even multiple of group_len, by adding repreated copies of fillvalue.
391 fillvalue can either be a character or a function that returns a character.
399 >>> pad(10, 4, lambda: '*')
402 padding_length
= group_len
- message_len
% group_len
403 if padding_length
== group_len
: padding_length
= 0
405 for _
in range(padding_length
):
406 if callable(fillvalue
):
407 padding
+= fillvalue()
412 def column_transposition_encipher(message
, keyword
, fillvalue
=' ',
413 fillcolumnwise
=False,
414 emptycolumnwise
=False):
415 """Enciphers using the column transposition cipher.
416 Message is padded to allow all rows to be the same length.
418 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
420 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
422 >>> column_transposition_encipher('hellothere', 'abcdef')
424 >>> column_transposition_encipher('hellothere', 'abcde')
426 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
428 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
430 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
432 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
434 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
436 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
438 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
440 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
442 >>> column_transposition_encipher('hellothere', 'cleverly')
444 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
446 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
449 transpositions
= transpositions_of(keyword
)
450 message
+= pad(len(message
), len(transpositions
), fillvalue
)
452 rows
= every_nth(message
, len(message
) // len(transpositions
))
454 rows
= chunks(message
, len(transpositions
))
455 transposed
= [transpose(r
, transpositions
) for r
in rows
]
457 return combine_every_nth(transposed
)
459 return ''.join(chain(*transposed
))
461 def column_transposition_decipher(message
, keyword
, fillvalue
=' ',
462 fillcolumnwise
=False,
463 emptycolumnwise
=False):
464 """Deciphers using the column transposition cipher.
465 Message is padded to allow all rows to be the same length.
467 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
469 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
471 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
473 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
475 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
477 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
479 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
481 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
484 transpositions
= transpositions_of(keyword
)
485 message
+= pad(len(message
), len(transpositions
), '*')
487 rows
= every_nth(message
, len(message
) // len(transpositions
))
489 rows
= chunks(message
, len(transpositions
))
490 untransposed
= [untranspose(r
, transpositions
) for r
in rows
]
492 return combine_every_nth(untransposed
)
494 return ''.join(chain(*untransposed
))
496 def scytale_encipher(message
, rows
, fillvalue
=' '):
497 """Enciphers using the scytale transposition cipher.
498 Message is padded with spaces to allow all rows to be the same length.
500 >>> scytale_encipher('thequickbrownfox', 3)
502 >>> scytale_encipher('thequickbrownfox', 4)
504 >>> scytale_encipher('thequickbrownfox', 5)
505 'tubn hirf ecoo qkwx '
506 >>> scytale_encipher('thequickbrownfox', 6)
508 >>> scytale_encipher('thequickbrownfox', 7)
509 'tqcrnx hukof eibwo '
511 transpositions
= [i
for i
in range(rows
)]
512 return column_transposition_encipher(message
, transpositions
,
513 fillvalue
=fillvalue
, fillcolumnwise
=True, emptycolumnwise
=False)
515 def scytale_decipher(message
, rows
):
516 """Deciphers using the scytale transposition cipher.
517 Assumes the message is padded so that all rows are the same length.
519 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
521 >>> scytale_decipher('tubnhirfecooqkwx', 4)
523 >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
525 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
527 >>> scytale_decipher('tqcrnx hukof eibwo ', 7)
530 transpositions
= [i
for i
in range(rows
)]
531 return column_transposition_decipher(message
, transpositions
,
532 fillcolumnwise
=True, emptycolumnwise
=False)
535 if __name__
== "__main__":