Added transposition cipher slides
[cipher-training.git] / slides / transposition-encipher.html
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <title>Keyword 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 attack the fort at dawn
83
84 a t t a c
85 k t h e f
86 o r t a t
87 d a w n
88
89 akod ttra aean cft
90
91 ---
92
93 # Generalising: column transposition ciphers
94
95 Scytale essentially fills a grid by rows, then reads it by columns
96
97 * (Deciphering is the reverse)
98
99 Column transposition ciphers:
100
101 * Fill a grid
102 * Reorder columns based on keyword
103 * Read the grid (perhaps different direction)
104
105 Scytale is just a special case of column transposition.
106
107 ---
108
109 # Grids and data structures
110
111 How to represent a grid?
112
113 What operations do we need to do on it?
114
115 ---
116
117 # Grids and data structures
118
119 How to represent a grid?
120
121 * List of strings
122 * Each row is a string
123 * Rows in order in the list
124
125 What operations do we need to do on it?
126
127 * Fill, by rows or columns
128 * Empty, by rows or columns
129 * Rearrange columns
130 * Calculate the size of the grid
131 * Pad message to fit a rectangle of the required size
132
133 ---
134
135 # Finding sizes
136
137 Know number of columns
138
139 Number of rows = ceiling(message length / columns)
140
141 Paddding is (rows * columns) - message length
142
143 * What to use as default padding?
144 * Keyword parameter!
145
146 ## Fit 'thequickbrownfox' (16 letters) into grid of
147
148 * 4 columns
149 * 5 columns
150
151 ---
152
153 # Fill and empty grid by rows
154
155 Split message into row-sized chunks
156
157 * slices and ranges
158
159 Append all the rows together
160
161 * `&lt;string&gt;.join()`
162
163 Keep thinking about test cases!
164
165 ---
166
167 # Fill and empty grid by columns
168
169 Idea: fill and empty by rows, with a transposition.
170
171 `zip(*rows)` and `itertools.zip_longest(*rows)`
172
173 ---
174
175 # Swapping columns
176
177 How to represent a transposition (_permutation_, to mathematicians)?
178
179 How to create it from a keyword?
180
181 ---
182
183 # Idea of a transposition
184
185 Says, for each element, where it should go
186
187 ```
188 0 1 2 3 4 5 6
189 t r e a s o n
190
191 a e n o r s t
192 3 2 6 5 1 4 0
193 ```
194
195 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, ...
196
197 `enumerate(_iterable_)` yields an iterator that walks over the iterator, including the element indexes.
198
199 ```python
200 >>> [i for i in enumerate('treason')]
201 [(0, 't'), (1, 'r'), (2, 'e'), (3, 'a'), (4, 's'), (5, 'o'), (6, 'n')]
202 >>> [i for i in enumerate((3, 2, 6, 5, 1, 4, 0))]
203 [(0, 3), (1, 2), (2, 6), (3, 5), (4, 1), (5, 4), (6, 0)]
204 ```
205
206 Write the `transpose` and `untranspose` functions.
207
208 ---
209
210 # Transposition from a keyword
211
212 Deduplicate the keyword
213
214 Sort it
215
216 Use `&lt;iterable&gt;.index()` to find the positions of the letters in the sorted keyword
217
218 ---
219
220 # Transposition ciphers
221
222 Put it all together
223
224 ---
225
226 # Masking the fill characters
227
228 Padding characters can be distinctive.
229
230 Make a function that generates a random letter, based on the `normalised_english_counts`
231
232 Use `callable()` to check if the `fillvalue` should be called or just inserted
233
234 </textarea>
235 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
236 </script>
237
238 <script type="text/javascript"
239 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
240
241 <script type="text/javascript">
242 var slideshow = remark.create({ ratio: "16:9" });
243
244 // Setup MathJax
245 MathJax.Hub.Config({
246 tex2jax: {
247 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
248 }
249 });
250 MathJax.Hub.Queue(function() {
251 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
252 return(elem.SourceElement());
253 }).parent().addClass('has-jax');
254 });
255 MathJax.Hub.Configured();
256 </script>
257 </body>
258 </html>