e81b066809623dae8db28cd89d1e90132b122e83
[szyfrow.git] / railfence.py
1 import math
2 from enum import Enum
3 from itertools import starmap, zip_longest
4 from szyfrow.support.utilities import *
5 from szyfrow.support.language_models import *
6
7
8 def railfence_encipher(message, height, fillvalue=''):
9 """Railfence cipher.
10 Works by splitting the text into sections, then reading across them to
11 generate the rows in the cipher. The rows are then combined to form the
12 ciphertext.
13
14 Example: the plaintext "hellotherefriends", with a height of four, written
15 out in the railfence as
16 h h i
17 etere*
18 lorfns
19 l e d
20 (with the * showing the one character to finish the last section).
21 Each 'section' is two columns, but unfolded. In the example, the first
22 section is 'hellot'.
23
24 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 2, fillvalue='!')
25 'hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!'
26 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3, fillvalue='!')
27 'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!'
28 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5, fillvalue='!')
29 'hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!'
30 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 10, fillvalue='!')
31 'hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!'
32 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3)
33 'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece'
34 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5)
35 'hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp'
36 >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 7)
37 'haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic'
38 """
39 sections = chunks(message, (height - 1) * 2, fillvalue=fillvalue)
40 n_sections = len(sections)
41 # Add the top row
42 rows = [cat([s[0] for s in sections])]
43 # process the middle rows of the grid
44 for r in range(1, height-1):
45 rows += [cat([s[r:r+1] + s[height*2-r-2:height*2-r-1] for s in sections])]
46 # process the bottom row
47 rows += [cat([s[height - 1:height] for s in sections])]
48 # rows += [wcat([s[height - 1] for s in sections])]
49 return cat(rows)
50
51 def railfence_decipher(message, height, fillvalue=''):
52 """Railfence decipher.
53 Works by reconstructing the grid used to generate the ciphertext, then
54 unfolding the sections so the text can be concatenated together.
55
56 Example: given the ciphertext 'hhieterelorfnsled' and a height of 4, first
57 work out that the second row has a character missing, find the rows of the
58 grid, then split the section into its two columns.
59
60 'hhieterelorfnsled' is split into
61 h h i
62 etere
63 lorfns
64 l e d
65 (spaces added for clarity), which is stored in 'rows'. This is then split
66 into 'down_rows' and 'up_rows':
67
68 down_rows:
69 hhi
70 eee
71 lrn
72 led
73
74 up_rows:
75 tr
76 ofs
77
78 These are then zipped together (after the up_rows are reversed) to recover
79 the plaintext.
80
81 Most of the procedure is about finding the correct lengths for each row then
82 splitting the ciphertext into those rows.
83
84 >>> railfence_decipher('hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!', 2).strip('!')
85 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
86 >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!', 3).strip('!')
87 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
88 >>> railfence_decipher('hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!', 5).strip('!')
89 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
90 >>> railfence_decipher('hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!', 10).strip('!')
91 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
92 >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece', 3)
93 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
94 >>> railfence_decipher('hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp', 5)
95 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
96 >>> railfence_decipher('haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic', 7)
97 'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
98 """
99 # find the number and size of the sections, including how many characters
100 # are missing for a full grid
101 n_sections = math.ceil(len(message) / ((height - 1) * 2))
102 padding_to_add = n_sections * (height - 1) * 2 - len(message)
103 # row_lengths are for the both up rows and down rows
104 row_lengths = [n_sections] * (height - 1) * 2
105 for i in range((height - 1) * 2 - 1, (height - 1) * 2 - (padding_to_add + 1), -1):
106 row_lengths[i] -= 1
107 # folded_rows are the combined row lengths in the middle of the railfence
108 folded_row_lengths = [row_lengths[0]]
109 for i in range(1, height-1):
110 folded_row_lengths += [row_lengths[i] + row_lengths[-i]]
111 folded_row_lengths += [row_lengths[height - 1]]
112 # find the rows that form the railfence grid
113 rows = []
114 row_start = 0
115 for i in folded_row_lengths:
116 rows += [message[row_start:row_start + i]]
117 row_start += i
118 # split the rows into the 'down_rows' (those that form the first column of
119 # a section) and the 'up_rows' (those that ofrm the second column of a
120 # section).
121 down_rows = [rows[0]]
122 up_rows = []
123 for i in range(1, height-1):
124 down_rows += [cat([c for n, c in enumerate(rows[i]) if n % 2 == 0])]
125 up_rows += [cat([c for n, c in enumerate(rows[i]) if n % 2 == 1])]
126 down_rows += [rows[-1]]
127 up_rows.reverse()
128 return cat(c for r in zip_longest(*(down_rows + up_rows), fillvalue='') for c in r)
129
130
131 def railfence_break(message, max_key_length=20,
132 fitness=Pletters, chunksize=500):
133 """Breaks a railfence cipher using a matrix of given rank and letter frequencies
134
135
136 """
137
138 sanitised_message = sanitise(message)
139 results = starmap(worker, [(sanitised_message, i, fitness)
140 for i in range(2, max_key_length+1)])
141 return max(results, key=lambda k: k[1])
142
143
144 def railfence_break(message, max_key_length=20,
145 fitness=Pbigrams, chunksize=500):
146 """Breaks a railfence cipher using a range of lengths and
147 n-gram frequency analysis
148
149 >>> railfence_break(railfence_encipher(sanitise( \
150 "It is a truth universally acknowledged, that a single man in \
151 possession of a good fortune, must be in want of a wife. However \
152 little known the feelings or views of such a man may be on his \
153 first entering a neighbourhood, this truth is so well fixed in \
154 the minds of the surrounding families, that he is considered the \
155 rightful property of some one or other of their daughters."), \
156 7)) # doctest: +ELLIPSIS
157 (7, -709.46467226...)
158 >>> railfence_break(railfence_encipher(sanitise( \
159 "It is a truth universally acknowledged, that a single man in \
160 possession of a good fortune, must be in want of a wife. However \
161 little known the feelings or views of such a man may be on his \
162 first entering a neighbourhood, this truth is so well fixed in \
163 the minds of the surrounding families, that he is considered the \
164 rightful property of some one or other of their daughters."), \
165 7), \
166 fitness=Ptrigrams) # doctest: +ELLIPSIS
167 (7, -997.0129085...)
168 """
169 def worker(message, height, fitness):
170 plaintext = railfence_decipher(message, height)
171 fit = fitness(plaintext)
172 return height, fit
173
174 sanitised_message = sanitise(message)
175 results = starmap(worker, [(sanitised_message, i, fitness)
176 for i in range(2, max_key_length+1)])
177 return max(results, key=lambda k: k[1])