Updated further work to include Enigma
[cipher-training.git] / slides / transposition-encipher.html
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <title>Transposition ciphers</title>
5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
6 <style type="text/css">
7 /* Slideshow styles */
8 body {
9 font-size: 20px;
10 }
11 h1, h2, h3 {
12 font-weight: 400;
13 margin-bottom: 0;
14 }
15 h1 { font-size: 3em; }
16 h2 { font-size: 2em; }
17 h3 { font-size: 1.6em; }
18 a, a > code {
19 text-decoration: none;
20 }
21 code {
22 -moz-border-radius: 5px;
23 -web-border-radius: 5px;
24 background: #e7e8e2;
25 border-radius: 5px;
26 font-size: 16px;
27 }
28 .plaintext {
29 background: #272822;
30 color: #80ff80;
31 text-shadow: 0 0 20px #333;
32 padding: 2px 5px;
33 }
34 .ciphertext {
35 background: #272822;
36 color: #ff6666;
37 text-shadow: 0 0 20px #333;
38 padding: 2px 5px;
39 }
40 .float-right {
41 float: right;
42 }
43 </style>
44 </head>
45 <body>
46 <textarea id="source">
47
48 # Transposition ciphers
49
50 attack the fort at dawn
51
52 a t t a c
53 k t h e f
54 o r t a t
55 d a w n
56
57 akod ttra aean cft
58
59 ---
60
61 # Transposition ciphers
62
63 Rather than changing symbols (substitution ciphers),
64
65 Rearrange them.
66
67 Still disguises the message.
68
69 (Good ciphers do both, and more.)
70
71 ---
72
73 # Scytale
74
75 Even older than Caesar cipher.
76
77 * Wrap a strip round a pole
78 * Write the message along it
79 * Unwind the strip
80 * "Unreadable" unless reader has pole of same diameter
81
82 ```
83 attack the fort at dawn
84
85 a t t a c
86 k t h e f
87 o r t a t
88 d a w n
89
90 akod ttra aean cft
91 ```
92
93 ---
94
95 # Generalising: column transposition ciphers
96
97 Scytale essentially fills a grid by rows, then reads it by columns
98
99 * (Deciphering is the reverse)
100
101 Column transposition ciphers:
102
103 * Fill a grid
104 * Reorder columns based on keyword
105 * Read the grid (perhaps different direction)
106
107 (Keyword = secret → cerst)
108 ```
109 attack the fort at dawn
110
111 s e c r t c e r s t
112 --------- ---------
113 a t t a c t t a a c
114 k t h e f h t e k f
115 o r t a t t r a o t
116 d a w n w a n d
117
118 ttaac htekf traot wand
119 thtw tra aean akod cft
120 ```
121
122 Scytale is just a special case of column transposition.
123
124 ---
125
126 # Grids and data structures
127
128 What operations do we need to do on a grid?
129
130 How to represent a grid?
131
132 ---
133
134 # Grids and data structures
135
136 What operations do we need to do on a grid?
137
138 * Fill, by rows or columns
139 * Empty, by rows or columns
140 * Rearrange columns
141 * Calculate the size of the grid
142 * Pad message to fit a rectangle of the required size
143
144 How to represent a grid?
145
146 * List of strings
147 * Each row is a string
148 * Rows in order in the list
149
150 ---
151
152 # Finding sizes
153
154 Know number of columns
155
156 Number of rows = `\(\left \lceil \frac{\mathrm{message\ length}}{\mathrm{columns}} \right \rceil\)`
157
158 Paddding is (rows ⨉ columns) - message length
159
160 * What to use as default padding?
161 * Keyword parameter!
162
163 ## Fit 'thequickbrownfox' (16 letters) into grid of
164
165 * 4 columns
166 * 5 columns
167
168 ---
169
170 # Fill and empty grid by rows
171
172 Split message into row-sized chunks
173
174 * slices and ranges
175
176 Append all the rows together
177
178 * `&lt;string&gt;.join()`
179
180 Keep thinking about test cases!
181
182 ---
183
184 # Fill and empty grid by columns
185
186 Idea: fill and empty by rows, with a transposition.
187
188 `zip(*rows)` and `itertools.zip_longest(*rows)`
189
190 ---
191
192 # Swapping columns
193
194 How to represent a transposition (_permutation_, to mathematicians)?
195
196 How to create it from a keyword?
197
198 ---
199
200 # Idea of a transposition
201
202 Says, for each element, where it should go
203
204 ```
205 0 1 2 3 4 5 6
206 t r e a s o n
207
208 a e n o r s t
209 3 2 6 5 1 4 0
210 ```
211
212 The transposition `(3, 2, 6, 5, 1, 4, 0)` says that what was in position 3 moves to position 0, what was in position 2 moves to position 1, what was in position 6 moves to position 2, ...
213
214 `enumerate(_iterable_)` yields an iterator that walks over the iterable, including the element indexes.
215
216 ```python
217 >>> [i for i in enumerate('treason')]
218 [(0, 't'), (1, 'r'), (2, 'e'), (3, 'a'), (4, 's'), (5, 'o'), (6, 'n')]
219 >>> [i for i in enumerate((3, 2, 6, 5, 1, 4, 0))]
220 [(0, 3), (1, 2), (2, 6), (3, 5), (4, 1), (5, 4), (6, 0)]
221 ```
222
223 Write the `transpose` and `untranspose` functions.
224
225 ---
226
227 # Transposition from a keyword
228
229 Deduplicate the keyword
230
231 Sort it
232
233 Use `&lt;iterable&gt;.index()` to find the positions of the letters in the sorted keyword
234
235 ---
236
237 # Transposition ciphers
238
239 Put it all together
240
241 ---
242
243 # Back to the scytale
244
245 Key is number of rows.
246
247 No transposition of columns.
248
249 * What does a null transposition look like?
250
251 How to fill and empty?
252
253 (Transposing the grid is easier)
254
255 ---
256
257 # Masking the fill characters
258
259 Padding characters can be distinctive.
260
261 Make a function that generates a random letter, based on the `normalised_english_counts`
262
263 Use `callable()` to check if the `fillvalue` should be called or just inserted
264
265 </textarea>
266 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
267 </script>
268
269 <script type="text/javascript"
270 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
271
272 <script type="text/javascript">
273 var slideshow = remark.create({ ratio: "16:9" });
274
275 // Setup MathJax
276 MathJax.Hub.Config({
277 tex2jax: {
278 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
279 }
280 });
281 MathJax.Hub.Queue(function() {
282 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
283 return(elem.SourceElement());
284 }).parent().addClass('has-jax');
285 });
286 MathJax.Hub.Configured();
287 </script>
288 </body>
289 </html>