2eb89f72306e30e4db99e539e36733aa792d13c4
[cipher-tools.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 import pprint
11
12
13
14 from utilities import *
15 from segment import *
16
17 from caesar import *
18 from affine import *
19 from keyword import *
20 from polybius import *
21 from column_transposition import *
22 from railfence import *
23
24
25 def make_cadenus_keycolumn(doubled_letters = 'vw', start='a', reverse=False):
26 """Makes the key column for a Cadenus cipher (the column down between the
27 rows of letters)
28
29 >>> make_cadenus_keycolumn()['a']
30 0
31 >>> make_cadenus_keycolumn()['b']
32 1
33 >>> make_cadenus_keycolumn()['c']
34 2
35 >>> make_cadenus_keycolumn()['v']
36 21
37 >>> make_cadenus_keycolumn()['w']
38 21
39 >>> make_cadenus_keycolumn()['z']
40 24
41 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['a']
42 1
43 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['b']
44 0
45 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['c']
46 24
47 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['i']
48 18
49 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['j']
50 18
51 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['v']
52 6
53 >>> make_cadenus_keycolumn(doubled_letters='ij', start='b', reverse=True)['z']
54 2
55 """
56 index_to_remove = string.ascii_lowercase.find(doubled_letters[0])
57 short_alphabet = string.ascii_lowercase[:index_to_remove] + string.ascii_lowercase[index_to_remove+1:]
58 if reverse:
59 short_alphabet = cat(reversed(short_alphabet))
60 start_pos = short_alphabet.find(start)
61 rotated_alphabet = short_alphabet[start_pos:] + short_alphabet[:start_pos]
62 keycolumn = {l: i for i, l in enumerate(rotated_alphabet)}
63 keycolumn[doubled_letters[0]] = keycolumn[doubled_letters[1]]
64 return keycolumn
65
66 def cadenus_encipher(message, keyword, keycolumn, fillvalue='a'):
67 """Encipher with the Cadenus cipher
68
69 >>> cadenus_encipher(sanitise('Whoever has made a voyage up the Hudson ' \
70 'must remember the Kaatskill mountains. ' \
71 'They are a dismembered branch of the great'), \
72 'wink', \
73 make_cadenus_keycolumn(doubled_letters='vw', start='a', reverse=True))
74 'antodeleeeuhrsidrbhmhdrrhnimefmthgeaetakseomehetyaasuvoyegrastmmuuaeenabbtpchehtarorikswosmvaleatned'
75 >>> cadenus_encipher(sanitise('a severe limitation on the usefulness of ' \
76 'the cadenus is that every message must be ' \
77 'a multiple of twenty-five letters long'), \
78 'easy', \
79 make_cadenus_keycolumn(doubled_letters='vw', start='a', reverse=True))
80 'systretomtattlusoatleeesfiyheasdfnmschbhneuvsnpmtofarenuseieeieltarlmentieetogevesitfaisltngeeuvowul'
81 """
82 rows = chunks(message, len(message) // 25, fillvalue=fillvalue)
83 columns = zip(*rows)
84 rotated_columns = [col[start:] + col[:start] for start, col in zip([keycolumn[l] for l in keyword], columns)]
85 rotated_rows = zip(*rotated_columns)
86 transpositions = transpositions_of(keyword)
87 transposed = [transpose(r, transpositions) for r in rotated_rows]
88 return cat(chain(*transposed))
89
90 def cadenus_decipher(message, keyword, keycolumn, fillvalue='a'):
91 """
92 >>> cadenus_decipher('antodeleeeuhrsidrbhmhdrrhnimefmthgeaetakseomehetyaa' \
93 'suvoyegrastmmuuaeenabbtpchehtarorikswosmvaleatned', \
94 'wink', \
95 make_cadenus_keycolumn(reverse=True))
96 'whoeverhasmadeavoyageupthehudsonmustrememberthekaatskillmountainstheyareadismemberedbranchofthegreat'
97 >>> cadenus_decipher('systretomtattlusoatleeesfiyheasdfnmschbhneuvsnpmtof' \
98 'arenuseieeieltarlmentieetogevesitfaisltngeeuvowul', \
99 'easy', \
100 make_cadenus_keycolumn(reverse=True))
101 'aseverelimitationontheusefulnessofthecadenusisthateverymessagemustbeamultipleoftwentyfiveletterslong'
102 """
103 rows = chunks(message, len(message) // 25, fillvalue=fillvalue)
104 transpositions = transpositions_of(keyword)
105 untransposed_rows = [untranspose(r, transpositions) for r in rows]
106 columns = zip(*untransposed_rows)
107 rotated_columns = [col[-start:] + col[:-start] for start, col in zip([keycolumn[l] for l in keyword], columns)]
108 rotated_rows = zip(*rotated_columns)
109 # return rotated_columns
110 return cat(chain(*rotated_rows))
111
112
113 def hill_encipher(matrix, message_letters, fillvalue='a'):
114 """Hill cipher
115
116 >>> hill_encipher(np.matrix([[7,8], [11,11]]), 'hellothere')
117 'drjiqzdrvx'
118 >>> hill_encipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
119 'hello there')
120 'tfjflpznvyac'
121 """
122 n = len(matrix)
123 sanitised_message = sanitise(message_letters)
124 if len(sanitised_message) % n != 0:
125 padding = fillvalue[0] * (n - len(sanitised_message) % n)
126 else:
127 padding = ''
128 message = [pos(c) for c in sanitised_message + padding]
129 message_chunks = [message[i:i+n] for i in range(0, len(message), n)]
130 # message_chunks = chunks(message, len(matrix), fillvalue=None)
131 enciphered_chunks = [((matrix * np.matrix(c).T).T).tolist()[0]
132 for c in message_chunks]
133 return cat([unpos(round(l))
134 for l in sum(enciphered_chunks, [])])
135
136 def hill_decipher(matrix, message, fillvalue='a'):
137 """Hill cipher
138
139 >>> hill_decipher(np.matrix([[7,8], [11,11]]), 'drjiqzdrvx')
140 'hellothere'
141 >>> hill_decipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
142 'tfjflpznvyac')
143 'hellothereaa'
144 """
145 adjoint = linalg.det(matrix)*linalg.inv(matrix)
146 inverse_determinant = modular_division_table[int(round(linalg.det(matrix))) % 26][1]
147 inverse_matrix = (inverse_determinant * adjoint) % 26
148 return hill_encipher(inverse_matrix, message, fillvalue)
149
150
151 # Where each piece of text ends up in the AMSCO transpositon cipher.
152 # 'index' shows where the slice appears in the plaintext, with the slice
153 # from 'start' to 'end'
154 AmscoSlice = collections.namedtuple('AmscoSlice', ['index', 'start', 'end'])
155
156 class AmscoFillStyle(Enum):
157 continuous = 1
158 same_each_row = 2
159 reverse_each_row = 3
160
161 def amsco_transposition_positions(message, keyword,
162 fillpattern=(1, 2),
163 fillstyle=AmscoFillStyle.continuous,
164 fillcolumnwise=False,
165 emptycolumnwise=True):
166 """Creates the grid for the AMSCO transposition cipher. Each element in the
167 grid shows the index of that slice and the start and end positions of the
168 plaintext that go to make it up.
169
170 >>> amsco_transposition_positions(string.ascii_lowercase, 'freddy', \
171 fillpattern=(1, 2)) # doctest: +NORMALIZE_WHITESPACE
172 [[AmscoSlice(index=3, start=4, end=6),
173 AmscoSlice(index=2, start=3, end=4),
174 AmscoSlice(index=0, start=0, end=1),
175 AmscoSlice(index=1, start=1, end=3),
176 AmscoSlice(index=4, start=6, end=7)],
177 [AmscoSlice(index=8, start=12, end=13),
178 AmscoSlice(index=7, start=10, end=12),
179 AmscoSlice(index=5, start=7, end=9),
180 AmscoSlice(index=6, start=9, end=10),
181 AmscoSlice(index=9, start=13, end=15)],
182 [AmscoSlice(index=13, start=19, end=21),
183 AmscoSlice(index=12, start=18, end=19),
184 AmscoSlice(index=10, start=15, end=16),
185 AmscoSlice(index=11, start=16, end=18),
186 AmscoSlice(index=14, start=21, end=22)],
187 [AmscoSlice(index=18, start=27, end=28),
188 AmscoSlice(index=17, start=25, end=27),
189 AmscoSlice(index=15, start=22, end=24),
190 AmscoSlice(index=16, start=24, end=25),
191 AmscoSlice(index=19, start=28, end=30)]]
192 """
193 transpositions = transpositions_of(keyword)
194 fill_iterator = cycle(fillpattern)
195 indices = count()
196 message_length = len(message)
197
198 current_position = 0
199 grid = []
200 current_fillpattern = fillpattern
201 while current_position < message_length:
202 row = []
203 if fillstyle == AmscoFillStyle.same_each_row:
204 fill_iterator = cycle(fillpattern)
205 if fillstyle == AmscoFillStyle.reverse_each_row:
206 fill_iterator = cycle(current_fillpattern)
207 for _ in range(len(transpositions)):
208 index = next(indices)
209 gap = next(fill_iterator)
210 row += [AmscoSlice(index, current_position, current_position + gap)]
211 current_position += gap
212 grid += [row]
213 if fillstyle == AmscoFillStyle.reverse_each_row:
214 current_fillpattern = list(reversed(current_fillpattern))
215 return [transpose(r, transpositions) for r in grid]
216
217 def amsco_transposition_encipher(message, keyword,
218 fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
219 """AMSCO transposition encipher.
220
221 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(1, 2))
222 'hoteelhler'
223 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(2, 1))
224 'hetelhelor'
225 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(1, 2))
226 'hotelerelh'
227 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(2, 1))
228 'hetelorlhe'
229 >>> amsco_transposition_encipher('hereissometexttoencipher', 'encode')
230 'etecstthhomoerereenisxip'
231 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2))
232 'hetcsoeisterereipexthomn'
233 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
234 'hecsoisttererteipexhomen'
235 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(2, 1))
236 'heecisoosttrrtepeixhemen'
237 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2))
238 'hxtomephescieretoeisnter'
239 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
240 'hxomeiphscerettoisenteer'
241 """
242 grid = amsco_transposition_positions(message, keyword,
243 fillpattern=fillpattern, fillstyle=fillstyle)
244 ct_as_grid = [[message[s.start:s.end] for s in r] for r in grid]
245 return combine_every_nth(ct_as_grid)
246
247
248 def amsco_transposition_decipher(message, keyword,
249 fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
250 """AMSCO transposition decipher
251
252 >>> amsco_transposition_decipher('hoteelhler', 'abc', fillpattern=(1, 2))
253 'hellothere'
254 >>> amsco_transposition_decipher('hetelhelor', 'abc', fillpattern=(2, 1))
255 'hellothere'
256 >>> amsco_transposition_decipher('hotelerelh', 'acb', fillpattern=(1, 2))
257 'hellothere'
258 >>> amsco_transposition_decipher('hetelorlhe', 'acb', fillpattern=(2, 1))
259 'hellothere'
260 >>> amsco_transposition_decipher('etecstthhomoerereenisxip', 'encode')
261 'hereissometexttoencipher'
262 >>> amsco_transposition_decipher('hetcsoeisterereipexthomn', 'cipher', fillpattern=(1, 2))
263 'hereissometexttoencipher'
264 >>> amsco_transposition_decipher('hecsoisttererteipexhomen', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
265 'hereissometexttoencipher'
266 >>> amsco_transposition_decipher('heecisoosttrrtepeixhemen', 'cipher', fillpattern=(2, 1))
267 'hereissometexttoencipher'
268 >>> amsco_transposition_decipher('hxtomephescieretoeisnter', 'cipher', fillpattern=(1, 3, 2))
269 'hereissometexttoencipher'
270 >>> amsco_transposition_decipher('hxomeiphscerettoisenteer', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
271 'hereissometexttoencipher'
272 """
273
274 grid = amsco_transposition_positions(message, keyword,
275 fillpattern=fillpattern, fillstyle=fillstyle)
276 transposed_sections = [s for c in [l for l in zip(*grid)] for s in c]
277 plaintext_list = [''] * len(transposed_sections)
278 current_pos = 0
279 for slice in transposed_sections:
280 plaintext_list[slice.index] = message[current_pos:current_pos-slice.start+slice.end][:len(message[slice.start:slice.end])]
281 current_pos += len(message[slice.start:slice.end])
282 return cat(plaintext_list)
283
284
285 def bifid_grid(keyword, wrap_alphabet, letter_mapping):
286 """Create the grids for a Bifid cipher
287 """
288 cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
289 if letter_mapping is None:
290 letter_mapping = {'j': 'i'}
291 translation = ''.maketrans(letter_mapping)
292 cipher_alphabet = cat(collections.OrderedDict.fromkeys(cipher_alphabet.translate(translation)))
293 f_grid = {k: ((i // 5) + 1, (i % 5) + 1)
294 for i, k in enumerate(cipher_alphabet)}
295 r_grid = {((i // 5) + 1, (i % 5) + 1): k
296 for i, k in enumerate(cipher_alphabet)}
297 return translation, f_grid, r_grid
298
299 def bifid_encipher(message, keyword, wrap_alphabet=KeywordWrapAlphabet.from_a,
300 letter_mapping=None, period=None, fillvalue=None):
301 """Bifid cipher
302
303 >>> bifid_encipher("indiajelly", 'iguana')
304 'ibidonhprm'
305 >>> bifid_encipher("indiacurry", 'iguana', period=4)
306 'ibnhgaqltm'
307 >>> bifid_encipher("indiacurry", 'iguana', period=4, fillvalue='x')
308 'ibnhgaqltzml'
309 """
310 translation, f_grid, r_grid = bifid_grid(keyword, wrap_alphabet, letter_mapping)
311
312 t_message = message.translate(translation)
313 pairs0 = [f_grid[l] for l in sanitise(t_message)]
314 if period:
315 chunked_pairs = [pairs0[i:i+period] for i in range(0, len(pairs0), period)]
316 if len(chunked_pairs[-1]) < period and fillvalue:
317 chunked_pairs[-1] += [f_grid[fillvalue]] * (period - len(chunked_pairs[-1]))
318 else:
319 chunked_pairs = [pairs0]
320
321 pairs1 = []
322 for c in chunked_pairs:
323 items = sum(list(list(i) for i in zip(*c)), [])
324 p = [(items[i], items[i+1]) for i in range(0, len(items), 2)]
325 pairs1 += p
326
327 return cat(r_grid[p] for p in pairs1)
328
329
330 def bifid_decipher(message, keyword, wrap_alphabet=KeywordWrapAlphabet.from_a,
331 letter_mapping=None, period=None, fillvalue=None):
332 """Decipher with bifid cipher
333
334 >>> bifid_decipher('ibidonhprm', 'iguana')
335 'indiaielly'
336 >>> bifid_decipher("ibnhgaqltm", 'iguana', period=4)
337 'indiacurry'
338 >>> bifid_decipher("ibnhgaqltzml", 'iguana', period=4)
339 'indiacurryxx'
340 """
341 translation, f_grid, r_grid = bifid_grid(keyword, wrap_alphabet, letter_mapping)
342
343 t_message = message.translate(translation)
344 pairs0 = [f_grid[l] for l in sanitise(t_message)]
345 if period:
346 chunked_pairs = [pairs0[i:i+period] for i in range(0, len(pairs0), period)]
347 if len(chunked_pairs[-1]) < period and fillvalue:
348 chunked_pairs[-1] += [f_grid[fillvalue]] * (period - len(chunked_pairs[-1]))
349 else:
350 chunked_pairs = [pairs0]
351
352 pairs1 = []
353 for c in chunked_pairs:
354 items = [j for i in c for j in i]
355 gap = len(c)
356 p = [(items[i], items[i+gap]) for i in range(gap)]
357 pairs1 += p
358
359 return cat(r_grid[p] for p in pairs1)
360
361
362 def autokey_encipher(message, keyword):
363 """Encipher with the autokey cipher
364
365 >>> autokey_encipher('meetatthefountain', 'kilt')
366 'wmpmmxxaeyhbryoca'
367 """
368 shifts = [pos(l) for l in keyword + message]
369 pairs = zip(message, shifts)
370 return cat([caesar_encipher_letter(l, k) for l, k in pairs])
371
372 def autokey_decipher(ciphertext, keyword):
373 """Decipher with the autokey cipher
374
375 >>> autokey_decipher('wmpmmxxaeyhbryoca', 'kilt')
376 'meetatthefountain'
377 """
378 plaintext = []
379 keys = list(keyword)
380 for c in ciphertext:
381 plaintext_letter = caesar_decipher_letter(c, pos(keys[0]))
382 plaintext += [plaintext_letter]
383 keys = keys[1:] + [plaintext_letter]
384 return cat(plaintext)
385
386
387 class PocketEnigma(object):
388 """A pocket enigma machine
389 The wheel is internally represented as a 26-element list self.wheel_map,
390 where wheel_map[i] == j shows that the position i places on from the arrow
391 maps to the position j places on.
392 """
393 def __init__(self, wheel=1, position='a'):
394 """initialise the pocket enigma, including which wheel to use and the
395 starting position of the wheel.
396
397 The wheel is either 1 or 2 (the predefined wheels) or a list of letter
398 pairs.
399
400 The position is the letter pointed to by the arrow on the wheel.
401
402 >>> pe.wheel_map
403 [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]
404 >>> pe.position
405 0
406 """
407 self.wheel1 = [('a', 'z'), ('b', 'e'), ('c', 'x'), ('d', 'k'),
408 ('f', 'h'), ('g', 'j'), ('i', 'm'), ('l', 'r'), ('n', 'o'),
409 ('p', 'v'), ('q', 't'), ('s', 'u'), ('w', 'y')]
410 self.wheel2 = [('a', 'c'), ('b', 'd'), ('e', 'w'), ('f', 'i'),
411 ('g', 'p'), ('h', 'm'), ('j', 'k'), ('l', 'n'), ('o', 'q'),
412 ('r', 'z'), ('s', 'u'), ('t', 'v'), ('x', 'y')]
413 if wheel == 1:
414 self.make_wheel_map(self.wheel1)
415 elif wheel == 2:
416 self.make_wheel_map(self.wheel2)
417 else:
418 self.validate_wheel_spec(wheel)
419 self.make_wheel_map(wheel)
420 if position in string.ascii_lowercase:
421 self.position = pos(position)
422 else:
423 self.position = position
424
425 def make_wheel_map(self, wheel_spec):
426 """Expands a wheel specification from a list of letter-letter pairs
427 into a full wheel_map.
428
429 >>> pe.make_wheel_map(pe.wheel2)
430 [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]
431 """
432 self.validate_wheel_spec(wheel_spec)
433 self.wheel_map = [0] * 26
434 for p in wheel_spec:
435 self.wheel_map[pos(p[0])] = pos(p[1])
436 self.wheel_map[pos(p[1])] = pos(p[0])
437 return self.wheel_map
438
439 def validate_wheel_spec(self, wheel_spec):
440 """Validates that a wheel specificaiton will turn into a valid wheel
441 map.
442
443 >>> pe.validate_wheel_spec([])
444 Traceback (most recent call last):
445 ...
446 ValueError: Wheel specification has 0 pairs, requires 13
447 >>> pe.validate_wheel_spec([('a', 'b', 'c')]*13)
448 Traceback (most recent call last):
449 ...
450 ValueError: Not all mappings in wheel specificationhave two elements
451 >>> pe.validate_wheel_spec([('a', 'b')]*13)
452 Traceback (most recent call last):
453 ...
454 ValueError: Wheel specification does not contain 26 letters
455 """
456 if len(wheel_spec) != 13:
457 raise ValueError("Wheel specification has {} pairs, requires 13".
458 format(len(wheel_spec)))
459 for p in wheel_spec:
460 if len(p) != 2:
461 raise ValueError("Not all mappings in wheel specification"
462 "have two elements")
463 if len(set([p[0] for p in wheel_spec] +
464 [p[1] for p in wheel_spec])) != 26:
465 raise ValueError("Wheel specification does not contain 26 letters")
466
467 def encipher_letter(self, letter):
468 """Enciphers a single letter, by advancing the wheel before looking up
469 the letter on the wheel.
470
471 >>> pe.set_position('f')
472 5
473 >>> pe.encipher_letter('k')
474 'h'
475 """
476 self.advance()
477 return self.lookup(letter)
478 decipher_letter = encipher_letter
479
480 def lookup(self, letter):
481 """Look up what a letter enciphers to, without turning the wheel.
482
483 >>> pe.set_position('f')
484 5
485 >>> cat([pe.lookup(l) for l in string.ascii_lowercase])
486 'udhbfejcpgmokrliwntsayqzvx'
487 >>> pe.lookup('A')
488 ''
489 """
490 if letter in string.ascii_lowercase:
491 return unpos(
492 (self.wheel_map[(pos(letter) - self.position) % 26] +
493 self.position))
494 else:
495 return ''
496
497 def advance(self):
498 """Advances the wheel one position.
499
500 >>> pe.set_position('f')
501 5
502 >>> pe.advance()
503 6
504 """
505 self.position = (self.position + 1) % 26
506 return self.position
507
508 def encipher(self, message, starting_position=None):
509 """Enciphers a whole message.
510
511 >>> pe.set_position('f')
512 5
513 >>> pe.encipher('helloworld')
514 'kjsglcjoqc'
515 >>> pe.set_position('f')
516 5
517 >>> pe.encipher('kjsglcjoqc')
518 'helloworld'
519 >>> pe.encipher('helloworld', starting_position = 'x')
520 'egrekthnnf'
521 """
522 if starting_position:
523 self.set_position(starting_position)
524 transformed = ''
525 for l in message:
526 transformed += self.encipher_letter(l)
527 return transformed
528 decipher = encipher
529
530 def set_position(self, position):
531 """Sets the position of the wheel, by specifying the letter the arrow
532 points to.
533
534 >>> pe.set_position('a')
535 0
536 >>> pe.set_position('m')
537 12
538 >>> pe.set_position('z')
539 25
540 """
541 self.position = pos(position)
542 return self.position
543
544
545 if __name__ == "__main__":
546 import doctest
547 doctest.testmod(extraglobs={'pe': PocketEnigma(1, 'a')})