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}$$`
  75
  76 But modular division is hard!
  77
  78
  79 ---
  80
  81 ## Explanation of extended Euclid's algorithm from [Programming with finite fields](http://jeremykun.com/2014/03/13/programming-with-finite-fields/)
  82
  83 **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_.
  84
  85 **Theorem:** For any two integers _a, b_ there exist unique integers _x, y_ such that _ax_ + _by_ = gcd(_a, b_).
  86
  87 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.
  88
  89 ```python
  90 def gcd(a, b):
  91    if abs(a) &lt; abs(b):
  92       return gcd(b, a)
  93
  94    while abs(b) > 0:
  95       q,r = divmod(a,b)
  96       a,b = b,r
  97
  98    return a
  99 ```
 100
 101 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.
 102
 103 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.
 104
 105 ```python
 106 def extendedEuclideanAlgorithm(a, b):
 107    if abs(b) > abs(a):
 108       (x,y,d) = extendedEuclideanAlgorithm(b, a)
 109       return (y,x,d)
 110
 111    if abs(b) == 0:
 112       return (1, 0, a)
 113
 114    x1, x2, y1, y2 = 0, 1, 1, 0
 115    while abs(b) > 0:
 116       q, r = divmod(a,b)
 117       x = x2 - q*x1
 118       y = y2 - q*y1
 119       a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y
 120
 121    return (x2, y2, a)
 122 ```
 123
 124 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.
 125
 126 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!
 127
 128 ```python
 129 def inverse(self):
 130    x,y,d = extendedEuclideanAlgorithm(self.n, self.p)
 131    return IntegerModP(x)
 132 ```
 133
 134 And indeed it works as expected:
 135
 136 ```python
 137 >>> mod23 = IntegersModP(23)
 138 >>> mod23(7).inverse()
 139 10 (mod 23)
 140 >>> mod23(7).inverse() * mod23(7)
 141 1 (mod 23)
 142 ```
 143
 144
 145     </textarea>
 146     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 147     </script>
 148
 149     <script type="text/javascript"
 150       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 151
 152     <script type="text/javascript">
 153       var slideshow = remark.create({ ratio: "16:9" });
 154
 155       // Setup MathJax
 156       MathJax.Hub.Config({
 157         tex2jax: {
 158         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 159         }
 160       });
 161       MathJax.Hub.Queue(function() {
 162         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 163             return(elem.SourceElement());
 164         }).parent().addClass('has-jax');
 165       });
 166       MathJax.Hub.Configured();
 167     </script>
 168   </body>
 169 </html>