83700a538cec2cd55f01b390967565e21e7afbd3
5 from itertools
import zip_longest
, cycle
, chain
, count
7 from numpy
import matrix
8 from numpy
import linalg
9 from language_models
import *
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 return list(collections
.OrderedDict
.fromkeys(text
))
99 def caesar_encipher_letter(accented_letter
, shift
):
100 """Encipher a letter, given a shift amount
102 >>> caesar_encipher_letter('a', 1)
104 >>> caesar_encipher_letter('a', 2)
106 >>> caesar_encipher_letter('b', 2)
108 >>> caesar_encipher_letter('x', 2)
110 >>> caesar_encipher_letter('y', 2)
112 >>> caesar_encipher_letter('z', 2)
114 >>> caesar_encipher_letter('z', -1)
116 >>> caesar_encipher_letter('a', -1)
118 >>> caesar_encipher_letter('A', 1)
120 >>> caesar_encipher_letter('é', 1)
123 letter
= unaccent(accented_letter
)
124 if letter
in string
.ascii_letters
:
125 if letter
in string
.ascii_uppercase
:
126 alphabet_start
= ord('A')
128 alphabet_start
= ord('a')
129 return chr(((ord(letter
) - alphabet_start
+ shift
) % 26) +
134 def caesar_decipher_letter(letter
, shift
):
135 """Decipher a letter, given a shift amount
137 >>> caesar_decipher_letter('b', 1)
139 >>> caesar_decipher_letter('b', 2)
142 return caesar_encipher_letter(letter
, -shift
)
144 def caesar_encipher(message
, shift
):
145 """Encipher a message with the Caesar cipher of given shift
147 >>> caesar_encipher('abc', 1)
149 >>> caesar_encipher('abc', 2)
151 >>> caesar_encipher('abcxyz', 2)
153 >>> caesar_encipher('ab cx yz', 2)
155 >>> caesar_encipher('Héllo World!', 2)
158 enciphered
= [caesar_encipher_letter(l
, shift
) for l
in message
]
159 return ''.join(enciphered
)
161 def caesar_decipher(message
, shift
):
162 """Decipher a message with the Caesar cipher of given shift
164 >>> caesar_decipher('bcd', 1)
166 >>> caesar_decipher('cde', 2)
168 >>> caesar_decipher('cd ez ab', 2)
170 >>> caesar_decipher('Jgnnq Yqtnf!', 2)
173 return caesar_encipher(message
, -shift
)
175 def affine_encipher_letter(accented_letter
, multiplier
=1, adder
=0, one_based
=True):
176 """Encipher a letter, given a multiplier and adder
178 >>> ''.join([affine_encipher_letter(l, 3, 5, True) \
179 for l in string.ascii_uppercase])
180 'HKNQTWZCFILORUXADGJMPSVYBE'
181 >>> ''.join([affine_encipher_letter(l, 3, 5, False) \
182 for l in string.ascii_uppercase])
183 'FILORUXADGJMPSVYBEHKNQTWZC'
185 letter
= unaccent(accented_letter
)
186 if letter
in string
.ascii_letters
:
187 if letter
in string
.ascii_uppercase
:
188 alphabet_start
= ord('A')
190 alphabet_start
= ord('a')
191 letter_number
= ord(letter
) - alphabet_start
192 if one_based
: letter_number
+= 1
193 cipher_number
= (letter_number
* multiplier
+ adder
) % 26
194 if one_based
: cipher_number
-= 1
195 return chr(cipher_number
% 26 + alphabet_start
)
199 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
200 """Encipher a letter, given a multiplier and adder
202 >>> ''.join([affine_decipher_letter(l, 3, 5, True) \
203 for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
204 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
205 >>> ''.join([affine_decipher_letter(l, 3, 5, False) \
206 for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
207 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
209 if letter
in string
.ascii_letters
:
210 if letter
in string
.ascii_uppercase
:
211 alphabet_start
= ord('A')
213 alphabet_start
= ord('a')
214 cipher_number
= ord(letter
) - alphabet_start
215 if one_based
: cipher_number
+= 1
217 modular_division_table
[multiplier
]
218 [(cipher_number
- adder
) % 26])
219 if one_based
: plaintext_number
-= 1
220 return chr(plaintext_number
% 26 + alphabet_start
)
224 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
225 """Encipher a message
227 >>> affine_encipher('hours passed during which jerico tried every ' \
228 'trick he could think of', 15, 22, True)
229 'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
231 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
)
233 return ''.join(enciphered
)
235 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
236 """Decipher a message
238 >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
239 'jfaoe ls omytd jlaxe mh', 15, 22, True)
240 'hours passed during which jerico tried every trick he could think of'
242 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
)
244 return ''.join(enciphered
)
247 class KeywordWrapAlphabet(Enum
):
253 def keyword_cipher_alphabet_of(keyword
, wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
254 """Find the cipher alphabet given a keyword.
255 wrap_alphabet controls how the rest of the alphabet is added
258 >>> keyword_cipher_alphabet_of('bayes')
259 'bayescdfghijklmnopqrtuvwxz'
260 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_a)
261 'bayescdfghijklmnopqrtuvwxz'
262 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_last)
263 'bayestuvwxzcdfghijklmnopqr'
264 >>> keyword_cipher_alphabet_of('bayes', KeywordWrapAlphabet.from_largest)
265 'bayeszcdfghijklmnopqrtuvwx'
267 if wrap_alphabet
== KeywordWrapAlphabet
.from_a
:
268 cipher_alphabet
= ''.join(deduplicate(sanitise(keyword
) +
269 string
.ascii_lowercase
))
271 if wrap_alphabet
== KeywordWrapAlphabet
.from_last
:
272 last_keyword_letter
= deduplicate(sanitise(keyword
))[-1]
274 last_keyword_letter
= sorted(sanitise(keyword
))[-1]
275 last_keyword_position
= string
.ascii_lowercase
.find(
276 last_keyword_letter
) + 1
277 cipher_alphabet
= ''.join(
278 deduplicate(sanitise(keyword
) +
279 string
.ascii_lowercase
[last_keyword_position
:] +
280 string
.ascii_lowercase
))
281 return cipher_alphabet
284 def keyword_encipher(message
, keyword
, wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
285 """Enciphers a message with a keyword substitution cipher.
286 wrap_alphabet controls how the rest of the alphabet is added
289 1 : from the last letter in the sanitised keyword
290 2 : from the largest letter in the sanitised keyword
292 >>> keyword_encipher('test message', 'bayes')
294 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_a)
296 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_last)
298 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_largest)
301 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
302 cipher_translation
= ''.maketrans(string
.ascii_lowercase
, cipher_alphabet
)
303 return unaccent(message
).lower().translate(cipher_translation
)
305 def keyword_decipher(message
, keyword
, wrap_alphabet
=KeywordWrapAlphabet
.from_a
):
306 """Deciphers a message with a keyword substitution cipher.
307 wrap_alphabet controls how the rest of the alphabet is added
310 1 : from the last letter in the sanitised keyword
311 2 : from the largest letter in the sanitised keyword
313 >>> keyword_decipher('rsqr ksqqbds', 'bayes')
315 >>> keyword_decipher('rsqr ksqqbds', 'bayes', KeywordWrapAlphabet.from_a)
317 >>> keyword_decipher('lskl dskkbus', 'bayes', KeywordWrapAlphabet.from_last)
319 >>> keyword_decipher('qspq jsppbcs', 'bayes', KeywordWrapAlphabet.from_largest)
322 cipher_alphabet
= keyword_cipher_alphabet_of(keyword
, wrap_alphabet
)
323 cipher_translation
= ''.maketrans(cipher_alphabet
, string
.ascii_lowercase
)
324 return message
.lower().translate(cipher_translation
)
327 def vigenere_encipher(message
, keyword
):
330 >>> vigenere_encipher('hello', 'abc')
333 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
334 pairs
= zip(message
, cycle(shifts
))
335 return ''.join([caesar_encipher_letter(l
, k
) for l
, k
in pairs
])
337 def vigenere_decipher(message
, keyword
):
340 >>> vigenere_decipher('hfnlp', 'abc')
343 shifts
= [ord(l
) - ord('a') for l
in sanitise(keyword
)]
344 pairs
= zip(message
, cycle(shifts
))
345 return ''.join([caesar_decipher_letter(l
, k
) for l
, k
in pairs
])
347 beaufort_encipher
=vigenere_decipher
348 beaufort_decipher
=vigenere_encipher
351 def transpositions_of(keyword
):
352 """Finds the transpostions given by a keyword. For instance, the keyword
353 'clever' rearranges to 'celrv', so the first column (0) stays first, the
354 second column (1) moves to third, the third column (2) moves to second,
357 If passed a tuple, assume it's already a transposition and just return it.
359 >>> transpositions_of('clever')
361 >>> transpositions_of('fred')
363 >>> transpositions_of((3, 2, 0, 1))
366 if isinstance(keyword
, tuple):
369 key
= deduplicate(keyword
)
370 transpositions
= tuple(key
.index(l
) for l
in sorted(key
))
371 return transpositions
373 def pad(message_len
, group_len
, fillvalue
):
374 padding_length
= group_len
- message_len
% group_len
375 if padding_length
== group_len
: padding_length
= 0
377 for i
in range(padding_length
):
378 if callable(fillvalue
):
379 padding
+= fillvalue()
384 def column_transposition_encipher(message
, keyword
, fillvalue
=' ',
385 fillcolumnwise
=False,
386 emptycolumnwise
=False):
387 """Enciphers using the column transposition cipher.
388 Message is padded to allow all rows to be the same length.
390 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
392 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
394 >>> column_transposition_encipher('hellothere', 'abcdef')
396 >>> column_transposition_encipher('hellothere', 'abcde')
398 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
400 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
402 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
404 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
406 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
408 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
410 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
412 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
414 >>> column_transposition_encipher('hellothere', 'cleverly')
416 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
418 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
421 transpositions
= transpositions_of(keyword
)
422 message
+= pad(len(message
), len(transpositions
), fillvalue
)
424 rows
= every_nth(message
, len(message
) // len(transpositions
))
426 rows
= chunks(message
, len(transpositions
))
427 transposed
= [transpose(r
, transpositions
) for r
in rows
]
429 return combine_every_nth(transposed
)
431 return ''.join(chain(*transposed
))
433 def column_transposition_decipher(message
, keyword
, fillvalue
=' ',
434 fillcolumnwise
=False,
435 emptycolumnwise
=False):
436 """Deciphers using the column transposition cipher.
437 Message is padded to allow all rows to be the same length.
439 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
441 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
443 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
445 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
447 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
449 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
451 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
453 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
456 transpositions
= transpositions_of(keyword
)
457 message
+= pad(len(message
), len(transpositions
), fillvalue
)
459 rows
= every_nth(message
, len(message
) // len(transpositions
))
461 rows
= chunks(message
, len(transpositions
))
462 untransposed
= [untranspose(r
, transpositions
) for r
in rows
]
464 return combine_every_nth(untransposed
)
466 return ''.join(chain(*untransposed
))
468 def scytale_encipher(message
, rows
, fillvalue
=' '):
469 """Enciphers using the scytale transposition cipher.
470 Message is padded with spaces to allow all rows to be the same length.
472 >>> scytale_encipher('thequickbrownfox', 3)
474 >>> scytale_encipher('thequickbrownfox', 4)
476 >>> scytale_encipher('thequickbrownfox', 5)
477 'tubn hirf ecoo qkwx '
478 >>> scytale_encipher('thequickbrownfox', 6)
480 >>> scytale_encipher('thequickbrownfox', 7)
481 'tqcrnx hukof eibwo '
483 # transpositions = [i for i in range(math.ceil(len(message) / rows))]
484 # return column_transposition_encipher(message, transpositions,
485 # fillvalue=fillvalue, fillcolumnwise=False, emptycolumnwise=True)
486 transpositions
= [i
for i
in range(rows
)]
487 return column_transposition_encipher(message
, transpositions
,
488 fillvalue
=fillvalue
, fillcolumnwise
=True, emptycolumnwise
=False)
490 def scytale_decipher(message
, rows
):
491 """Deciphers using the scytale transposition cipher.
492 Assumes the message is padded so that all rows are the same length.
494 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
496 >>> scytale_decipher('tubnhirfecooqkwx', 4)
498 >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
500 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
502 >>> scytale_decipher('tqcrnx hukof eibwo ', 7)
505 # transpositions = [i for i in range(math.ceil(len(message) / rows))]
506 # return column_transposition_decipher(message, transpositions,
507 # fillcolumnwise=False, emptycolumnwise=True)
508 transpositions
= [i
for i
in range(rows
)]
509 return column_transposition_decipher(message
, transpositions
,
510 fillcolumnwise
=True, emptycolumnwise
=False)
513 def railfence_encipher(message
, height
, fillvalue
=''):
515 Works by splitting the text into sections, then reading across them to
516 generate the rows in the cipher. The rows are then combined to form the
519 Example: the plaintext "hellotherefriends", with a height of four, written
520 out in the railfence as
525 (with the * showing the one character to finish the last section).
526 Each 'section' is two columns, but unfolded. In the example, the first
529 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 2, fillvalue='!')
530 'hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!'
531 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3, fillvalue='!')
532 'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!'
533 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5, fillvalue='!')
534 'hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!'
535 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 10, fillvalue='!')
536 'hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!'
537 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3)
538 'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece'
539 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5)
540 'hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp'
541 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 7)
542 'haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic'
544 sections
= chunks(message
, (height
- 1) * 2, fillvalue
=fillvalue
)
545 n_sections
= len(sections
)
547 rows
= [''.join([s
[0] for s
in sections
])]
548 # process the middle rows of the grid
549 for r
in range(1, height
-1):
550 rows
+= [''.join([s
[r
:r
+1] + s
[height
*2-r
-2:height
*2-r
-1] for s
in sections
])]
551 # process the bottom row
552 rows
+= [''.join([s
[height
- 1:height
] for s
in sections
])]
553 # rows += [' '.join([s[height - 1] for s in sections])]
556 def railfence_decipher(message
, height
, fillvalue
=''):
557 """Railfence decipher.
558 Works by reconstructing the grid used to generate the ciphertext, then
559 unfolding the sections so the text can be concatenated together.
561 Example: given the ciphertext 'hhieterelorfnsled' and a height of 4, first
562 work out that the second row has a character missing, find the rows of the
563 grid, then split the section into its two columns.
565 'hhieterelorfnsled' is split into
570 (spaces added for clarity), which is stored in 'rows'. This is then split
571 into 'down_rows' and 'up_rows':
583 These are then zipped together (after the up_rows are reversed) to recover
586 Most of the procedure is about finding the correct lengths for each row then
587 splitting the ciphertext into those rows.
589 >>> railfence_decipher('hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!', 2).strip('!')
590 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
591 >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!', 3).strip('!')
592 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
593 >>> railfence_decipher('hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!', 5).strip('!')
594 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
595 >>> railfence_decipher('hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!', 10).strip('!')
596 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
597 >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece', 3)
598 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
599 >>> railfence_decipher('hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp', 5)
600 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
601 >>> railfence_decipher('haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic', 7)
602 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
604 # find the number and size of the sections, including how many characters
605 # are missing for a full grid
606 n_sections
= math
.ceil(len(message
) / ((height
- 1) * 2))
607 padding_to_add
= n_sections
* (height
- 1) * 2 - len(message
)
608 # row_lengths are for the both up rows and down rows
609 row_lengths
= [n_sections
] * (height
- 1) * 2
610 for i
in range((height
- 1) * 2 - 1, (height
- 1) * 2 - (padding_to_add
+ 1), -1):
612 # folded_rows are the combined row lengths in the middle of the railfence
613 folded_row_lengths
= [row_lengths
[0]]
614 for i
in range(1, height
-1):
615 folded_row_lengths
+= [row_lengths
[i
] + row_lengths
[-i
]]
616 folded_row_lengths
+= [row_lengths
[height
- 1]]
617 # find the rows that form the railfence grid
620 for i
in folded_row_lengths
:
621 rows
+= [message
[row_start
:row_start
+ i
]]
623 # split the rows into the 'down_rows' (those that form the first column of
624 # a section) and the 'up_rows' (those that ofrm the second column of a
626 down_rows
= [rows
[0]]
628 for i
in range(1, height
-1):
629 down_rows
+= [''.join([c
for n
, c
in enumerate(rows
[i
]) if n
% 2 == 0])]
630 up_rows
+= [''.join([c
for n
, c
in enumerate(rows
[i
]) if n
% 2 == 1])]
631 down_rows
+= [rows
[-1]]
633 return ''.join(c
for r
in zip_longest(*(down_rows
+ up_rows
), fillvalue
='') for c
in r
)
635 def make_cadenus_keycolumn(doubled_letters
= 'vw', start
='a', reverse
=False):
636 """Makes the key column for a Cadenus cipher (the column down between the
639 >>> make_cadenus_keycolumn()['a']
641 >>> make_cadenus_keycolumn()['b']
643 >>> make_cadenus_keycolumn()['c']
645 >>> make_cadenus_keycolumn()['v']
647 >>> make_cadenus_keycolumn()['w']
649 >>> make_cadenus_keycolumn()['z']
651 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['a']
653 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['b']
655 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['c']
657 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['i']
659 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['j']
661 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['v']
663 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['z']
666 index_to_remove
= string
.ascii_lowercase
.find(doubled_letters
[0])
667 short_alphabet
= string
.ascii_lowercase
[:index_to_remove
] + string
.ascii_lowercase
[index_to_remove
+1:]
669 short_alphabet
= ''.join(reversed(short_alphabet
))
670 start_pos
= short_alphabet
.find(start
)
671 rotated_alphabet
= short_alphabet
[start_pos
:] + short_alphabet
[:start_pos
]
672 keycolumn
= {l
: i
for i
, l
in enumerate(rotated_alphabet
)}
673 keycolumn
[doubled_letters
[0]] = keycolumn
[doubled_letters
[1]]
676 def cadenus_encipher(message
, keyword
, keycolumn
, fillvalue
='a'):
677 """Encipher with the Cadenus cipher
679 >>> cadenus_encipher(sanitise('Whoever has made a voyage up the Hudson ' \
680 'must remember the Kaatskill mountains. ' \
681 'They are a dismembered branch of the great'), \
683 make_cadenus_keycolumn(doubled_letters='vw', start='a', reverse=True))
684 'antodeleeeuhrsidrbhmhdrrhnimefmthgeaetakseomehetyaasuvoyegrastmmuuaeenabbtpchehtarorikswosmvaleatned'
685 >>> cadenus_encipher(sanitise('a severe limitation on the usefulness of ' \
686 'the cadenus is that every message must be ' \
687 'a multiple of twenty-five letters long'), \
689 make_cadenus_keycolumn(doubled_letters='vw', start='a', reverse=True))
690 'systretomtattlusoatleeesfiyheasdfnmschbhneuvsnpmtofarenuseieeieltarlmentieetogevesitfaisltngeeuvowul'
692 rows
= chunks(message
, len(message
) // 25, fillvalue
=fillvalue
)
694 rotated_columns
= [col
[start
:] + col
[:start
] for start
, col
in zip([keycolumn
[l
] for l
in keyword
], columns
)]
695 rotated_rows
= zip(*rotated_columns
)
696 transpositions
= transpositions_of(keyword
)
697 transposed
= [transpose(r
, transpositions
) for r
in rotated_rows
]
698 return ''.join(chain(*transposed
))
700 def cadenus_decipher(message
, keyword
, keycolumn
, fillvalue
='a'):
702 >>> cadenus_decipher('antodeleeeuhrsidrbhmhdrrhnimefmthgeaetakseomehetyaa' \
703 'suvoyegrastmmuuaeenabbtpchehtarorikswosmvaleatned', \
705 make_cadenus_keycolumn(reverse=True))
706 'whoeverhasmadeavoyageupthehudsonmustrememberthekaatskillmountainstheyareadismemberedbranchofthegreat'
707 >>> cadenus_decipher('systretomtattlusoatleeesfiyheasdfnmschbhneuvsnpmtof' \
708 'arenuseieeieltarlmentieetogevesitfaisltngeeuvowul', \
710 make_cadenus_keycolumn(reverse=True))
711 'aseverelimitationontheusefulnessofthecadenusisthateverymessagemustbeamultipleoftwentyfiveletterslong'
713 rows
= chunks(message
, len(message
) // 25, fillvalue
=fillvalue
)
714 transpositions
= transpositions_of(keyword
)
715 untransposed_rows
= [untranspose(r
, transpositions
) for r
in rows
]
716 columns
= zip(*untransposed_rows
)
717 rotated_columns
= [col
[-start
:] + col
[:-start
] for start
, col
in zip([keycolumn
[l
] for l
in keyword
], columns
)]
718 rotated_rows
= zip(*rotated_columns
)
719 # return rotated_columns
720 return ''.join(chain(*rotated_rows
))
723 def hill_encipher(matrix
, message_letters
, fillvalue
='a'):
726 >>> hill_encipher(np.matrix([[7,8], [11,11]]), 'hellothere')
728 >>> hill_encipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
733 sanitised_message
= sanitise(message_letters
)
734 if len(sanitised_message
) % n
!= 0:
735 padding
= fillvalue
[0] * (n
- len(sanitised_message
) % n
)
738 message
= [ord(c
) - ord('a') for c
in sanitised_message
+ padding
]
739 message_chunks
= [message
[i
:i
+n
] for i
in range(0, len(message
), n
)]
740 # message_chunks = chunks(message, len(matrix), fillvalue=None)
741 enciphered_chunks
= [((matrix
* np
.matrix(c
).T
).T
).tolist()[0]
742 for c
in message_chunks
]
743 return ''.join([chr(int(round(l
)) % 26 + ord('a'))
744 for l
in sum(enciphered_chunks
, [])])
746 def hill_decipher(matrix
, message
, fillvalue
='a'):
749 >>> hill_decipher(np.matrix([[7,8], [11,11]]), 'drjiqzdrvx')
751 >>> hill_decipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
755 adjoint
= linalg
.det(matrix
)*linalg
.inv(matrix
)
756 inverse_determinant
= modular_division_table
[int(round(linalg
.det(matrix
))) % 26][1]
757 inverse_matrix
= (inverse_determinant
* adjoint
) % 26
758 return hill_encipher(inverse_matrix
, message
, fillvalue
)
761 # Where each piece of text ends up in the AMSCO transpositon cipher.
762 # 'index' shows where the slice appears in the plaintext, with the slice
763 # from 'start' to 'end'
764 AmscoSlice
= collections
.namedtuple('AmscoSlice', ['index', 'start', 'end'])
766 def amsco_transposition_positions(message
, keyword
,
768 fillcolumnwise
=False,
769 emptycolumnwise
=True):
770 """Creates the grid for the AMSCO transposition cipher. Each element in the
771 grid shows the index of that slice and the start and end positions of the
772 plaintext that go to make it up.
774 >>> amsco_transposition_positions(string.ascii_lowercase, 'freddy', \
775 fillpattern=(1, 2)) # doctest: +NORMALIZE_WHITESPACE
776 [[AmscoSlice(index=3, start=4, end=6),
777 AmscoSlice(index=2, start=3, end=4),
778 AmscoSlice(index=0, start=0, end=1),
779 AmscoSlice(index=1, start=1, end=3),
780 AmscoSlice(index=4, start=6, end=7)],
781 [AmscoSlice(index=8, start=12, end=13),
782 AmscoSlice(index=7, start=10, end=12),
783 AmscoSlice(index=5, start=7, end=9),
784 AmscoSlice(index=6, start=9, end=10),
785 AmscoSlice(index=9, start=13, end=15)],
786 [AmscoSlice(index=13, start=19, end=21),
787 AmscoSlice(index=12, start=18, end=19),
788 AmscoSlice(index=10, start=15, end=16),
789 AmscoSlice(index=11, start=16, end=18),
790 AmscoSlice(index=14, start=21, end=22)],
791 [AmscoSlice(index=18, start=27, end=28),
792 AmscoSlice(index=17, start=25, end=27),
793 AmscoSlice(index=15, start=22, end=24),
794 AmscoSlice(index=16, start=24, end=25),
795 AmscoSlice(index=19, start=28, end=30)]]
797 transpositions
= transpositions_of(keyword
)
798 fill_iterator
= cycle(fillpattern
)
800 message_length
= len(message
)
804 while current_position
< message_length
:
806 for _
in range(len(transpositions
)):
807 index
= next(indices
)
808 gap
= next(fill_iterator
)
809 row
+= [AmscoSlice(index
, current_position
, current_position
+ gap
)]
810 current_position
+= gap
812 return [transpose(r
, transpositions
) for r
in grid
]
814 def amsco_transposition_encipher(message
, keyword
, fillpattern
=(1,2)):
815 """AMSCO transposition encipher.
817 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(1, 2))
819 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(2, 1))
821 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(1, 2))
823 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(2, 1))
825 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2))
826 'hecsoisttererteipexhomen'
827 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(2, 1))
828 'heetcisooestrrepeixthemn'
829 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2))
830 'hxomeiphscerettoisenteer'
832 grid
= amsco_transposition_positions(message
, keyword
, fillpattern
=fillpattern
)
833 ct_as_grid
= [[message
[s
.start
:s
.end
] for s
in r
] for r
in grid
]
834 return combine_every_nth(ct_as_grid
)
837 def amsco_transposition_decipher(message
, keyword
, fillpattern
=(1,2)):
838 """AMSCO transposition decipher
840 >>> amsco_transposition_decipher('hoteelhler', 'abc', fillpattern=(1, 2))
842 >>> amsco_transposition_decipher('hetelhelor', 'abc', fillpattern=(2, 1))
844 >>> amsco_transposition_decipher('hotelerelh', 'acb', fillpattern=(1, 2))
846 >>> amsco_transposition_decipher('hetelorlhe', 'acb', fillpattern=(2, 1))
848 >>> amsco_transposition_decipher('hecsoisttererteipexhomen', 'cipher', fillpattern=(1, 2))
849 'hereissometexttoencipher'
850 >>> amsco_transposition_decipher('heetcisooestrrepeixthemn', 'cipher', fillpattern=(2, 1))
851 'hereissometexttoencipher'
852 >>> amsco_transposition_decipher('hxomeiphscerettoisenteer', 'cipher', fillpattern=(1, 3, 2))
853 'hereissometexttoencipher'
856 grid
= amsco_transposition_positions(message
, keyword
, fillpattern
=fillpattern
)
857 transposed_sections
= [s
for c
in [l
for l
in zip(*grid
)] for s
in c
]
858 plaintext_list
= [''] * len(transposed_sections
)
860 for slice in transposed_sections
:
861 plaintext_list
[slice.index
] = message
[current_pos
:current_pos
-slice.start
+slice.end
][:len(message
[slice.start
:slice.end
])]
862 current_pos
+= len(message
[slice.start
:slice.end
])
863 return ''.join(plaintext_list
)
866 class PocketEnigma(object):
867 """A pocket enigma machine
868 The wheel is internally represented as a 26-element list self.wheel_map,
869 where wheel_map[i] == j shows that the position i places on from the arrow
870 maps to the position j places on.
872 def __init__(self
, wheel
=1, position
='a'):
873 """initialise the pocket enigma, including which wheel to use and the
874 starting position of the wheel.
876 The wheel is either 1 or 2 (the predefined wheels) or a list of letter
879 The position is the letter pointed to by the arrow on the wheel.
882 [25, 4, 23, 10, 1, 7, 9, 5, 12, 6, 3, 17, 8, 14, 13, 21, 19, 11, 20, 16, 18, 15, 24, 2, 22, 0]
886 self
.wheel1
= [('a', 'z'), ('b', 'e'), ('c', 'x'), ('d', 'k'),
887 ('f', 'h'), ('g', 'j'), ('i', 'm'), ('l', 'r'), ('n', 'o'),
888 ('p', 'v'), ('q', 't'), ('s', 'u'), ('w', 'y')]
889 self
.wheel2
= [('a', 'c'), ('b', 'd'), ('e', 'w'), ('f', 'i'),
890 ('g', 'p'), ('h', 'm'), ('j', 'k'), ('l', 'n'), ('o', 'q'),
891 ('r', 'z'), ('s', 'u'), ('t', 'v'), ('x', 'y')]
893 self
.make_wheel_map(self
.wheel1
)
895 self
.make_wheel_map(self
.wheel2
)
897 self
.validate_wheel_spec(wheel
)
898 self
.make_wheel_map(wheel
)
899 if position
in string
.ascii_lowercase
:
900 self
.position
= ord(position
) - ord('a')
902 self
.position
= position
904 def make_wheel_map(self
, wheel_spec
):
905 """Expands a wheel specification from a list of letter-letter pairs
906 into a full wheel_map.
908 >>> pe.make_wheel_map(pe.wheel2)
909 [2, 3, 0, 1, 22, 8, 15, 12, 5, 10, 9, 13, 7, 11, 16, 6, 14, 25, 20, 21, 18, 19, 4, 24, 23, 17]
911 self
.validate_wheel_spec(wheel_spec
)
912 self
.wheel_map
= [0] * 26
914 self
.wheel_map
[ord(p
[0]) - ord('a')] = ord(p
[1]) - ord('a')
915 self
.wheel_map
[ord(p
[1]) - ord('a')] = ord(p
[0]) - ord('a')
916 return self
.wheel_map
918 def validate_wheel_spec(self
, wheel_spec
):
919 """Validates that a wheel specificaiton will turn into a valid wheel
922 >>> pe.validate_wheel_spec([])
923 Traceback (most recent call last):
925 ValueError: Wheel specification has 0 pairs, requires 13
926 >>> pe.validate_wheel_spec([('a', 'b', 'c')]*13)
927 Traceback (most recent call last):
929 ValueError: Not all mappings in wheel specificationhave two elements
930 >>> pe.validate_wheel_spec([('a', 'b')]*13)
931 Traceback (most recent call last):
933 ValueError: Wheel specification does not contain 26 letters
935 if len(wheel_spec
) != 13:
936 raise ValueError("Wheel specification has {} pairs, requires 13".
937 format(len(wheel_spec
)))
940 raise ValueError("Not all mappings in wheel specification"
942 if len(set([p
[0] for p
in wheel_spec
] +
943 [p
[1] for p
in wheel_spec
])) != 26:
944 raise ValueError("Wheel specification does not contain 26 letters")
946 def encipher_letter(self
, letter
):
947 """Enciphers a single letter, by advancing the wheel before looking up
948 the letter on the wheel.
950 >>> pe.set_position('f')
952 >>> pe.encipher_letter('k')
956 return self
.lookup(letter
)
957 decipher_letter
= encipher_letter
959 def lookup(self
, letter
):
960 """Look up what a letter enciphers to, without turning the wheel.
962 >>> pe.set_position('f')
964 >>> ''.join([pe.lookup(l) for l in string.ascii_lowercase])
965 'udhbfejcpgmokrliwntsayqzvx'
969 if letter
in string
.ascii_lowercase
:
971 (self
.wheel_map
[(ord(letter
) - ord('a') - self
.position
) % 26] +
972 self
.position
) % 26 +
978 """Advances the wheel one position.
980 >>> pe.set_position('f')
985 self
.position
= (self
.position
+ 1) % 26
988 def encipher(self
, message
, starting_position
=None):
989 """Enciphers a whole message.
991 >>> pe.set_position('f')
993 >>> pe.encipher('helloworld')
995 >>> pe.set_position('f')
997 >>> pe.encipher('kjsglcjoqc')
999 >>> pe.encipher('helloworld', starting_position = 'x')
1002 if starting_position
:
1003 self
.set_position(starting_position
)
1006 transformed
+= self
.encipher_letter(l
)
1010 def set_position(self
, position
):
1011 """Sets the position of the wheel, by specifying the letter the arrow
1014 >>> pe.set_position('a')
1016 >>> pe.set_position('m')
1018 >>> pe.set_position('z')
1021 self
.position
= ord(position
) - ord('a')
1022 return self
.position
1025 if __name__
== "__main__":
1027 doctest
.testmod(extraglobs
={'pe': PocketEnigma(1, 'a')})