Added challenge 8 files, done 8a
[cipher-training.git] / cipher.py
1 import string
2 import collections
3 import math
4 from enum import Enum
5 from itertools import zip_longest, cycle, chain, count
6 import numpy as np
7 from numpy import matrix
8 from numpy import linalg
9 from language_models import *
10
11
12 modular_division_table = [[0]*26 for _ in range(26)]
13 for a in range(26):
14 for b in range(26):
15 c = (a * b) % 26
16 modular_division_table[b][c] = a
17
18
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
22
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!']
32 """
33 split_text = chunks(text, n, fillvalue)
34 return [''.join(l) for l in zip_longest(*split_text, fillvalue=fillvalue)]
35
36 def combine_every_nth(split_text):
37 """Reforms a text split into every_nth strings
38
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'
45 """
46 return ''.join([''.join(l)
47 for l in zip_longest(*split_text, fillvalue='')])
48
49 def chunks(text, n, fillvalue=None):
50 """Split a text into chunks of n characters
51
52 >>> chunks('abcdefghi', 3)
53 ['abc', 'def', 'ghi']
54 >>> chunks('abcdefghi', 4)
55 ['abcd', 'efgh', 'i']
56 >>> chunks('abcdefghi', 4, fillvalue='!')
57 ['abcd', 'efgh', 'i!!!']
58 """
59 if fillvalue:
60 padding = fillvalue[0] * (n - len(text) % n)
61 else:
62 padding = ''
63 return [(text+padding)[i:i+n] for i in range(0, len(text), n)]
64
65 def transpose(items, transposition):
66 """Moves items around according to the given transposition
67
68 >>> transpose(['a', 'b', 'c', 'd'], (0,1,2,3))
69 ['a', 'b', 'c', 'd']
70 >>> transpose(['a', 'b', 'c', 'd'], (3,1,2,0))
71 ['d', 'b', 'c', 'a']
72 >>> transpose([10,11,12,13,14,15], (3,2,4,1,5,0))
73 [13, 12, 14, 11, 15, 10]
74 """
75 transposed = [''] * len(transposition)
76 for p, t in enumerate(transposition):
77 transposed[p] = items[t]
78 return transposed
79
80 def untranspose(items, transposition):
81 """Undoes a transpose
82
83 >>> untranspose(['a', 'b', 'c', 'd'], [0,1,2,3])
84 ['a', 'b', 'c', 'd']
85 >>> untranspose(['d', 'b', 'c', 'a'], [3,1,2,0])
86 ['a', 'b', 'c', 'd']
87 >>> untranspose([13, 12, 14, 11, 15, 10], [3,2,4,1,5,0])
88 [10, 11, 12, 13, 14, 15]
89 """
90 transposed = [''] * len(transposition)
91 for p, t in enumerate(transposition):
92 transposed[t] = items[p]
93 return transposed
94
95 def deduplicate(text):
96 return list(collections.OrderedDict.fromkeys(text))
97
98
99 def caesar_encipher_letter(accented_letter, shift):
100 """Encipher a letter, given a shift amount
101
102 >>> caesar_encipher_letter('a', 1)
103 'b'
104 >>> caesar_encipher_letter('a', 2)
105 'c'
106 >>> caesar_encipher_letter('b', 2)
107 'd'
108 >>> caesar_encipher_letter('x', 2)
109 'z'
110 >>> caesar_encipher_letter('y', 2)
111 'a'
112 >>> caesar_encipher_letter('z', 2)
113 'b'
114 >>> caesar_encipher_letter('z', -1)
115 'y'
116 >>> caesar_encipher_letter('a', -1)
117 'z'
118 >>> caesar_encipher_letter('A', 1)
119 'B'
120 >>> caesar_encipher_letter('é', 1)
121 'f'
122 """
123 letter = unaccent(accented_letter)
124 if letter in string.ascii_letters:
125 if letter in string.ascii_uppercase:
126 alphabet_start = ord('A')
127 else:
128 alphabet_start = ord('a')
129 return chr(((ord(letter) - alphabet_start + shift) % 26) +
130 alphabet_start)
131 else:
132 return letter
133
134 def caesar_decipher_letter(letter, shift):
135 """Decipher a letter, given a shift amount
136
137 >>> caesar_decipher_letter('b', 1)
138 'a'
139 >>> caesar_decipher_letter('b', 2)
140 'z'
141 """
142 return caesar_encipher_letter(letter, -shift)
143
144 def caesar_encipher(message, shift):
145 """Encipher a message with the Caesar cipher of given shift
146
147 >>> caesar_encipher('abc', 1)
148 'bcd'
149 >>> caesar_encipher('abc', 2)
150 'cde'
151 >>> caesar_encipher('abcxyz', 2)
152 'cdezab'
153 >>> caesar_encipher('ab cx yz', 2)
154 'cd ez ab'
155 >>> caesar_encipher('Héllo World!', 2)
156 'Jgnnq Yqtnf!'
157 """
158 enciphered = [caesar_encipher_letter(l, shift) for l in message]
159 return ''.join(enciphered)
160
161 def caesar_decipher(message, shift):
162 """Decipher a message with the Caesar cipher of given shift
163
164 >>> caesar_decipher('bcd', 1)
165 'abc'
166 >>> caesar_decipher('cde', 2)
167 'abc'
168 >>> caesar_decipher('cd ez ab', 2)
169 'ab cx yz'
170 >>> caesar_decipher('Jgnnq Yqtnf!', 2)
171 'Hello World!'
172 """
173 return caesar_encipher(message, -shift)
174
175 def affine_encipher_letter(accented_letter, multiplier=1, adder=0, one_based=True):
176 """Encipher a letter, given a multiplier and adder
177
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'
184 """
185 letter = unaccent(accented_letter)
186 if letter in string.ascii_letters:
187 if letter in string.ascii_uppercase:
188 alphabet_start = ord('A')
189 else:
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)
196 else:
197 return letter
198
199 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
200 """Encipher a letter, given a multiplier and adder
201
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'
208 """
209 if letter in string.ascii_letters:
210 if letter in string.ascii_uppercase:
211 alphabet_start = ord('A')
212 else:
213 alphabet_start = ord('a')
214 cipher_number = ord(letter) - alphabet_start
215 if one_based: cipher_number += 1
216 plaintext_number = (
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)
221 else:
222 return letter
223
224 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
225 """Encipher a message
226
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'
230 """
231 enciphered = [affine_encipher_letter(l, multiplier, adder, one_based)
232 for l in message]
233 return ''.join(enciphered)
234
235 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
236 """Decipher a message
237
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'
241 """
242 enciphered = [affine_decipher_letter(l, multiplier, adder, one_based)
243 for l in message]
244 return ''.join(enciphered)
245
246
247 class KeywordWrapAlphabet(Enum):
248 from_a = 1
249 from_last = 2
250 from_largest = 3
251
252
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
256 after the keyword.
257
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'
266 """
267 if wrap_alphabet == KeywordWrapAlphabet.from_a:
268 cipher_alphabet = ''.join(deduplicate(sanitise(keyword) +
269 string.ascii_lowercase))
270 else:
271 if wrap_alphabet == KeywordWrapAlphabet.from_last:
272 last_keyword_letter = deduplicate(sanitise(keyword))[-1]
273 else:
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
282
283
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
287 after the keyword.
288 0 : from 'a'
289 1 : from the last letter in the sanitised keyword
290 2 : from the largest letter in the sanitised keyword
291
292 >>> keyword_encipher('test message', 'bayes')
293 'rsqr ksqqbds'
294 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_a)
295 'rsqr ksqqbds'
296 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_last)
297 'lskl dskkbus'
298 >>> keyword_encipher('test message', 'bayes', KeywordWrapAlphabet.from_largest)
299 'qspq jsppbcs'
300 """
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)
304
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
308 after the keyword.
309 0 : from 'a'
310 1 : from the last letter in the sanitised keyword
311 2 : from the largest letter in the sanitised keyword
312
313 >>> keyword_decipher('rsqr ksqqbds', 'bayes')
314 'test message'
315 >>> keyword_decipher('rsqr ksqqbds', 'bayes', KeywordWrapAlphabet.from_a)
316 'test message'
317 >>> keyword_decipher('lskl dskkbus', 'bayes', KeywordWrapAlphabet.from_last)
318 'test message'
319 >>> keyword_decipher('qspq jsppbcs', 'bayes', KeywordWrapAlphabet.from_largest)
320 'test message'
321 """
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)
325
326
327 def vigenere_encipher(message, keyword):
328 """Vigenere encipher
329
330 >>> vigenere_encipher('hello', 'abc')
331 'hfnlp'
332 """
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])
336
337 def vigenere_decipher(message, keyword):
338 """Vigenere decipher
339
340 >>> vigenere_decipher('hfnlp', 'abc')
341 'hello'
342 """
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])
346
347 beaufort_encipher=vigenere_decipher
348 beaufort_decipher=vigenere_encipher
349
350
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,
355 and so on.
356
357 If passed a tuple, assume it's already a transposition and just return it.
358
359 >>> transpositions_of('clever')
360 (0, 2, 1, 4, 3)
361 >>> transpositions_of('fred')
362 (3, 2, 0, 1)
363 >>> transpositions_of((3, 2, 0, 1))
364 (3, 2, 0, 1)
365 """
366 if isinstance(keyword, tuple):
367 return keyword
368 else:
369 key = deduplicate(keyword)
370 transpositions = tuple(key.index(l) for l in sorted(key))
371 return transpositions
372
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
376 padding = ''
377 for i in range(padding_length):
378 if callable(fillvalue):
379 padding += fillvalue()
380 else:
381 padding += fillvalue
382 return padding
383
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.
389
390 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
391 'hlohr eltee '
392 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
393 'hellothere '
394 >>> column_transposition_encipher('hellothere', 'abcdef')
395 'hellothere '
396 >>> column_transposition_encipher('hellothere', 'abcde')
397 'hellothere'
398 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
399 'hellothere'
400 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
401 'hlohreltee'
402 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
403 'htehlelroe'
404 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
405 'hellothere'
406 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
407 'heotllrehe'
408 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
409 'holrhetlee'
410 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
411 'htleehoelr'
412 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
413 'hleolteher'
414 >>> column_transposition_encipher('hellothere', 'cleverly')
415 'hleolthre e '
416 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
417 'hleolthre!e!'
418 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
419 'hleolthre*e*'
420 """
421 transpositions = transpositions_of(keyword)
422 message += pad(len(message), len(transpositions), fillvalue)
423 if fillcolumnwise:
424 rows = every_nth(message, len(message) // len(transpositions))
425 else:
426 rows = chunks(message, len(transpositions))
427 transposed = [transpose(r, transpositions) for r in rows]
428 if emptycolumnwise:
429 return combine_every_nth(transposed)
430 else:
431 return ''.join(chain(*transposed))
432
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.
438
439 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
440 'hellothere'
441 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
442 'hellothere'
443 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
444 'hellothere'
445 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
446 'hellothere'
447 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
448 'hellothere'
449 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
450 'hellothere'
451 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
452 'hellothere'
453 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
454 'hellothere'
455 """
456 transpositions = transpositions_of(keyword)
457 message += pad(len(message), len(transpositions), fillvalue)
458 if emptycolumnwise:
459 rows = every_nth(message, len(message) // len(transpositions))
460 else:
461 rows = chunks(message, len(transpositions))
462 untransposed = [untranspose(r, transpositions) for r in rows]
463 if fillcolumnwise:
464 return combine_every_nth(untransposed)
465 else:
466 return ''.join(chain(*untransposed))
467
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.
471
472 >>> scytale_encipher('thequickbrownfox', 3)
473 'tcnhkfeboqrxuo iw '
474 >>> scytale_encipher('thequickbrownfox', 4)
475 'tubnhirfecooqkwx'
476 >>> scytale_encipher('thequickbrownfox', 5)
477 'tubn hirf ecoo qkwx '
478 >>> scytale_encipher('thequickbrownfox', 6)
479 'tqcrnxhukof eibwo '
480 >>> scytale_encipher('thequickbrownfox', 7)
481 'tqcrnx hukof eibwo '
482 """
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)
489
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.
493
494 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
495 'thequickbrownfox '
496 >>> scytale_decipher('tubnhirfecooqkwx', 4)
497 'thequickbrownfox'
498 >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
499 'thequickbrownfox '
500 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
501 'thequickbrownfox '
502 >>> scytale_decipher('tqcrnx hukof eibwo ', 7)
503 'thequickbrownfox '
504 """
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)
511
512
513 def railfence_encipher(message, height, fillvalue=''):
514 """Railfence cipher.
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
517 ciphertext.
518
519 Example: the plaintext "hellotherefriends", with a height of four, written
520 out in the railfence as
521 h h i
522 etere*
523 lorfns
524 l e d
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
527 section is 'hellot'.
528
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'
543 """
544 sections = chunks(message, (height - 1) * 2, fillvalue=fillvalue)
545 n_sections = len(sections)
546 # Add the top row
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])]
554 return ''.join(rows)
555
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.
560
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.
564
565 'hhieterelorfnsled' is split into
566 h h i
567 etere
568 lorfns
569 l e d
570 (spaces added for clarity), which is stored in 'rows'. This is then split
571 into 'down_rows' and 'up_rows':
572
573 down_rows:
574 hhi
575 eee
576 lrn
577 led
578
579 up_rows:
580 tr
581 ofs
582
583 These are then zipped together (after the up_rows are reversed) to recover
584 the plaintext.
585
586 Most of the procedure is about finding the correct lengths for each row then
587 splitting the ciphertext into those rows.
588
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'
603 """
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):
611 row_lengths[i] -= 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
618 rows = []
619 row_start = 0
620 for i in folded_row_lengths:
621 rows += [message[row_start:row_start + i]]
622 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
625 # section).
626 down_rows = [rows[0]]
627 up_rows = []
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]]
632 up_rows.reverse()
633 return ''.join(c for r in zip_longest(*(down_rows + up_rows), fillvalue='') for c in r)
634
635
636 def hill_encipher(matrix, message_letters, fillvalue='a'):
637 """Hill cipher
638
639 >>> hill_encipher(np.matrix([[7,8], [11,11]]), 'hellothere')
640 'drjiqzdrvx'
641 >>> hill_encipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
642 'hello there')
643 'tfjflpznvyac'
644 """
645 n = len(matrix)
646 sanitised_message = sanitise(message_letters)
647 if len(sanitised_message) % n != 0:
648 padding = fillvalue[0] * (n - len(sanitised_message) % n)
649 else:
650 padding = ''
651 message = [ord(c) - ord('a') for c in sanitised_message + padding]
652 message_chunks = [message[i:i+n] for i in range(0, len(message), n)]
653 # message_chunks = chunks(message, len(matrix), fillvalue=None)
654 enciphered_chunks = [((matrix * np.matrix(c).T).T).tolist()[0]
655 for c in message_chunks]
656 return ''.join([chr(int(round(l)) % 26 + ord('a'))
657 for l in sum(enciphered_chunks, [])])
658
659 def hill_decipher(matrix, message, fillvalue='a'):
660 """Hill cipher
661
662 >>> hill_decipher(np.matrix([[7,8], [11,11]]), 'drjiqzdrvx')
663 'hellothere'
664 >>> hill_decipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
665 'tfjflpznvyac')
666 'hellothereaa'
667 """
668 adjoint = linalg.det(matrix)*linalg.inv(matrix)
669 inverse_determinant = modular_division_table[int(round(linalg.det(matrix))) % 26][1]
670 inverse_matrix = (inverse_determinant * adjoint) % 26
671 return hill_encipher(inverse_matrix, message, fillvalue)
672
673
674 # Where each piece of text ends up in the AMSCO transpositon cipher.
675 # 'index' shows where the slice appears in the plaintext, with the slice
676 # from 'start' to 'end'
677 AmscoSlice = collections.namedtuple('AmscoSlice', ['index', 'start', 'end'])
678
679 def amsco_transposition_positions(message, keyword,
680 fillpattern=(1, 2),
681 fillcolumnwise=False,
682 emptycolumnwise=True):
683 """Creates the grid for the AMSCO transposition cipher. Each element in the
684 grid shows the index of that slice and the start and end positions of the
685 plaintext that go to make it up.
686
687 >>> amsco_transposition_positions(string.ascii_lowercase, 'freddy', \
688 fillpattern=(1, 2)) # doctest: +NORMALIZE_WHITESPACE
689 [[AmscoSlice(index=3, start=4, end=6),
690 AmscoSlice(index=2, start=3, end=4),
691 AmscoSlice(index=0, start=0, end=1),
692 AmscoSlice(index=1, start=1, end=3),
693 AmscoSlice(index=4, start=6, end=7)],
694 [AmscoSlice(index=8, start=12, end=13),
695 AmscoSlice(index=7, start=10, end=12),
696 AmscoSlice(index=5, start=7, end=9),
697 AmscoSlice(index=6, start=9, end=10),
698 AmscoSlice(index=9, start=13, end=15)],
699 [AmscoSlice(index=13, start=19, end=21),
700 AmscoSlice(index=12, start=18, end=19),
701 AmscoSlice(index=10, start=15, end=16),
702 AmscoSlice(index=11, start=16, end=18),
703 AmscoSlice(index=14, start=21, end=22)],
704 [AmscoSlice(index=18, start=27, end=28),
705 AmscoSlice(index=17, start=25, end=27),
706 AmscoSlice(index=15, start=22, end=24),
707 AmscoSlice(index=16, start=24, end=25),
708 AmscoSlice(index=19, start=28, end=30)]]
709 """
710 transpositions = transpositions_of(keyword)
711 fill_iterator = cycle(fillpattern)
712 indices = count()
713 message_length = len(message)
714
715 current_position = 0
716 grid = []
717 while current_position < message_length:
718 row = []
719 for _ in range(len(transpositions)):
720 index = next(indices)
721 gap = next(fill_iterator)
722 row += [AmscoSlice(index, current_position, current_position + gap)]
723 current_position += gap
724 grid += [row]
725 return [transpose(r, transpositions) for r in grid]
726
727 def amsco_transposition_encipher(message, keyword, fillpattern=(1,2)):
728 """AMSCO transposition encipher.
729
730 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(1, 2))
731 'hoteelhler'
732 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(2, 1))
733 'hetelhelor'
734 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(1, 2))
735 'hotelerelh'
736 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(2, 1))
737 'hetelorlhe'
738 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2))
739 'hecsoisttererteipexhomen'
740 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(2, 1))
741 'heetcisooestrrepeixthemn'
742 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2))
743 'hxomeiphscerettoisenteer'
744 """
745 grid = amsco_transposition_positions(message, keyword, fillpattern=fillpattern)
746 ct_as_grid = [[message[s.start:s.end] for s in r] for r in grid]
747 return combine_every_nth(ct_as_grid)
748
749
750 def amsco_transposition_decipher(message, keyword, fillpattern=(1,2)):
751 """AMSCO transposition decipher
752
753 >>> amsco_transposition_decipher('hoteelhler', 'abc', fillpattern=(1, 2))
754 'hellothere'
755 >>> amsco_transposition_decipher('hetelhelor', 'abc', fillpattern=(2, 1))
756 'hellothere'
757 >>> amsco_transposition_decipher('hotelerelh', 'acb', fillpattern=(1, 2))
758 'hellothere'
759 >>> amsco_transposition_decipher('hetelorlhe', 'acb', fillpattern=(2, 1))
760 'hellothere'
761 >>> amsco_transposition_decipher('hecsoisttererteipexhomen', 'cipher', fillpattern=(1, 2))
762 'hereissometexttoencipher'
763 >>> amsco_transposition_decipher('heetcisooestrrepeixthemn', 'cipher', fillpattern=(2, 1))
764 'hereissometexttoencipher'
765 >>> amsco_transposition_decipher('hxomeiphscerettoisenteer', 'cipher', fillpattern=(1, 3, 2))
766 'hereissometexttoencipher'
767 """
768
769 grid = amsco_transposition_positions(message, keyword, fillpattern=fillpattern)
770 transposed_sections = [s for c in [l for l in zip(*grid)] for s in c]
771 plaintext_list = [''] * len(transposed_sections)
772 current_pos = 0
773 for slice in transposed_sections:
774 plaintext_list[slice.index] = message[current_pos:current_pos-slice.start+slice.end][:len(message[slice.start:slice.end])]
775 current_pos += len(message[slice.start:slice.end])
776 return ''.join(plaintext_list)
777
778
779 class PocketEnigma(object):
780 """A pocket enigma machine
781 The wheel is internally represented as a 26-element list self.wheel_map,
782 where wheel_map[i] == j shows that the position i places on from the arrow
783 maps to the position j places on.
784 """
785 def __init__(self, wheel=1, position='a'):
786 """initialise the pocket enigma, including which wheel to use and the
787 starting position of the wheel.
788
789 The wheel is either 1 or 2 (the predefined wheels) or a list of letter
790 pairs.
791
792 The position is the letter pointed to by the arrow on the wheel.
793
794 >>> pe.wheel_map
795 [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]
796 >>> pe.position
797 0
798 """
799 self.wheel1 = [('a', 'z'), ('b', 'e'), ('c', 'x'), ('d', 'k'),
800 ('f', 'h'), ('g', 'j'), ('i', 'm'), ('l', 'r'), ('n', 'o'),
801 ('p', 'v'), ('q', 't'), ('s', 'u'), ('w', 'y')]
802 self.wheel2 = [('a', 'c'), ('b', 'd'), ('e', 'w'), ('f', 'i'),
803 ('g', 'p'), ('h', 'm'), ('j', 'k'), ('l', 'n'), ('o', 'q'),
804 ('r', 'z'), ('s', 'u'), ('t', 'v'), ('x', 'y')]
805 if wheel == 1:
806 self.make_wheel_map(self.wheel1)
807 elif wheel == 2:
808 self.make_wheel_map(self.wheel2)
809 else:
810 self.validate_wheel_spec(wheel)
811 self.make_wheel_map(wheel)
812 if position in string.ascii_lowercase:
813 self.position = ord(position) - ord('a')
814 else:
815 self.position = position
816
817 def make_wheel_map(self, wheel_spec):
818 """Expands a wheel specification from a list of letter-letter pairs
819 into a full wheel_map.
820
821 >>> pe.make_wheel_map(pe.wheel2)
822 [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]
823 """
824 self.validate_wheel_spec(wheel_spec)
825 self.wheel_map = [0] * 26
826 for p in wheel_spec:
827 self.wheel_map[ord(p[0]) - ord('a')] = ord(p[1]) - ord('a')
828 self.wheel_map[ord(p[1]) - ord('a')] = ord(p[0]) - ord('a')
829 return self.wheel_map
830
831 def validate_wheel_spec(self, wheel_spec):
832 """Validates that a wheel specificaiton will turn into a valid wheel
833 map.
834
835 >>> pe.validate_wheel_spec([])
836 Traceback (most recent call last):
837 ...
838 ValueError: Wheel specification has 0 pairs, requires 13
839 >>> pe.validate_wheel_spec([('a', 'b', 'c')]*13)
840 Traceback (most recent call last):
841 ...
842 ValueError: Not all mappings in wheel specificationhave two elements
843 >>> pe.validate_wheel_spec([('a', 'b')]*13)
844 Traceback (most recent call last):
845 ...
846 ValueError: Wheel specification does not contain 26 letters
847 """
848 if len(wheel_spec) != 13:
849 raise ValueError("Wheel specification has {} pairs, requires 13".
850 format(len(wheel_spec)))
851 for p in wheel_spec:
852 if len(p) != 2:
853 raise ValueError("Not all mappings in wheel specification"
854 "have two elements")
855 if len(set([p[0] for p in wheel_spec] +
856 [p[1] for p in wheel_spec])) != 26:
857 raise ValueError("Wheel specification does not contain 26 letters")
858
859 def encipher_letter(self, letter):
860 """Enciphers a single letter, by advancing the wheel before looking up
861 the letter on the wheel.
862
863 >>> pe.set_position('f')
864 5
865 >>> pe.encipher_letter('k')
866 'h'
867 """
868 self.advance()
869 return self.lookup(letter)
870 decipher_letter = encipher_letter
871
872 def lookup(self, letter):
873 """Look up what a letter enciphers to, without turning the wheel.
874
875 >>> pe.set_position('f')
876 5
877 >>> ''.join([pe.lookup(l) for l in string.ascii_lowercase])
878 'udhbfejcpgmokrliwntsayqzvx'
879 >>> pe.lookup('A')
880 ''
881 """
882 if letter in string.ascii_lowercase:
883 return chr(
884 (self.wheel_map[(ord(letter) - ord('a') - self.position) % 26] +
885 self.position) % 26 +
886 ord('a'))
887 else:
888 return ''
889
890 def advance(self):
891 """Advances the wheel one position.
892
893 >>> pe.set_position('f')
894 5
895 >>> pe.advance()
896 6
897 """
898 self.position = (self.position + 1) % 26
899 return self.position
900
901 def encipher(self, message, starting_position=None):
902 """Enciphers a whole message.
903
904 >>> pe.set_position('f')
905 5
906 >>> pe.encipher('helloworld')
907 'kjsglcjoqc'
908 >>> pe.set_position('f')
909 5
910 >>> pe.encipher('kjsglcjoqc')
911 'helloworld'
912 >>> pe.encipher('helloworld', starting_position = 'x')
913 'egrekthnnf'
914 """
915 if starting_position:
916 self.set_position(starting_position)
917 transformed = ''
918 for l in message:
919 transformed += self.encipher_letter(l)
920 return transformed
921 decipher = encipher
922
923 def set_position(self, position):
924 """Sets the position of the wheel, by specifying the letter the arrow
925 points to.
926
927 >>> pe.set_position('a')
928 0
929 >>> pe.set_position('m')
930 12
931 >>> pe.set_position('z')
932 25
933 """
934 self.position = ord(position) - ord('a')
935 return self.position
936
937
938 if __name__ == "__main__":
939 import doctest
940 doctest.testmod(extraglobs={'pe': PocketEnigma(1, 'a')})