4 <title>Affine ciphers
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
51 <textarea id=
"source">
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
59 An extension of Caesar ciphers
61 * Count the gaps in the letters.
67 .indexlink[[Index](index.html)]
71 # How affine ciphers work
73 .ciphertext[_ciphertext_letter_] =.plaintext[_plaintext_letter_] × a + b
75 * Convert letters to numbers
76 * Take the total modulus
26
80 * Build the `affine_encipher()` function
84 # Deciphering affine ciphers is harder
86 `$$p = \frac{c - b}{a} \mod
26$$`
88 But modular division is hard!
90 Define division as mutiplication by the inverse: `\(\frac{x}{y} = x \times \frac{
1}{y} = x \times y^{-
1}\)`
92 A number _x_, when multiplied by its inverse _x_
<sup>-
1</sup>, gives result of
1.
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).
96 Result from number theory: only numbers coprime with _n_ have multiplicative inverses in arithmetic mod _n_.
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_)
100 Coprime numbers have gcd of
1.
102 _mx_ + _ny_ =
1 mod _n_. But _ny_ mod _n_ =
0, so _mx_ =
1 mod _m_, so _m_ = _x_
<sup>-
1</sup>.
104 Perhaps the algorithm for finding gcds could be useful?
110 .float-right[![right-aligned GCD](gcd.svg)]
112 World's oldest algorithm.
114 _a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_)
116 Repeatedly apply these steps until _r_ =
0, when the other number = gcd(_a_, _b_). For instance, _a_ =
81, _b_ =
57
124 Therefore, gcd(
81,
57) =
3 and
81_x_ +
57_y_ =
3
126 Now unfold the derivation to find _x_ and _y_
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
133 Can we do this in one pass?
137 # Hands up if you're lost
145 .float-right[![right-aligned GCD](fast-good-cheap.gif)]
147 ## Fast, cheap, good: pick two
149 ## Programmer time, execution time, space: pick one, get some of another.
151 (Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.)
153 Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (
6 numbers).
155 Can we trade space for ease?
157 A standard technique is memoisation: store the results somewhere, then just look them up.
161 # Modular multiplication table for
7
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
173 Can use this to find the multiplicative inverses.
175 (
7) |
1 |
2 |
3 |
4 |
5 |
6
176 ----|---|---|---|---|---|---
177 |
1 |
4 |
5 |
2 |
3 |
6
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...
189 5. The decipherment table for this key
190 6. The decipherment table for all keys
192 The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc.
200 Keeping the decipherment close to encipherment seems aesthetically better to me.
202 Giving the ability to do division is the most obvious (to me).
204 As there are only a few possible modular bases, might as well calculate the whole table at startup.
206 ## Now implement affine decipherment.
208 Check both enciphering and deciphering work. Round-trip some text.
211 # Counting from
0 or
1
213 When converting letters to numbers, we're using the range
0-
25.
215 Another convention is to use numbers in range
1-
26.
219 * You'll need another parameter:
221 affine_encipher_letter(letter, multiplier, adder, one_based=False)
225 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
228 <script type=
"text/javascript"
229 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
231 <script type=
"text/javascript">
232 var slideshow = remark.create({ ratio:
"16:9" });
237 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
240 MathJax.Hub.Queue(function() {
241 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
242 return(elem.SourceElement());
243 }).parent().addClass('has-jax');
245 MathJax.Hub.Configured();