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