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>