text-shadow: 0 0 20px #333;
padding: 2px 5px;
}
+ .float-right {
+ float: right;
+ }
</style>
</head>
<body>
# Breaking caesar ciphers
-
+
---
-# Brute force
+# Human vs Machine
+
+Slow but clever vs Dumb but fast
+
+## Human approach
+
+Ciphertext | Plaintext
+---|---
+ | 
+
+---
+
+# 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"?
+---
+
+# 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 (`.update()`)
+3. Sort by count
+4. Write counts to `count_1l.txt` (`'text{}\n'.format()`)
+
+---
+
+# Vector distances
+
+.float-right[]
+
+Several different distance measures (__metrics__, also called __norms__):
+
+* L<sub>2</sub> norm (Euclidean distance):
+`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
+
+* L<sub>1</sub> norm (Manhattan distance, taxicab distance):
+`\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
+
+* L<sub>3</sub> 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<sub>0</sub> 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<sub>∞</sub> 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[]
+
+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.
+
+---
+
+# 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!
+
+---
+
+# Breaking caesar ciphers (at last!)
+
+## Remember the basic idea
+
+```
+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?
+
+---
+
</textarea>
<script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
</script>
+
+ <script type="text/javascript"
+ src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
<script type="text/javascript">
- var slideshow = remark.create();
+ var slideshow = remark.create({ ratio: "16:9" });
+
+ // Setup MathJax
+ MathJax.Hub.Config({
+ tex2jax: {
+ skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+ }
+ });
+ MathJax.Hub.Queue(function() {
+ $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+ return(elem.SourceElement());
+ }).parent().addClass('has-jax');
+ });
+ MathJax.Hub.Configured();
</script>
</body>
-</html>
\ No newline at end of file
+</html>
projects / cipher-training.git / blobdiff