# Affine ciphers 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 --|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-- 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 An extension of Caesar ciphers * Count the gaps in the letters. --- # How affine ciphers work _ciphertext_letter_ =_plaintext_letter_ × a + b * Convert letters to numbers * Take the total modulus 26 # Enciphering is easy * Build the `affine_encipher()` function --- # Deciphering affine ciphers is harder `$$p = \frac{c - b}{a} \mod 26$$` But modular division is hard! Define division as mutiplication by the inverse: `\(\frac{x}{y} = x \times \frac{1}{y} = x \times y^{-1}\)` A number _x_, when multiplied by its inverse _x_
-1
, gives result of 1. 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). Result from number theory: only numbers coprime with _n_ have multiplicative inverses in arithmetic mod _n_. 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_) Coprime numbers have gcd of 1. _ax_ + _ny_ = 1 mod _n_. But _ny_ mod _n_ = 0, so _ax_ = 1 mod _n_, so _a_ = _x_
-1
. Perhaps the algorithm for finding gcds could be useful? --- # Euclid's algorithm .float-right[![right-aligned GCD](gcd.svg)] World's oldest algorithm. _a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_) 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 * 24 = 2 × 9 + 6 * 9 = 1 × 6 + 3 * 6 = 2 × 3 + 0 Therefore, gcd(81, 57) = 3 and 81_x_ + 57_y_ = 3 Now unfold the derivation to find _x_ and _y_ * 3 = 9 × 1 + 6 × -1 * 3 = 9 × 1 + (24 - 2 × 9) × -1 = 9 × 3 + 24 × -1 * 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? --- # Hands up if you're lost ## (Be honest) --- # Triple constraints .float-right[![right-aligned GCD](fast-good-cheap.gif)] ## Fast, cheap, good: pick two ## 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). Can we trade space for ease? A standard technique is memoisation: store the results somewhere, then just look them up. --- # Modular multiplication table for 7 (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 Can use this to find the multiplicative inverses. (7) | 1 | 2 | 3 | 4 | 5 | 6 ----|---|---|---|---|---|--- | 1 | 4 | 5 | 2 | 3 | 6 How much to store? --- # How much to store? 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 affine_encipher_letter(letter, multiplier, adder, one_based=False) ```