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>