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