3 from itertools
import chain
4 from support
.utilities
import *
5 from support
.language_models
import *
7 from logger
import logger
9 def transpositions_of(keyword
):
10 """Finds the transpostions given by a keyword. For instance, the keyword
11 'clever' rearranges to 'celrv', so the first column (0) stays first, the
12 second column (1) moves to third, the third column (2) moves to second,
15 If passed a tuple, assume it's already a transposition and just return it.
17 >>> transpositions_of('clever')
19 >>> transpositions_of('fred')
21 >>> transpositions_of((3, 2, 0, 1))
24 if isinstance(keyword
, tuple):
27 key
= deduplicate(keyword
)
28 transpositions
= tuple(key
.index(l
) for l
in sorted(key
))
32 transpositions
= collections
.defaultdict(list)
34 transpositions
[transpositions_of(word
)] += [word
]
37 def pad(message_len
, group_len
, fillvalue
):
38 padding_length
= group_len
- message_len
% group_len
39 if padding_length
== group_len
: padding_length
= 0
41 for i
in range(padding_length
):
42 if callable(fillvalue
):
43 padding
+= fillvalue()
48 def column_transposition_encipher(message
, keyword
, fillvalue
=' ',
50 emptycolumnwise
=False):
51 """Enciphers using the column transposition cipher.
52 Message is padded to allow all rows to be the same length.
54 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
56 >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
58 >>> column_transposition_encipher('hellothere', 'abcdef')
60 >>> column_transposition_encipher('hellothere', 'abcde')
62 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
64 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
66 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
68 >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
70 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
72 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
74 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
76 >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
78 >>> column_transposition_encipher('hellothere', 'cleverly')
80 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
82 >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
85 transpositions
= transpositions_of(keyword
)
86 message
+= pad(len(message
), len(transpositions
), fillvalue
)
88 rows
= every_nth(message
, len(message
) // len(transpositions
))
90 rows
= chunks(message
, len(transpositions
))
91 transposed
= [transpose(r
, transpositions
) for r
in rows
]
93 return combine_every_nth(transposed
)
95 return cat(chain(*transposed
))
97 def column_transposition_decipher(message
, keyword
, fillvalue
=' ',
99 emptycolumnwise
=False):
100 """Deciphers using the column transposition cipher.
101 Message is padded to allow all rows to be the same length.
103 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
105 >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
107 >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
109 >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
111 >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
113 >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
115 >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
117 >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
120 transpositions
= transpositions_of(keyword
)
121 message
+= pad(len(message
), len(transpositions
), fillvalue
)
123 rows
= every_nth(message
, len(message
) // len(transpositions
))
125 rows
= chunks(message
, len(transpositions
))
126 untransposed
= [untranspose(r
, transpositions
) for r
in rows
]
128 return combine_every_nth(untransposed
)
130 return cat(chain(*untransposed
))
132 def scytale_encipher(message
, rows
, fillvalue
=' '):
133 """Enciphers using the scytale transposition cipher.
134 Message is padded with spaces to allow all rows to be the same length.
136 >>> scytale_encipher('thequickbrownfox', 3)
138 >>> scytale_encipher('thequickbrownfox', 4)
140 >>> scytale_encipher('thequickbrownfox', 5)
141 'tubn hirf ecoo qkwx '
142 >>> scytale_encipher('thequickbrownfox', 6)
144 >>> scytale_encipher('thequickbrownfox', 7)
145 'tqcrnx hukof eibwo '
147 # transpositions = [i for i in range(math.ceil(len(message) / rows))]
148 # return column_transposition_encipher(message, transpositions,
149 # fillvalue=fillvalue, fillcolumnwise=False, emptycolumnwise=True)
150 transpositions
= [i
for i
in range(rows
)]
151 return column_transposition_encipher(message
, transpositions
,
152 fillvalue
=fillvalue
, fillcolumnwise
=True, emptycolumnwise
=False)
154 def scytale_decipher(message
, rows
):
155 """Deciphers using the scytale transposition cipher.
156 Assumes the message is padded so that all rows are the same length.
158 >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
160 >>> scytale_decipher('tubnhirfecooqkwx', 4)
162 >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
164 >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
166 >>> scytale_decipher('tqcrnx hukof eibwo ', 7)
169 # transpositions = [i for i in range(math.ceil(len(message) / rows))]
170 # return column_transposition_decipher(message, transpositions,
171 # fillcolumnwise=False, emptycolumnwise=True)
172 transpositions
= [i
for i
in range(rows
)]
173 return column_transposition_decipher(message
, transpositions
,
174 fillcolumnwise
=True, emptycolumnwise
=False)
177 def column_transposition_break_mp(message
, translist
=transpositions
,
178 fitness
=Pbigrams
, chunksize
=500):
179 """Breaks a column transposition cipher using a dictionary and
180 n-gram frequency analysis
182 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
183 "It is a truth universally acknowledged, that a single man in \
184 possession of a good fortune, must be in want of a wife. However \
185 little known the feelings or views of such a man may be on his \
186 first entering a neighbourhood, this truth is so well fixed in \
187 the minds of the surrounding families, that he is considered the \
188 rightful property of some one or other of their daughters."), \
190 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
191 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
192 (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
193 (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
194 >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
195 "It is a truth universally acknowledged, that a single man in \
196 possession of a good fortune, must be in want of a wife. However \
197 little known the feelings or views of such a man may be on his \
198 first entering a neighbourhood, this truth is so well fixed in \
199 the minds of the surrounding families, that he is considered the \
200 rightful property of some one or other of their daughters."), \
202 translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
203 (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
204 (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
205 fitness=Ptrigrams) # doctest: +ELLIPSIS
206 (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
208 with multiprocessing
.Pool() as pool
:
209 helper_args
= [(message
, trans
, fillcolumnwise
, emptycolumnwise
,
211 for trans
in translist
212 for fillcolumnwise
in [True, False]
213 for emptycolumnwise
in [True, False]]
214 # Gotcha: the helper function here needs to be defined at the top level
215 # (limitation of Pool.starmap)
216 breaks
= pool
.starmap(column_transposition_break_worker
,
217 helper_args
, chunksize
)
218 return max(breaks
, key
=lambda k
: k
[1])
219 column_transposition_break
= column_transposition_break_mp
221 def column_transposition_break_worker(message
, transposition
,
222 fillcolumnwise
, emptycolumnwise
, fitness
):
223 plaintext
= column_transposition_decipher(message
, transposition
,
224 fillcolumnwise
=fillcolumnwise
, emptycolumnwise
=emptycolumnwise
)
225 fit
= fitness(sanitise(plaintext
))
226 logger
.debug('Column transposition break attempt using key {0} '
227 'gives fit of {1} and decrypt starting: {2}'.format(
229 sanitise(plaintext
)[:50]))
230 return (transposition
, fillcolumnwise
, emptycolumnwise
), fit
233 def scytale_break_mp(message
, max_key_length
=20,
234 fitness
=Pbigrams
, chunksize
=500):
235 """Breaks a scytale cipher using a range of lengths and
236 n-gram frequency analysis
238 >>> scytale_break_mp(scytale_encipher(sanitise( \
239 "It is a truth universally acknowledged, that a single man in \
240 possession of a good fortune, must be in want of a wife. However \
241 little known the feelings or views of such a man may be on his \
242 first entering a neighbourhood, this truth is so well fixed in \
243 the minds of the surrounding families, that he is considered the \
244 rightful property of some one or other of their daughters."), \
245 5)) # doctest: +ELLIPSIS
247 >>> scytale_break_mp(scytale_encipher(sanitise( \
248 "It is a truth universally acknowledged, that a single man in \
249 possession of a good fortune, must be in want of a wife. However \
250 little known the feelings or views of such a man may be on his \
251 first entering a neighbourhood, this truth is so well fixed in \
252 the minds of the surrounding families, that he is considered the \
253 rightful property of some one or other of their daughters."), \
255 fitness=Ptrigrams) # doctest: +ELLIPSIS
258 with multiprocessing
.Pool() as pool
:
259 helper_args
= [(message
, trans
, False, True, fitness
)
261 [[col
for col
in range(math
.ceil(len(message
)/rows
))]
262 for rows
in range(1,max_key_length
+1)]]
263 # Gotcha: the helper function here needs to be defined at the top level
264 # (limitation of Pool.starmap)
265 breaks
= pool
.starmap(column_transposition_break_worker
,
266 helper_args
, chunksize
)
267 best
= max(breaks
, key
=lambda k
: k
[1])
268 return math
.trunc(len(message
) / len(best
[0][0])), best
[1]
269 scytale_break
= scytale_break_mp
271 if __name__
== "__main__":