text-shadow: 0 0 20px #333;
padding: 2px 5px;
}
+ .indexlink {
+ position: absolute;
+ bottom: 1em;
+ left: 1em;
+ }
+ .float-right {
+ float: right;
+ }
</style>
</head>
<body>
# Breaking caesar ciphers
-
+
+
+---
+
+layout: true
+
+.indexlink[[Index](index.html)]
+
+---
+
+# Human vs Machine
+
+Slow but clever vs Dumb but fast
+
+## Human approach
+
+Ciphertext | Plaintext
+---|---
+ | 
---
-# Brute force
+# Human vs machine
+
+## Machine approach
+
+Brute force.
-How many keys to try?
+Try all keys.
+
+* How many keys to try?
## Basic idea
# How close is it to English?
What does English look like?
+
* We need a model of English.
How do we define "closeness"?
+## Here begineth the yak shaving
+
---
# What does English look like?
. | .
z | 3575
-One way of thinking about this is a 26-dimensional vector.
+Use this to predict the probability of each letter, and hence the probability of a sequence of letters.
-Create a vector of our text, and one of idealised English.
+---
+
+.float-right[]
+
+# Naive Bayes, or the bag of letters
+
+What is the probability that this string of letters is a sample of English?
+
+Ignore letter order, just treat each letter individually.
+
+Probability of a text is `\( \prod_i p_i \)`
+
+Letter | h | e | l | l | o | hello
+------------|---------|---------|---------|---------|---------|-------
+Probability | 0.06645 | 0.12099 | 0.04134 | 0.04134 | 0.08052 | 1.10648239 × 10<sup>-6</sup>
+
+Letter | i | f | m | m | p | ifmmp
+------------|---------|---------|---------|---------|---------|-------
+Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 × 10<sup>-8</sup>
+
+(Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
+
+Letter | h | e | l | l | o | hello
+------------|---------|---------|---------|---------|---------|-------
+Probability | -1.1774 | -0.9172 | -1.3836 | -1.3836 | -1.0940 | -5.956055
-The distance between the vectors is how far from English the text is.
---
-# Vector distances
+# Frequencies of English
+But before then how do we count the letters?
-## FIXME! Diagram of vector subtraction here
+* Read a file into a string
+```python
+open()
+.read()
+```
+* Count them
+```python
+import collections
+collections.Counter()
+```
+
+Create the `language_models.py` file for this.
+
+---
-Several different distance measures (__metrics__, also called __norms__):
+# Canonical forms
-* L<sub>2</sub> norm (Euclidean distance): `\(|\mathbf{x} - \mathbf{y}| = \sqrt{\sum_i (\mathbf{x}_i - \mathbf{y}_i)^2} \)`
+Counting letters in _War and Peace_ gives all manner of junk.
-* L<sub>1</sub> norm (Manhattan distance, taxicab distance): `\(|\mathbf{x} - \mathbf{y}| = \sum_i |\mathbf{x}_i - \mathbf{y}_i| \)`
+* Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
-* L<sub>3</sub> norm: `\(|\mathbf{x} - \mathbf{y}| = \sqrt[3]{\sum_i |\mathbf{x}_i - \mathbf{y}_i|^3} \)`
+```python
+[l.lower() for l in text if ...]
+```
+---
-The higher the power used, the more weight is given to the largest differences in components.
+# Accents
-(Extends out to:
+```python
+>>> 'é' in string.ascii_letters
+>>> 'e' in string.ascii_letters
+```
-* L<sub>0</sub> norm (Hamming distance): `\(|\mathbf{x} - \mathbf{y}| = \sum_i \left\{\begin{matrix} 1 &\mbox{if}\ \mathbf{x}_i \neq \mathbf{y}_i , \\ 0 &\mbox{if}\ \mathbf{x}_i = \mathbf{y}_i \end{matrix} \right| \)`
+## Unicode, combining codepoints, and normal forms
-* L<sub>∞</sub> norm: `\(|\mathbf{x} - \mathbf{y}| = \max_i{(\mathbf{x}_i - \mathbf{y}_i)} \)`
+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
+import unicodedata
+
+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 (`.update()`)
+3. Sort by count (read the docs...)
+4. Write counts to `count_1l.txt`
+```python
+with open('count_1l.txt', 'w') as f:
+ for each letter...:
+ f.write('text\t{}\n'.format(count))
+```
+
+---
+
+# Reading letter probabilities
+
+1. Load the file `count_1l.txt` into a dict, with letters as keys.
+
+2. Normalise the counts (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 }$$`
+ * Return a new dict
+ * Remember the doctest!
+
+3. Create a dict `Pl` that gives the log probability of a letter
+
+4. Create a function `Pletters` that gives the probability of an iterable of letters
+ * What preconditions should this function have?
+ * Remember the doctest!
-neither of which will be that useful.)
---
-# Normalisation of vectors
+# Breaking caesar ciphers
-Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
+New file: `cipherbreak.py`
-* 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 } }\)`
+## Remember the basic idea
-* 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 }\)`
+```
+for each key:
+ decipher with this key
+ how close is it to English?
+ remember the best key
+```
+
+Try it on the text in `2013/1a.ciphertext`. Does it work?
---
-# Angle, not distance
+# Aside: Logging
+
+Better than scattering `print()`statements through your code
+
+```python
+import logging
+
+logger = logging.getLogger(__name__)
+logger.addHandler(logging.FileHandler('cipher.log'))
+logger.setLevel(logging.WARNING)
-Rather than looking at the distance between the vectors, look at the angle between them.
+ logger.debug('Caesar break attempt using key {0} gives fit of {1} '
+ 'and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
-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} \)`
+```
+* Yes, it's ugly.
+
+Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
-But,
-`\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
-and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
+Use `logger.debug()`, `logger.info()`, etc. to log a message.
-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!
+# Homework: how much ciphertext do we need?
-Cosine similarity is 1 if in same direction, 0 if at 90⁰, -1 if antiparallel.
+## Let's do an experiment to find out
-## FIXME! Cosine distance bug: frequencies2 length not squared.
+1. Load the whole corpus into a string (sanitised)
+2. Select a random chunk of plaintext and a random key
+3. Encipher the text
+4. Score 1 point if `caesar_cipher_break()` recovers the correct key
+5. Repeat many times and with many plaintext lengths
+```python
+import csv
-## FIXME! Diagram of vector dot product
+def show_results():
+ with open('caesar_break_parameter_trials.csv', 'w') as f:
+ writer = csv.DictWriter(f, ['name'] + message_lengths,
+ quoting=csv.QUOTE_NONNUMERIC)
+ writer.writeheader()
+ for scoring in sorted(scores.keys()):
+ scores[scoring]['name'] = scoring
+ writer.writerow(scores[scoring])
+```
</textarea>
<script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
projects / cipher-training.git / blobdiff