slides/affine-encipher.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>Affine 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 # Affine ciphers
  54
  55 a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
  56 --|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
  57 b | e | h | k | n | q | t | w | z | c | f | i | l | o | r | u | x | a | d | g | j | m | p | s | v | y
  58
  59 An extension of Caesar ciphers
  60
  61 * Count the gaps in the letters.
  62
  63 ---
  64
  65 layout: true
  66
  67 .indexlink[[Index](index.html)]
  68
  69 ---
  70
  71 # How affine ciphers work
  72
  73 .ciphertext[_ciphertext_letter_] =.plaintext[_plaintext_letter_] × a + b
  74
  75 * Convert letters to numbers
  76 * Take the total modulus 26
  77
  78 # Enciphering is easy
  79
  80 * Build the `affine_encipher()` function
  81
  82 ---
  83
  84 # Deciphering affine ciphers is harder
  85
  86 `$$p = \frac{c - b}{a} \mod 26$$`
  87
  88 But modular division is hard!
  89
  90 Define division as mutiplication by the inverse: `\(\frac{x}{y} = x \times \frac{1}{y} = x \times y^{-1}\)`
  91
  92 A number _x_, when multiplied by its inverse _x_<sup>-1</sup>, gives result of 1.
  93
  94 This is not always defined in modular arithmetic. For instance, 7 × 4 = 28 = 2 mod 26, but 20 × 4 = 80 = 2 mod 26. Therefore, 4 doesn't have a multiplicative inverse (and therefore makes a bad key for affine ciphers).
  95
  96 Result from number theory: only numbers coprime with _n_ have multiplicative inverses in arithmetic mod _n_.
  97
  98 Another result from number theory: for non-negative integers _m_ and _n_, and there exist unique integers _x_ and _y_ such that _mx_ + _ny_ = gcd(_m_, _n_)
  99
 100 Coprime numbers have gcd of 1.
 101
 102 _mx_ + _ny_ = 1 mod _n_. But _ny_ mod _n_ = 0, so _mx_ = 1 mod _m_, so _m_ = _x_<sup>-1</sup>.
 103
 104 Perhaps the algorithm for finding gcds could be useful?
 105
 106 ---
 107
 108 # Euclid's algorithm
 109
 110 .float-right[![right-aligned GCD](gcd.svg)]
 111
 112 World's oldest algorithm.
 113
 114 _a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_)
 115
 116 Repeatedly apply these steps until _r_ = 0, when the other number = gcd(_a_, _b_). For instance, _a_ = 81, _b_ = 57
 117
 118 * 81 = 1 × 57 + 24
 119 * 57 = 2 × 24 + 9
 120 * 24 = 2 × 9 + 6
 121 * 9 = 1 × 6 + 3
 122 * 6 = 2 × 3 + 0
 123
 124 Therefore, gcd(81, 57) = 3 and 81_x_ + 57_y_ = 3
 125
 126 Now unfold the derivation to find _x_ and _y_
 127
 128 * 3 = 9 × 1 + 6 × -1
 129 * 3 = 9 × 1 + (24 - 2 × 9) × -1 = 9 × 3 + 24 × -1
 130 * 3 = (57 - 2 × 24) × 3 + 24 × -1 = 57 × 3 + 24 × -7
 131 * 3 = 57 × 3 + (81 - 57 × 1) × -7 = 57 × 10 + 81 × -7
 132
 133 Can we do this in one pass?
 134
 135 ---
 136
 137 # Hands up if you're lost
 138
 139 ## (Be honest)
 140
 141 ---
 142
 143 # Triple constraints
 144
 145 .float-right[![right-aligned GCD](fast-good-cheap.gif)]
 146
 147 ## Fast, cheap, good: pick two
 148
 149 ## Programmer time, execution time, space: pick one, get some of another.
 150
 151 (Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.)
 152
 153 Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (6 numbers).
 154
 155 Can we trade space for ease?
 156
 157 A standard technique is memoisation: store the results somewhere, then just look them up.
 158
 159 ---
 160
 161 # Modular multiplication table for 7
 162
 163 (7) | 0 | 1 | 2 | 3 | 4 | 5 | 6
 164 ----|---|---|---|---|---|---|---
 165   0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
 166   1 | 0 | 1 | 2 | 3 | 4 | 5 | 6
 167   2 | 0 | 2 | 4 | 6 | 1 | 3 | 5
 168   3 | 0 | 3 | 6 | 2 | 5 | 1 | 4
 169   4 | 0 | 4 | 1 | 5 | 2 | 6 | 3
 170   5 | 0 | 5 | 3 | 1 | 6 | 4 | 2
 171   6 | 0 | 6 | 5 | 4 | 3 | 2 | 1
 172
 173 Can use this to find the multiplicative inverses.
 174
 175 (7) | 1 | 2 | 3 | 4 | 5 | 6
 176 ----|---|---|---|---|---|---
 177     | 1 | 4 | 5 | 2 | 3 | 6
 178
 179 How much to store?
 180
 181 ---
 182
 183 # How much to store?
 184
 185 1. The inverses for this modular base.
 186 2. The inverses for all bases (12 of them)
 187 3. All the _x_ ÷ _y_ = _z_ mod _n_ triples...
 188 4. ...for all _n_
 189 5. The decipherment table for this key
 190 6. The decipherment table for all keys
 191
 192 The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc.
 193
 194 ## Thoughts?
 195
 196 ---
 197
 198 # How much to store?
 199
 200 Keeping the decipherment close to encipherment seems aesthetically better to me.
 201
 202 Giving the ability to do division is the most obvious (to me).
 203
 204 As there are only a few possible modular bases, might as well calculate the whole table at startup.
 205
 206 ## Now implement affine decipherment.
 207
 208 Check both enciphering and deciphering work. Round-trip some text.
 209 ---
 210
 211 # Counting from 0 or 1
 212
 213 When converting letters to numbers, we're using the range 0-25.
 214
 215 Another convention is to use numbers in range 1-26.
 216
 217 Implement this.
 218
 219 * You'll need another parameter:
 220 ```python
 221 affine_encipher_letter(letter, multiplier, adder, one_based=False)
 222 ```
 223
 224     </textarea>
 225     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 226     </script>
 227
 228     <script type="text/javascript"
 229       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 230
 231     <script type="text/javascript">
 232       var slideshow = remark.create({ ratio: "16:9" });
 233
 234       // Setup MathJax
 235       MathJax.Hub.Config({
 236         tex2jax: {
 237         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 238         }
 239       });
 240       MathJax.Hub.Queue(function() {
 241         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 242             return(elem.SourceElement());
 243         }).parent().addClass('has-jax');
 244       });
 245       MathJax.Hub.Configured();
 246     </script>
 247   </body>
 248 </html>