Fixed the merge conflict
[cipher-training.git] / 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 ## Fast, cheap, good: pick two
134
135 ## Programmer time, execution time, space: pick one, get some of another.
136
137 (Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.)
138
139 Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (6 numbers).
140
141 Can we trade space for ease?
142
143 A standard technique is memoisation: store the results somewhere, then just look them up.
144
145 ---
146
147 # Modular multiplication table for 7
148
149 (7) | 0 | 1 | 2 | 3 | 4 | 5 | 6
150 ----|---|---|---|---|---|---|---
151 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
152 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6
153 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5
154 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4
155 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3
156 5 | 0 | 5 | 3 | 1 | 6 | 4 | 2
157 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1
158
159 Can use this to find the multiplicative inverses.
160
161 (7) | 1 | 2 | 3 | 4 | 5 | 6
162 ----|---|---|---|---|---|---
163 | 1 | 4 | 5 | 2 | 3 | 6
164
165 How much to store?
166
167 ---
168
169 # How much to store?
170
171 1. The inverses for this modular base.
172 2. The inverses for all bases (12 of them)
173 3. All the _x_ ÷ _y_ = _z_ mod _n_ triples...
174 4. ...for all _n_
175 5. The decipherment table for this key
176 6. The decipherment table for all keys
177
178 The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc.
179
180 ## Thoughts?
181
182 ---
183
184 # How much to store?
185
186 Keeping the decipherment close to encipherment seems aesthetically better to me.
187
188 Giving the ability to do division is the most obvious (to me).
189
190 As there are only a few possible modular bases, might as well calculate the whole table at startup.
191
192 ## Now implement affine decipherment.
193
194 Check both enciphering and deciphering work. Round-trip some text.
195 ---
196
197 # Counting from 0 or 1
198
199 When converting letters to numbers, we're using the range 0-25.
200
201 Another convention is to use numbers in range 1-26.
202
203 Implement this.
204
205 * You'll need another parameter:
206 ```python
207 affine_encipher_letter(letter, multiplier, adder, one_based=False)
208 ```
209
210 </textarea>
211 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
212 </script>
213
214 <script type="text/javascript"
215 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
216
217 <script type="text/javascript">
218 var slideshow = remark.create({ ratio: "16:9" });
219
220 // Setup MathJax
221 MathJax.Hub.Config({
222 tex2jax: {
223 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
224 }
225 });
226 MathJax.Hub.Queue(function() {
227 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
228 return(elem.SourceElement());
229 }).parent().addClass('has-jax');
230 });
231 MathJax.Hub.Configured();
232 </script>
233 </body>
234 </html>