4 <title>Transposition ciphers
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
46 <textarea id=
"source">
48 # Transposition ciphers
50 attack the fort at dawn
61 # Transposition ciphers
63 Rather than changing symbols (substitution ciphers),
67 Still disguises the message.
69 (Good ciphers do both, and more.)
75 Even older than Caesar cipher.
77 * Wrap a strip round a pole
78 * Write the message along it
80 *
"Unreadable" unless reader has pole of same diameter
83 attack the fort at dawn
95 # Generalising: column transposition ciphers
97 Scytale essentially fills a grid by rows, then reads it by columns
99 * (Deciphering is the reverse)
101 Column transposition ciphers:
104 * Reorder columns based on keyword
105 * Read the grid (perhaps different direction)
107 (Keyword = secret → cerst)
109 attack the fort at dawn
118 ttaac htekf traot wand
119 thtw tra aean akod cft
122 Scytale is just a special case of column transposition.
126 # Grids and data structures
128 What operations do we need to do on a grid?
130 How to represent a grid?
134 # Grids and data structures
136 What operations do we need to do on a grid?
138 * Fill, by rows or columns
139 * Empty, by rows or columns
141 * Calculate the size of the grid
142 * Pad message to fit a rectangle of the required size
144 How to represent a grid?
147 * Each row is a string
148 * Rows in order in the list
154 Know number of columns
156 Number of rows = `\(\left \lceil \frac{\mathrm{message\ length}}{\mathrm{columns}} \right \rceil\)`
158 Paddding is (rows ⨉ columns) - message length
160 * What to use as default padding?
163 ## Fit 'thequickbrownfox' (
16 letters) into grid of
170 # Fill and empty grid by rows
172 Split message into row-sized chunks
176 Append all the rows together
178 * `
<string
>.join()`
180 Keep thinking about test cases!
184 # Fill and empty grid by columns
186 Idea: fill and empty by rows, with a transposition.
188 `zip(*rows)` and `itertools.zip_longest(*rows)`
194 How to represent a transposition (_permutation_, to mathematicians)?
196 How to create it from a keyword?
200 # Idea of a transposition
202 Says, for each element, where it should go
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, ...
214 `enumerate(_iterable_)` yields an iterator that walks over the iterable, including the element indexes.
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)]
223 Write the `transpose` and `untranspose` functions.
227 # Transposition from a keyword
229 Deduplicate the keyword
233 Use `
<iterable
>.index()` to find the positions of the letters in the sorted keyword
237 # Transposition ciphers
243 # Back to the scytale
245 Key is number of rows.
247 No transposition of columns.
249 * What does a null transposition look like?
251 How to fill and empty?
253 (Transposing the grid is easier)
257 # Masking the fill characters
259 Padding characters can be distinctive.
261 Make a function that generates a random letter, based on the `normalised_english_counts`
263 Use `callable()` to check if the `fillvalue` should be called or just inserted
266 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
269 <script type=
"text/javascript"
270 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
272 <script type=
"text/javascript">
273 var slideshow = remark.create({ ratio:
"16:9" });
278 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
281 MathJax.Hub.Queue(function() {
282 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
283 return(elem.SourceElement());
284 }).parent().addClass('has-jax');
286 MathJax.Hub.Configured();