Affine ciphers

From 43490849ba6741d30c9638698c477ff7f914bcfe Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 23 Apr 2014 18:44:24 +0100 Subject: [PATCH] Finished affine ciphers --- slides/affine-break.html | 91 +++++++++ slides/affine-encipher.html | 129 +++++++------ slides/gcd.svg | 344 +++++++++++++++++++++++++++++++++++ slides/keyword-encipher.html | 96 ++++++++++ 4 files changed, 604 insertions(+), 56 deletions(-) create mode 100644 slides/affine-break.html create mode 100644 slides/gcd.svg create mode 100644 slides/keyword-encipher.html diff --git a/slides/affine-break.html b/slides/affine-break.html new file mode 100644 index 0000000..cca64e8 --- /dev/null +++ b/slides/affine-break.html @@ -0,0 +1,91 @@ + + + + Affine ciphers + + + + + + + + + + + + diff --git a/slides/affine-encipher.html b/slides/affine-encipher.html index db62817..1a09109 100644 --- a/slides/affine-encipher.html +++ b/slides/affine-encipher.html @@ -95,15 +95,13 @@ Perhaps the algorithm for finding gcds could be useful? # Euclid's algorithm -World's oldest algorithm. - -_a_ = _qb_ + _r_ +.float-right[![right-aligned GCD](gcd.svg)] -gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_) +World's oldest algorithm. -Repeatedly apply these steps until _r_ = 0, when the other number = gcd(a,b) +_a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_) -For instance, _a_ = 81, _b_ = 57 +Repeatedly apply these steps until _r_ = 0, when the other number = gcd(a,b). For instance, _a_ = 81, _b_ = 57 * 81 = 1 Ã 57 + 24 * 57 = 2 Ã 24 + 9 @@ -120,76 +118,95 @@ Now unfold the derivation to find _x_ and _y_ * 3 = (57 - 2 Ã 24) Ã 3 + 24 Ã -1 = 57 Ã 3 + 24 Ã -7 * 3 = 57 Ã 3 + (81 - 57 Ã 1) Ã -7 = 57 Ã 10 + 81 Ã -7 +Can we do this in one pass? + --- -# Example above from http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html +# Hands up if you're lost -## Explanation of extended Euclid's algorithm from [Programming with finite fields](http://jeremykun.com/2014/03/13/programming-with-finite-fields/) +## (Be honest) -**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_. +--- -**Theorem:** For any two integers _a, b_ there exist unique integers _x, y_ such that _ax_ + _by_ = gcd(_a, b_). +# Triple constraints -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. +## Fast, cheap, good: pick two -```python -def gcd(a, b): - if abs(a) < abs(b): - return gcd(b, a) - - while abs(b) > 0: - q,r = divmod(a,b) - a,b = b,r - - return a -``` +## Programmer time, execution time, space: pick one, get some of another. + +(Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.) + +Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (6 numbers). -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. +Can we trade space for ease? + +A standard technique is memoisation: store the results somewhere, then just look them up. --- -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. +# Modular multiplication table for 7 -```python -def extendedEuclideanAlgorithm(a, b): - if abs(b) > abs(a): - (x,y,d) = extendedEuclideanAlgorithm(b, a) - return (y,x,d) - - if abs(b) == 0: - return (1, 0, a) - - x1, x2, y1, y2 = 0, 1, 1, 0 - while abs(b) > 0: - q, r = divmod(a,b) - x = x2 - q*x1 - y = y2 - q*y1 - a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y - - return (x2, y2, a) -``` +(7) | 0 | 1 | 2 | 3 | 4 | 5 | 6 +----|---|---|---|---|---|---|--- + 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 + 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 + 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 + 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 + 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 + 5 | 0 | 5 | 3 | 1 | 6 | 4 | 2 + 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 -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. +Can use this to find the multiplicative inverses. -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! +(7) | 1 | 2 | 3 | 4 | 5 | 6 +----|---|---|---|---|---|--- + | 1 | 4 | 5 | 2 | 3 | 6 -```python -def inverse(self): - x,y,d = extendedEuclideanAlgorithm(self.n, self.p) - return IntegerModP(x) -``` +How much to store? + +--- + +# How much to store? -And indeed it works as expected: +1. The inverses for this modular base. +2. The inverses for all bases (12 of them) +3. All the _x_ Ã· _y_ = _z_ mod _n_ triples... +4. ...for all _n_ +5. The decipherment table for this key +6. The decipherment table for all keys +The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc. + +## Thoughts? + +--- + +# How much to store? + +Keeping the decipherment close to encipherment seems aesthetically better to me. + +Giving the ability to do division is the most obvious (to me). + +As there are only a few possible modular bases, might as well calculate the whole table at startup. + +## Now implement affine decipherment. + +Check both enciphering and deciphering work. Round-trip some text. +--- + +# Counting from 0 or 1 + +When converting letters to numbers, we're using the range 0-25. + +Another convention is to use numbers in range 1-26. + +Implement this. + +* You'll need another parameter: ```python ->>> mod23 = IntegersModP(23) ->>> mod23(7).inverse() -10 (mod 23) ->>> mod23(7).inverse() * mod23(7) -1 (mod 23) +affine_encipher_letter(letter, multiplier, adder, one_based=False) ``` - diff --git a/slides/gcd.svg b/slides/gcd.svg new file mode 100644 index 0000000..80f8256 --- /dev/null +++ b/slides/gcd.svg @@ -0,0 +1,344 @@ + + + \ No newline at end of file diff --git a/slides/keyword-encipher.html b/slides/keyword-encipher.html new file mode 100644 index 0000000..be151a3 --- /dev/null +++ b/slides/keyword-encipher.html @@ -0,0 +1,96 @@ + + + + Affine ciphers + + + + + + + + + + + + -- 2.34.1