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