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