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;
46 <textarea id=
"source">
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
54 An extension of Caesar ciphers
56 * Count the gaps in the letters.
59 # How affine ciphers work
61 _ciphertext_letter_ =_plaintext_letter_ × a + b
63 * Convert letters to numbers
64 * Take the total modulus
26
68 * Build the `affine_encipher()` function
72 # Deciphering affine ciphers is harder
74 `$$p = \frac{c - b}{a} \mod
26$$`
76 But modular division is hard!
78 Define division as mutiplication by the inverse: `\(\frac{x}{y} = x \times \frac{
1}{y} = x \times y^{-
1}\)`
80 A number _x_, when multiplied by its inverse _x_
<sup>-
1</sup>, gives result of
1.
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).
84 Result from number theory: only numbers coprime with _n_ have multiplicative inverses in arithmetic mod _n_.
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_)
88 Coprime numbers have gcd of
1.
90 _ax_ + _ny_ =
1 mod _n_. But _ny_ mod _n_ =
0, so _ax_ =
1 mod _n_, so _a_ = _x_
<sup>-
1</sup>.
92 Perhaps the algorithm for finding gcds could be useful?
98 .float-right[![right-aligned GCD](gcd.svg)]
100 World's oldest algorithm.
102 _a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_)
104 Repeatedly apply these steps until _r_ =
0, when the other number = gcd(_a_, _b_). For instance, _a_ =
81, _b_ =
57
112 Therefore, gcd(
81,
57) =
3 and
81_x_ +
57_y_ =
3
114 Now unfold the derivation to find _x_ and _y_
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
121 Can we do this in one pass?
125 # Hands up if you're lost
133 .float-right[![right-aligned GCD](fast-good-cheap.gif)]
135 ## Fast, cheap, good: pick two
137 ## Programmer time, execution time, space: pick one, get some of another.
139 (Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.)
141 Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (
6 numbers).
143 Can we trade space for ease?
145 A standard technique is memoisation: store the results somewhere, then just look them up.
149 # Modular multiplication table for
7
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
161 Can use this to find the multiplicative inverses.
163 (
7) |
1 |
2 |
3 |
4 |
5 |
6
164 ----|---|---|---|---|---|---
165 |
1 |
4 |
5 |
2 |
3 |
6
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...
177 5. The decipherment table for this key
178 6. The decipherment table for all keys
180 The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc.
188 Keeping the decipherment close to encipherment seems aesthetically better to me.
190 Giving the ability to do division is the most obvious (to me).
192 As there are only a few possible modular bases, might as well calculate the whole table at startup.
194 ## Now implement affine decipherment.
196 Check both enciphering and deciphering work. Round-trip some text.
199 # Counting from
0 or
1
201 When converting letters to numbers, we're using the range
0-
25.
203 Another convention is to use numbers in range
1-
26.
207 * You'll need another parameter:
209 affine_encipher_letter(letter, multiplier, adder, one_based=False)
213 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
216 <script type=
"text/javascript"
217 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
219 <script type=
"text/javascript">
220 var slideshow = remark.create({ ratio:
"16:9" });
225 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
228 MathJax.Hub.Queue(function() {
229 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
230 return(elem.SourceElement());
231 }).parent().addClass('has-jax');
233 MathJax.Hub.Configured();