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 World's oldest algorithm.
  99
 100 _a_ = _qb_ + _r_
 101
 102 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)
 105
 106 For instance, _a_ = 81, _b_ = 57
 107
 108 * 81 = 1 × 57 + 24
 109 * 57 = 2 × 24 + 9
 110 * 24 = 2 × 9 + 6
 111 * 9 = 1 × 6 + 3
 112 * 6 = 2 × 3 + 0
 113
 114 Therefore, gcd(81, 57) = 3 and 81_x_ + 57_y_ = 3
 115
 116 Now unfold the derivation to find _x_ and _y_
 117
 118 * 3 = 9 × 1 + 6 × -1
 119 * 3 = 9 × 1 + (24 - 2 × 9) × -1 = 9 × 3 + 24 × -1
 120 * 3 = (57 - 2 × 24) × 3 + 24 × -1 = 57 × 3 + 24 × -7
 121 * 3 = 57 × 3 + (81 - 57 × 1) × -7 = 57 × 10 + 81 × -7
 122
 123 ---
 124
 125 # Example above from http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html
 126
 127 ## Explanation of extended Euclid's algorithm from [Programming with finite fields](http://jeremykun.com/2014/03/13/programming-with-finite-fields/)
 128
 129 **Definition:** An element _d_ is called a greatest common divisor (gcd) of _a, b_ if it divides both _a_ and _b_, and for every other _z_ dividing both _a_ and _b_, _z_ divides _d_.
 130
 131 **Theorem:** For any two integers _a, b_ there exist unique integers _x, y_ such that _ax_ + _by_ = gcd(_a, b_).
 132
 133 We could beat around the bush and try to prove these things in various ways, but when it comes down to it there’s one algorithm of central importance that both computes the gcd and produces the needed linear combination _x, y_. The algorithm is called the Euclidean algorithm. Here is a simple version that just gives the gcd.
 134
 135 ```python
 136 def gcd(a, b):
 137    if abs(a) &lt; abs(b):
 138       return gcd(b, a)
 139
 140    while abs(b) > 0:
 141       q,r = divmod(a,b)
 142       a,b = b,r
 143
 144    return a
 145 ```
 146
 147 This works by the simple observation that gcd(_a_, _aq_ + _r_) = gcd(_a_, _r_) (this is an easy exercise to prove directly). So the Euclidean algorithm just keeps applying this rule over and over again: take the remainder when dividing the bigger argument by the smaller argument until the remainder becomes zero. Then gcd(_x_, 0) = 0 because everything divides zero.
 148
 149 ---
 150
 151 Now the so-called ‘extended’ Euclidean algorithm just keeps track of some additional data as it goes (the partial quotients and remainders). Here’s the algorithm.
 152
 153 ```python
 154 def extendedEuclideanAlgorithm(a, b):
 155    if abs(b) &gt; abs(a):
 156       (x,y,d) = extendedEuclideanAlgorithm(b, a)
 157       return (y,x,d)
 158
 159    if abs(b) == 0:
 160       return (1, 0, a)
 161
 162    x1, x2, y1, y2 = 0, 1, 1, 0
 163    while abs(b) > 0:
 164       q, r = divmod(a,b)
 165       x = x2 - q*x1
 166       y = y2 - q*y1
 167       a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y
 168
 169    return (x2, y2, a)
 170 ```
 171
 172 Indeed, the reader who hasn’t seen this stuff before is encouraged to trace out a run for the numbers 4864, 3458. Their gcd is 38 and the two integers are 32 and -45, respectively.
 173
 174 How does this help us compute inverses? Well, if we want to find the inverse of _a_ modulo _p_, we know that their gcd is 1. So compute the _x, y_ such that _ax_ + _py_ = 1, and then reduce both sides mod _p_. You get _ax_ + 0 = 1 _mod p_, which means that _x mod p_ is the inverse of _a_. So once we have the extended Euclidean algorithm our inverse function is trivial to write!
 175
 176 ```python
 177 def inverse(self):
 178    x,y,d = extendedEuclideanAlgorithm(self.n, self.p)
 179    return IntegerModP(x)
 180 ```
 181
 182 And indeed it works as expected:
 183
 184 ```python
 185 >>> mod23 = IntegersModP(23)
 186 >>> mod23(7).inverse()
 187 10 (mod 23)
 188 >>> mod23(7).inverse() * mod23(7)
 189 1 (mod 23)
 190 ```
 191
 192
 193     </textarea>
 194     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 195     </script>
 196
 197     <script type="text/javascript"
 198       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 199
 200     <script type="text/javascript">
 201       var slideshow = remark.create({ ratio: "16:9" });
 202
 203       // Setup MathJax
 204       MathJax.Hub.Config({
 205         tex2jax: {
 206         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 207         }
 208       });
 209       MathJax.Hub.Queue(function() {
 210         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 211             return(elem.SourceElement());
 212         }).parent().addClass('has-jax');
 213       });
 214       MathJax.Hub.Configured();
 215     </script>
 216   </body>
 217 </html>