# Breaking caesar ciphers ![center-aligned Caesar wheel](caesarwheel1.gif) --- # Human vs Machine Slow but clever vs Dumb but fast ## Human approach Ciphertext | Plaintext ---|--- ![left-aligned Ciphertext frequencies](c1a_frequency_histogram.png) | ![left-aligned English frequencies](english_frequency_histogram.png) --- # Human vs machine ## Machine approach Brute force. Try all keys. * How many keys to try? ## Basic idea ``` for each key: decipher with this key how close is it to English? remember the best key ``` What steps do we know how to do? --- # How close is it to English? What does English look like? * We need a model of English. How do we define "closeness"? --- # What does English look like? ## Abstraction: frequency of letter counts Letter | Count -------|------ a | 489107 b | 92647 c | 140497 d | 267381 e | 756288 . | . . | . . | . z | 3575 One way of thinking about this is a 26-dimensional vector. Create a vector of our text, and one of idealised English. The distance between the vectors is how far from English the text is. --- # Frequencies of English But before then how do we count the letters? * Read a file into a string ```python open() .read() ``` * Count them ```python import collections ``` Create the `language_models.py` file for this. --- # Canonical forms Counting letters in _War and Peace_ gives all manner of junk. * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting ```python [l.lower() for l in text if ...] ``` --- # Accents ```python >>> 'é' in string.ascii_letters >>> 'e' in string.ascii_letters ``` ## Unicode, combining codepoints, and normal forms Text encodings will bite you when you least expect it. - **é** : LATIN SMALL LETTER E WITH ACUTE (U+00E9) - **e** + ** ́** : LATIN SMALL LETTER E (U+0065) + COMBINING ACUTE ACCENT (U+0301) * urlencoding is the other pain point. --- # Five minutes on StackOverflow later... ```python def unaccent(text): """Remove all accents from letters. It does this by converting the unicode string to decomposed compatibility form, dropping all the combining accents, then re-encoding the bytes. >>> unaccent('hello') 'hello' >>> unaccent('HELLO') 'HELLO' >>> unaccent('héllo') 'hello' >>> unaccent('héllö') 'hello' >>> unaccent('HÉLLÖ') 'HELLO' """ return unicodedata.normalize('NFKD', text).\ encode('ascii', 'ignore').\ decode('utf-8') ``` --- # Find the frequencies of letters in English 1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`. 2. Find the frequencies 3. Sort by count (`sorted(, key=)` ; `.items()`, `.keys()`, `.values()`, `.get()`) 4. Write counts to `count_1l.txt` --- # Vector distances .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)] Several different distance measures (__metrics__, also called __norms__): * L
2
norm (Euclidean distance): `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)` * L
1
norm (Manhattan distance, taxicab distance): `\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)` * L
3
norm: `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)` The higher the power used, the more weight is given to the largest differences in components. (Extends out to: * L
0
norm (Hamming distance): `$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{ \begin{matrix} 1 &\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\ 0 &\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$` * L
∞
norm: `\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)` neither of which will be that useful here, but they keep cropping up.) --- # Normalisation of vectors Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them. * Eucliean scaling (vector with unit length): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \sqrt{\mathbf{x}_1^2 + \mathbf{x}_2^2 + \mathbf{x}_3^2 + \dots } }$$` * Normalisation (components of vector sum to 1): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \mathbf{x}_1 + \mathbf{x}_2 + \mathbf{x}_3 + \dots }$$` --- # Angle, not distance Rather than looking at the distance between the vectors, look at the angle between them. .float-right[![right-aligned Vector dot product](vector-dot-product.svg)] Vector dot product shows how much of one vector lies in the direction of another: `\( \mathbf{A} \bullet \mathbf{B} = \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)` But, `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)` and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)` A bit of rearranging give the cosine simiarity: `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } = \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$` This is independent of vector lengths! Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel. --- # An infinite number of monkeys What is the probability that this string of letters is a sample of English? Given 'th', 'e' is about six times more likely than 'a' or 'i'. ## Naive Bayes, or the bag of letters Ignore letter order, just treat each letter individually. Probability of a text is `\( \prod_i p_i \)` (Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`) --- # Which is best? | Euclidean | Normalised ---|-----------|------------ L1 | x | x L2 | x | x L3 | x | x Cosine | x | x And the probability measure! * Nine different ways of measuring fitness. ## Computing is an empircal science Let's do some experiments to find the best solution! --- ## Step 1: get **some** codebreaking working Let's start with the letter probability norm, because it's easy. ## Step 2: build some other scoring functions We also need a way of passing the different functions to the keyfinding function. ## Step 3: find the best scoring function Try them all on random ciphertexts, see which one works best.