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;
51 <textarea id=
"source">
53 # Transposition ciphers
55 attack the fort at dawn
68 .indexlink[[Index](index.html)]
72 # Transposition ciphers
74 Rather than changing symbols (substitution ciphers),
78 Still disguises the message.
80 (Good ciphers do both, and more.)
86 Even older than Caesar cipher.
88 * Wrap a strip round a pole
89 * Write the message along it
91 *
"Unreadable" unless reader has pole of same diameter
94 attack the fort at dawn
106 # Generalising: column transposition ciphers
108 Scytale essentially fills a grid by rows, then reads it by columns
110 * (Deciphering is the reverse)
112 Column transposition ciphers:
115 * Reorder columns based on keyword
116 * Read the grid (perhaps different direction)
118 (Keyword = secret → cerst)
120 attack the fort at dawn
129 ttaac htekf traot wand
130 thtw tra aean akod cft
133 Scytale is just a special case of column transposition.
137 # Grids and data structures
139 What operations do we need to do on a grid?
141 How to represent a grid?
145 # Grids and data structures
147 What operations do we need to do on a grid?
149 * Fill, by rows or columns
150 * Empty, by rows or columns
152 * Calculate the size of the grid
153 * Pad message to fit a rectangle of the required size
155 How to represent a grid?
158 * Each row is a string
159 * Rows in order in the list
165 Know number of columns
167 Number of rows = `\(\left \lceil \frac{\mathrm{message\ length}}{\mathrm{columns}} \right \rceil\)`
169 Paddding is (rows ⨉ columns) - message length
171 * What to use as default padding?
174 ## Fit 'thequickbrownfox' (
16 letters) into grid of
181 # Fill and empty grid by rows
183 Split message into row-sized chunks
187 Append all the rows together
189 * `
<string
>.join()`
191 Keep thinking about test cases!
195 # Fill and empty grid by columns
197 Idea: fill and empty by rows, with a transposition.
199 `zip(*rows)` and `itertools.zip_longest(*rows)`
205 How to represent a transposition (_permutation_, to mathematicians)?
207 How to create it from a keyword?
211 # Idea of a transposition
213 Says, for each element, where it should go
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, ...
225 `enumerate(_iterable_)` yields an iterator that walks over the iterable, including the element indexes.
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)]
234 Write the `transpose` and `untranspose` functions.
238 # Transposition from a keyword
240 Deduplicate the keyword
244 Use `
<iterable
>.index()` to find the positions of the letters in the sorted keyword
248 # Transposition ciphers
254 # Back to the scytale
256 Key is number of rows.
258 No transposition of columns.
260 * What does a null transposition look like?
262 How to fill and empty?
264 (Transposing the grid is easier)
268 # Masking the fill characters
270 Padding characters can be distinctive.
272 Make a function that generates a random letter, based on the `normalised_english_counts`
274 Use `callable()` to check if the `fillvalue` should be called or just inserted
277 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
280 <script type=
"text/javascript"
281 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
283 <script type=
"text/javascript">
284 var slideshow = remark.create({ ratio:
"16:9" });
289 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
292 MathJax.Hub.Queue(function() {
293 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
294 return(elem.SourceElement());
295 }).parent().addClass('has-jax');
297 MathJax.Hub.Configured();