48ab30627b7c46f472b526a2fcbd4cfbe3c05b6c
[szyfrow.git] / amsco.py
1 from enum import Enum
2 import multiprocessing
3 import itertools
4
5 from szyfrow.support.utilities import *
6 from szyfrow.support.language_models import *
7 from szyfrow.column_transposition import transpositions, transpositions_of
8
9 # Where each piece of text ends up in the AMSCO transpositon cipher.
10 # 'index' shows where the slice appears in the plaintext, with the slice
11 # from 'start' to 'end'
12 AmscoSlice = collections.namedtuple('AmscoSlice', ['index', 'start', 'end'])
13
14 class AmscoFillStyle(Enum):
15 continuous = 1
16 same_each_row = 2
17 reverse_each_row = 3
18
19 def amsco_transposition_positions(message, keyword,
20 fillpattern=(1, 2),
21 fillstyle=AmscoFillStyle.continuous,
22 fillcolumnwise=False,
23 emptycolumnwise=True):
24 """Creates the grid for the AMSCO transposition cipher. Each element in the
25 grid shows the index of that slice and the start and end positions of the
26 plaintext that go to make it up.
27
28 >>> amsco_transposition_positions(string.ascii_lowercase, 'freddy', \
29 fillpattern=(1, 2)) # doctest: +NORMALIZE_WHITESPACE
30 [[AmscoSlice(index=3, start=4, end=6),
31 AmscoSlice(index=2, start=3, end=4),
32 AmscoSlice(index=0, start=0, end=1),
33 AmscoSlice(index=1, start=1, end=3),
34 AmscoSlice(index=4, start=6, end=7)],
35 [AmscoSlice(index=8, start=12, end=13),
36 AmscoSlice(index=7, start=10, end=12),
37 AmscoSlice(index=5, start=7, end=9),
38 AmscoSlice(index=6, start=9, end=10),
39 AmscoSlice(index=9, start=13, end=15)],
40 [AmscoSlice(index=13, start=19, end=21),
41 AmscoSlice(index=12, start=18, end=19),
42 AmscoSlice(index=10, start=15, end=16),
43 AmscoSlice(index=11, start=16, end=18),
44 AmscoSlice(index=14, start=21, end=22)],
45 [AmscoSlice(index=18, start=27, end=28),
46 AmscoSlice(index=17, start=25, end=27),
47 AmscoSlice(index=15, start=22, end=24),
48 AmscoSlice(index=16, start=24, end=25),
49 AmscoSlice(index=19, start=28, end=30)]]
50 """
51 transpositions = transpositions_of(keyword)
52 fill_iterator = itertools.cycle(fillpattern)
53 indices = itertools.count()
54 message_length = len(message)
55
56 current_position = 0
57 grid = []
58 current_fillpattern = fillpattern
59 while current_position < message_length:
60 row = []
61 if fillstyle == AmscoFillStyle.same_each_row:
62 fill_iterator = itertools.cycle(fillpattern)
63 if fillstyle == AmscoFillStyle.reverse_each_row:
64 fill_iterator = itertools.cycle(current_fillpattern)
65 for _ in range(len(transpositions)):
66 index = next(indices)
67 gap = next(fill_iterator)
68 row += [AmscoSlice(index, current_position, current_position + gap)]
69 current_position += gap
70 grid += [row]
71 if fillstyle == AmscoFillStyle.reverse_each_row:
72 current_fillpattern = list(reversed(current_fillpattern))
73 return [transpose(r, transpositions) for r in grid]
74
75 def amsco_transposition_encipher(message, keyword,
76 fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
77 """AMSCO transposition encipher.
78
79 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(1, 2))
80 'hoteelhler'
81 >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(2, 1))
82 'hetelhelor'
83 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(1, 2))
84 'hotelerelh'
85 >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(2, 1))
86 'hetelorlhe'
87 >>> amsco_transposition_encipher('hereissometexttoencipher', 'encode')
88 'etecstthhomoerereenisxip'
89 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2))
90 'hetcsoeisterereipexthomn'
91 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
92 'hecsoisttererteipexhomen'
93 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(2, 1))
94 'heecisoosttrrtepeixhemen'
95 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2))
96 'hxtomephescieretoeisnter'
97 >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
98 'hxomeiphscerettoisenteer'
99 """
100 grid = amsco_transposition_positions(message, keyword,
101 fillpattern=fillpattern, fillstyle=fillstyle)
102 ct_as_grid = [[message[s.start:s.end] for s in r] for r in grid]
103 return combine_every_nth(ct_as_grid)
104
105
106 def amsco_transposition_decipher(message, keyword,
107 fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
108 """AMSCO transposition decipher
109
110 >>> amsco_transposition_decipher('hoteelhler', 'abc', fillpattern=(1, 2))
111 'hellothere'
112 >>> amsco_transposition_decipher('hetelhelor', 'abc', fillpattern=(2, 1))
113 'hellothere'
114 >>> amsco_transposition_decipher('hotelerelh', 'acb', fillpattern=(1, 2))
115 'hellothere'
116 >>> amsco_transposition_decipher('hetelorlhe', 'acb', fillpattern=(2, 1))
117 'hellothere'
118 >>> amsco_transposition_decipher('etecstthhomoerereenisxip', 'encode')
119 'hereissometexttoencipher'
120 >>> amsco_transposition_decipher('hetcsoeisterereipexthomn', 'cipher', fillpattern=(1, 2))
121 'hereissometexttoencipher'
122 >>> amsco_transposition_decipher('hecsoisttererteipexhomen', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
123 'hereissometexttoencipher'
124 >>> amsco_transposition_decipher('heecisoosttrrtepeixhemen', 'cipher', fillpattern=(2, 1))
125 'hereissometexttoencipher'
126 >>> amsco_transposition_decipher('hxtomephescieretoeisnter', 'cipher', fillpattern=(1, 3, 2))
127 'hereissometexttoencipher'
128 >>> amsco_transposition_decipher('hxomeiphscerettoisenteer', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
129 'hereissometexttoencipher'
130 """
131
132 grid = amsco_transposition_positions(message, keyword,
133 fillpattern=fillpattern, fillstyle=fillstyle)
134 transposed_sections = [s for c in [l for l in zip(*grid)] for s in c]
135 plaintext_list = [''] * len(transposed_sections)
136 current_pos = 0
137 for slice in transposed_sections:
138 plaintext_list[slice.index] = message[current_pos:current_pos-slice.start+slice.end][:len(message[slice.start:slice.end])]
139 current_pos += len(message[slice.start:slice.end])
140 return cat(plaintext_list)
141
142
143 def amsco_break(message, translist=transpositions, patterns = [(1, 2), (2, 1)],
144 fillstyles = [AmscoFillStyle.continuous,
145 AmscoFillStyle.same_each_row,
146 AmscoFillStyle.reverse_each_row],
147 fitness=Pbigrams,
148 chunksize=500):
149 """Breaks an AMSCO transposition cipher using a dictionary and
150 n-gram frequency analysis
151
152 >>> amsco_break(amsco_transposition_encipher(sanitise( \
153 "It is a truth universally acknowledged, that a single man in \
154 possession of a good fortune, must be in want of a wife. However \
155 little known the feelings or views of such a man may be on his \
156 first entering a neighbourhood, this truth is so well fixed in \
157 the minds of the surrounding families, that he is considered the \
158 rightful property of some one or other of their daughters."), \
159 'encipher'), \
160 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
161 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
162 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
163 patterns=[(1, 2)]) # doctest: +ELLIPSIS
164 (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
165 >>> amsco_break(amsco_transposition_encipher(sanitise( \
166 "It is a truth universally acknowledged, that a single man in \
167 possession of a good fortune, must be in want of a wife. However \
168 little known the feelings or views of such a man may be on his \
169 first entering a neighbourhood, this truth is so well fixed in \
170 the minds of the surrounding families, that he is considered the \
171 rightful property of some one or other of their daughters."), \
172 'encipher', fillpattern=(2, 1)), \
173 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
174 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
175 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
176 patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
177 (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
178 """
179 with multiprocessing.Pool() as pool:
180 helper_args = [(message, trans, pattern, fillstyle, fitness)
181 for trans in translist
182 for pattern in patterns
183 for fillstyle in fillstyles]
184 # Gotcha: the helper function here needs to be defined at the top level
185 # (limitation of Pool.starmap)
186 breaks = pool.starmap(amsco_break_worker, helper_args, chunksize)
187 return max(breaks, key=lambda k: k[1])
188
189 def amsco_break_worker(message, transposition,
190 pattern, fillstyle, fitness):
191 plaintext = amsco_transposition_decipher(message, transposition,
192 fillpattern=pattern, fillstyle=fillstyle)
193 fit = fitness(sanitise(plaintext))
194 return (transposition, pattern, fillstyle), fit
195
196 if __name__ == "__main__":
197 import doctest