Affine ciphers

From 0188c8e755e8950facd9eb34932000c2fb0569fa Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 3 Jul 2014 20:44:02 +0100 Subject: [PATCH] Merged slides from presentation-slides branch --- slides/affine-break.html | 91 ++++++ slides/affine-encipher.html | 236 ++++++++++++++ slides/alternative-plaintext-scoring.html | 244 ++++++++++++++ slides/caesar-break.html | 155 ++++----- slides/fast-good-cheap.gif | Bin 0 -> 9192 bytes slides/further-work.html | 92 ++++++ slides/gcd.svg | 344 ++++++++++++++++++++ slides/keyword-break.html | 224 +++++++++++++ slides/keyword-encipher.html | 209 ++++++++++++ slides/transposition-encipher.html | 258 +++++++++++++++ slides/word-segmentation.html | 370 ++++++++++++++++++++++ 11 files changed, 2147 insertions(+), 76 deletions(-) create mode 100644 slides/affine-break.html create mode 100644 slides/affine-encipher.html create mode 100644 slides/alternative-plaintext-scoring.html create mode 100644 slides/fast-good-cheap.gif create mode 100644 slides/further-work.html create mode 100644 slides/gcd.svg create mode 100644 slides/keyword-break.html create mode 100644 slides/keyword-encipher.html create mode 100644 slides/transposition-encipher.html create mode 100644 slides/word-segmentation.html diff --git a/slides/affine-break.html b/slides/affine-break.html new file mode 100644 index 0000000..58b27f6 --- /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 new file mode 100644 index 0000000..30f3900 --- /dev/null +++ b/slides/affine-encipher.html @@ -0,0 +1,236 @@ + + + + Affine ciphers + + + + +

+
+# 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)
+```
+
+

+ + + + + + + diff --git a/slides/alternative-plaintext-scoring.html b/slides/alternative-plaintext-scoring.html new file mode 100644 index 0000000..d6f4aa1 --- /dev/null +++ b/slides/alternative-plaintext-scoring.html @@ -0,0 +1,244 @@ + + + + Alternative plaintext scoring + + + + +

+
+# Alternative plaintext scoring methods
+
+---
+
+# Back to frequency of letter counts
+
+Letter | Count
+-------|------
+a | 489107
+b | 92647
+c | 140497
+d | 267381
+e | 756288
+. | .
+. | .
+. | .
+z | 3575
+
+Another 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.
+
+---
+
+# Vector distances
+
+.float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
+
+Several different distance measures (__metrics__, also called __norms__):
+
+* L2 norm (Euclidean distance): 
+`$\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} $`
+
+* L1 norm (Manhattan distance, taxicab distance): 
+`$\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| $`
+
+* L3 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:
+
+* L0 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.
+
+---
+
+# 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!
+
+---
+
+# Experimental harness
+
+## Step 1: build some other scoring functions
+
+We need a way of passing the different functions to the keyfinding function.
+
+## Step 2: find the best scoring function
+
+Try them all on random ciphertexts, see which one works best.
+
+---
+
+# Functions are values!
+
+```python
+>>> Pletters
+<function Pletters at 0x7f60e6d9c4d0>
+```
+
+```python
+def caesar_break(message, fitness=Pletters):
+ """Breaks a Caesar cipher using frequency analysis
+...
+ for shift in range(26):
+ plaintext = caesar_decipher(message, shift)
+ fit = fitness(plaintext)
+```
+
+---
+
+# Changing the comparison function
+
+* Must be a function that takes a text and returns a score
+ * Better fit must give higher score, opposite of the vector distance norms
+
+```python
+def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert):
+ def frequency_compare(text):
+ ...
+ return score
+ return frequency_compare
+```
+
+---
+
+# Data-driven processing
+
+```python
+metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'}, 
+ {'func': norms.l2, 'invert': True, 'name': 'l2'},
+ {'func': norms.l3, 'invert': True, 'name': 'l3'},
+ {'func': norms.cosine_similarity, 'invert': False, 'name': 'cosine_similarity'}]
+scalings = [{'corpus_frequency': normalised_english_counts, 
+ 'scaling': norms.normalise,
+ 'name': 'normalised'},
+ {'corpus_frequency': euclidean_scaled_english_counts, 
+ 'scaling': norms.euclidean_scale,
+ 'name': 'euclidean_scaled'}]
+```
+
+Use this to make all nine scoring functions.
+
+
+

+ + + + + + + diff --git a/slides/caesar-break.html b/slides/caesar-break.html index 187719d..5ea77b9 100644 --- a/slides/caesar-break.html +++ b/slides/caesar-break.html @@ -111,11 +111,34 @@ e | 756288 . | . 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. +--- + +# An infinite number of monkeys + +What is the probability that this string of letters is a sample of English? + +## Naive Bayes, or the bag of letters + +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^-6 + +Letter | i | f | m | m | p | ifmmp +------------|---------|---------|---------|---------|---------|------- +Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 Ã 10^-8 + +(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. --- @@ -126,13 +149,15 @@ But before then how do we count the letters? * Read a file into a string ```python open() -read() +.read() ``` * Count them ```python import collections ``` +Create the `language_models.py` file for this. + --- # Canonical forms @@ -146,20 +171,21 @@ Counting letters in _War and Peace_ gives all manner of junk. ``` --- - # Accents ```python ->>> caesar_encipher_letter('Ã©', 1) +>>> 'Ã©' in string.ascii_letters +>>> 'e' in string.ascii_letters ``` -What does it produce? - -What should it produce? ## 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. --- @@ -190,101 +216,78 @@ def unaccent(text): --- -# Vector distances - -.float-right[![right-aligned Vector subtraction](vector-subtraction.svg)] - -Several different distance measures (__metrics__, also called __norms__): +# Find the frequencies of letters in English -* L₂ norm (Euclidean distance): -`$\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} $` +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()`) -* L₁ norm (Manhattan distance, taxicab distance): -`$\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| $` +--- -* L₃ norm: -`$\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} $` +# Reading letter probabilities -The higher the power used, the more weight is given to the largest differences in components. +1. Load the file `count_1l.txt` into a dict, with letters as keys. -(Extends out to: +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! -* L₀ 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. $$` +3. Create a dict `Pl` that gives the log probability of a letter -* L_∞ norm: -`$\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} $` +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. +## Remember the basic idea -* 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 } }$$` +``` +for each key: + decipher with this key + how close is it to English? + remember the best key +``` -* 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 }$$` +Try it on the text in `2013/1a.ciphertext`. Does it work? --- -# 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)] +# Aside: Logging -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. - ---- +Better than scattering `print()`statements through your code -# An infinite number of monkeys - -What is the probability that this string of letters is a sample of English? +```python +import logging -Given 'th', 'e' is about six times more likely than 'a' or 'i'. +logger = logging.getLogger(__name__) +logger.addHandler(logging.FileHandler('cipher.log')) +logger.setLevel(logging.WARNING) -## Naive Bayes, or the bag of letters + logger.debug('Caesar break attempt using key {0} gives fit of {1} ' + 'and decrypt starting: {2}'.format(shift, fit, plaintext[:50])) -Ignore letter order, just treat each letter individually. +``` +* Yes, it's ugly. -Probability of a text is `$ \prod_i p_i $` +Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG -(Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `$ \sum_i \log p_i $`) +Use `logger.debug()`, `logger.info()`, etc. to log a message. --- -# 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. +# How much ciphertext do we need? -## Computing is an empircal science +## Let's do an experiment to find out +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 diff --git a/slides/fast-good-cheap.gif b/slides/fast-good-cheap.gif new file mode 100644 index 0000000000000000000000000000000000000000..63411f0ee1c3ebeb00ab49d30edccb436715e0c0 GIT binary patch literal 9192 zcmV(|$9Q)*j< zt>o+RwQ6dJ&$xx7!g!jz?)ddkXOG;uxx$5oX>gD;t%a?^*1ULl1eIzPg?pn(Nvhq< zoI5*?YI%FF+Ol>Pnwpt#S8c8VT+gsGmD`0?>Oa#MH7 ztukkrI%AWkPfy9#zv(;lslnhFqF8HE&^i zi#1r0MVU&)etv`~7c|xBB(<{rdXn&(ASv zmo#OVKwype{rh29MhlW+Cx2NJjbM^EH~;_tGiI3pnP!V0RRX8fPaF6goTEOh>41ejE#P{Qdr@H8{{4NRSnWBKP>X`Ny!K!-t11 z6r4yeN5XqiAZpym(OVpfAjt(0agmRL8y!=sTv_UdiI6a*SuDxN0?V5?b2cInv!^o? zH1E-9p|hw_oZx&aW#!~tP(BWhN}Z~)#L}zwp7KF6fU4K8??4E=>QjXpt@i+cUCVYG z1F}m0XQJhkv8~;^sF=X@IdbkjE^Y7%9_-2G-kx&(;vmep@y^3BulT(vVvXa=m<91r z0XZZGr<3nJ$V{5?gw7$ehECYEwClDAoS>$tf#m9hYG3RA`gZoj#JBkr*iHPXUf%`B zpb37_TJh&M;RHcm5H$09>7Z-x7?1iu)z|M;-cJ5uK=1T8LAWcIxXyGwQK`2gB6VjC3g&>+@ zm4@Pg*P(d&gs5UD=aDFldMDDf(26v6B9V*I)E6U7b=ByjBOl=yjRwo@SQ21ACaH-3 zVM0PIaOR2IbzT1Im}Fj->{LAFBEBm+6142BiS3`5Bn$pS1>xYk7r68bq&JIrl4c z(uwNFq{Jrl;jzSZmuZ&GcA6rzy0sW7snwc_?QS=&+AUhIeoGnx(v+~oy6i52sc#wp zF|Jkunwy!fKkcFKzWVa%8?*B!WRty@JqXPb{O)V8Z({_ER)qvJmfkSJQPIs$7=!Oq)`%`KJrh7`sLSr@X)bINccb0qEmGYC{){nF4- zTP+O(Xzl{qmW8iT+s?dgKJ}@$qVc@6v#x+vr;?vTu1BYy-S2l~b4AdI<$~V{fm{M~ zh^(HG29kk*X`XAA0;mVMr_?Kg{=gS3R!6e@K_+(N>fi4cfIATSV_{)ans<=!IrBZB zSl4jjJEB*$t6|JH8|xPGsP{mvJWGe`7@so;moO!wMt#j{py3vP0~c6;dn7~1Q}TgC zc4*5PmrEG^P{RQ_jB6-{dtXA>M=~6sGW9PJrNvlzOl)3kXF(PB3YN)fQgum8~tC56<+OQ>-*6CMWth1~)`;nesPDe{Yy zPZ?MymjOdqh%I5Q>=U@mCnm-il~wpC&%9GTkRyeOG4OQNNg{Az(;{^rYK z;4w^#o7V%b=Eh}OOp98PTr-JLIYV_WV8~2Z3zj#RB3SH?Hrr+~Jb5Khj_Z;8LgieD zxd(YZg=p#=#UTyV$a$HQWaRXV3iU-gzeFvcp`co%+}W*ZTFe5s3FjV)I2rIE6ch>M z3j;Q~(M{50mH{&*zakkLk)m@hp1Pf?B<~+Y z_}cgKpr)*-VBvVs-BFo$82Vl@y{i$}uquwm3Hl~defbnhG#DLPR_oRwM8mF|dxZ(!%P$MB zVz>!o=XZs+L2;6)f#XEmwFVnpS73M#D{h4ffSjL7BV$OyOb1SNA+kTSSp$S_n zdql~v)Y60t`BkYxVNu;Ux55N)PH+7zs9sjUfXo*$^ByRxAO??EU~Wb5DnhMP227yS zqK1VDIP6$dUjzqNlXP&TDoCwB?4l=j#sNG3t67rS)(JEA^*#PcG9fr1(80;2#n2oS zpl;K)thgVubxmXm-&Wce>GN5yQ)7O;+D)y=XE&c=z9p1;$Rr#0-stOVYNzqEwPWi= z;kpVUW6rg!m;jMMP-;D+yCm%v9d9R7fU8k;GWc9&VG;Q|9=O>Li{00Yp+SP;J^UW_ zhp% zeB>Sed6};EZX*_s)hLZ$CRr+tAat4s5|}{4RX|~jfq>^sNv_lrLhOCrcs1Hin58Gv z+%7^_8rhZGMga^92H;I@4R6Jg*AA8cWKLW$g>&#~;@w5_&S}1cw^jS<32#09 zxQq78H5-)lmds(WP7fa%!MbqcYI>}+e}DqdYYEa86SiM03&PAAD%#T4K_5^+CZYq@ zK0FQ|!owtnhuZ)HedvP$pcHX^RUJ2^$H$cAS7kMg8QmF3ejm>8gB``4U!ce30)$=n z=Y9N233#{xtf2iq=wL_c-WRq#q_6oWWW3LFJbF}sc0WKK-6+t0eSiV3Hz7fHHBj{w zYPJUnNE09QJp6?mL2zs3b9X+Mdjgnz8E_(^moQZ)Q6DHj=5`n+;0t!8Xs&<-4<`r6 zmw{HWd22(g-fp>kh-aCaVtYR8w0+V_IPRyb$| zY`w?_q-UcB$Ax|YiDB3}Sceu@WiRvg3Ku{Cn0P+}2@7QffC$-s zbLbbq=ypMIkB2jN0{1av)neuY0&td$ut10g*^vU6h=XKthu4jXcO9mOEvVNDYnVCc zcmXO1$Y6mQ1OTPr+ah`G|)jds+7_ zM!5hJyf$DLpbY4>0L# zhB%os=@)=jQHAq-p@Dy>qJI;{Iv|h+Mh0hmCk_9Xl%J@Y?S}!~$4mM`mByBbCV3sV zax4+p3M$DuGbMJ2>1<&+gut1BG--8UI2ZA^2gS%7JJ~2Bcw`5Jj{c>N&JYGBM`qJ_ zolNPJPceRzVVT}|BDB{iS@~K7z>MZ|chA6%s3w{2X_jcAcv{hc+u0$(cP7I}k^5%c)R6>dKP@}V`iO$fQsHT)WDu5Uu2XvT+4H%C) zc1eTMoC9H`)zgP!NoHi(q}rFA!Lf+nITujomJmiI<4F)&Dx%R42F6#RU|Nmv$#SC< zrE7MaXTpO$(WZ!lc0!1Kb6SKO$Q&e@mTt+N{PLapSR?!x5)6ZII$gqmMWJJ2|JHLN+7fuU=~D2ME0oTprm9b2hs|;TKJJhLUcG-hm~uk z`hlhWXlSqSmHg7I6alkmBeSMUvqr*@g4v5`svm2*hA0S{{Nl3H0H;8^yKyLrF;b5V zNFgaFY)gwQz|=z|!*|5n6H(hYBFnty3V()!Z5jHV3mPrbfVU{-LuCuG;G4E}${zHY zFjH!ZS;ViRS{xoaokgi$a0a^K;D$^3z3*Fue+wWT=xz>ZF-I#S<mqDw+r(3e&(V~O7CHvC+S~R5%R`x7ivV+DsUAyUvHhPJ8QX(EJBrAkTep zu4sXvH%T%!%$b>SxFH(MyRo8WfkSv69TOgR!}*Z~^Ud(kPwM zD!tO}qRAlZYb;v`9$?U-OcQnNoo!1@VSF1geHT;QAJ{B3lWYhOZ~z9)!3hD$;T*R{ zV$p2TvrY1|=vKIeFaidRx*kMz#uhr|tRU6P7EK!_-Fr6sdsod_~u&mn4* zHBOBPvMkRVjTR}_z?>qaUP01ABD!SO(~EG-@?6t+ay16ZDGvx1u-ha-Ei|0X2;6+s z_nNWQlBQmjeyaX-N-_rYHzKazDR~%5!g5)z^GQ(kTBEooY>vA*hb<2+@sm|5Ti$N ztB`$ill=%qZP`eD5BNOam4p_(%n~KsB*ctrtL+I^UD^hFPBD_pmkBjjSrpQIC9hpG zvAqdroz{MFxi)qp>UPSwjT7&xA-wHtzAXuOEzi}87G1pm2Rn^R9oW|3coWLqBy8+! z99jy84c#@%FZs+Ifz;96W)#?cAlfZ$+|3DFK*Y4H*H6)+7Y85;K+5}amQ=kF2v(7S0kfrz~>LF&#b%pDg5h3?N>3HErHCDv{z4Lf5{A->6X8 z-W=mv(w$f57tPHOjO!u+jcPxB45aPN@ZBLapz4K#wJqKck4++x{WMQL3bXCaRF3Of zzAqx4$F9;5o{b}Vz{zJb#-Q*9m~ic8ZtH25>;%>SXX7o}A*3uT00ZO>0|IdF=$`KC zzV7Uf?kn)_@E-5-KJWAn?@-_ycyQ+i$mcc82WD2LCGqF(5a`NM@JjIkatg}AeR=#I zVwBs~LBZZTq{#+f@jlT5APyiInoO2N;d@};Mg$RZZSf>e5qfY3Fiy0?ia0G`O!igd z2{G&bfZiov^95lCh|M0lK2^pv>!90YKljl9 z1zr%`%IrZYYj_Z6+bl}$>#*Z=Klss*1Q}2NoSCzVhdSO1yAMlF_>iv$d64p~=|5{k zGN~OLGOrF`4*8xB3pjt~<<#&edknV*yl?j2jP__*P!Z<>l>74&V%OLJ>dH^}Cy)2F zeP(N9UoF63%pSvlzYMRQ{j4AQ-W=Tt(PS&P@d@Mg*RjXQ@c8IY_eT%ov0oFN3J5}b zgM@{IG<=DQi;RtqiD(0Vla!T~mzbHFARK<4pP-?lqok##r>Lo_tE{cAucRM+v$VCg zx45~wySy2Xzl#cn!+Qh3$HxGg%goLHlnk)Z($mz{*4L;#yxZK}-c~lqzZS%WF5>8o z15Vj6lpCbrpFuTk+$qciCy2d=5F<*ImV}?hi@FRL zT;yWlf{ly-9K*4&WTi9{Q>t94vP>R~Fkzng0W#5oau#YPqOrgMFcE7^mgJ#=rO~5E zt=Wmm)S?cZ0Lnek$){rrM86&gT{t1B*RNnv;b}^?8-{Q-1r4KGMBtutz}ReUhrmhL zyLiDuu~N40E?+eV3@bpD9HAn>6x^8WtV`aFBZ<(dCz5QDohU^(uNL@aP#sYa*i=+m3}z}LFpr|FUpD+n?+v8%w`kf(G(z5oB9 zXyaaAXQfk|AuZIT*+6^XaEuW9#R1@i{^@bYfPDcbj$4J~1k!;F()WmBiRdkb zAz7D+^8hhZZR8n)dw>Rv1FZyl&1r45z-Zj~t7lDI}eaHQ?ATbWwR|sdnL?M)fjfVP_OORru zAuvZeXpmZlBJyXK$8eF*LN}Nw>a9qrSSmj)9#g1@=oGr0BJvpmtRo~XL;$YL9#!40 z{fHw(f<~6(rA@=A`U_AB5!LLsDzOJGKYjjEgoo*9YKU#b8ix#+?sNt2yb_r?u32dU z6R0?^eg+Vc$I!_R2zJqHuss&ut53O9DYB+)j<8AyyH~ce=)oAzqpQN(NZPO>!hH9L zx^Iai8Z+=@ta3a)a@@_S4NF|ep^cC%rz5yA)6mL1Uo)l4+gPbnvBPj$^Ds9%k^(c( z_3ZRC_5z)YkUH`IG|;h&3~ETyjc}U@59d8C_A7cyy$i!z4rHSvf^D6SR+-2<_S~&J zYBnwy$e~kPG%C5srRMx2*Cln)ZTKpr-kl5D={#(0k&0;Tb~+?l;@IJsqq4E$wRmh0 zmJDi}NXWGrgkvQ-X0CcE&vIT1%;>buC8spVZpgmk?0I$Dtw97GH?y>4^7-dC-UNhicQ;!uZHnlguU7=;*hD5%9+^ z|NQjVZ~y&9e4zjS{P*ww{{Rf200&6G0vhmu2uz>?7YIP<1ut*n0GuH_lsqIY&md8d zLHRbw!44|_4t5bM$Du%nB%{e_3svx-3RlQNAbIW=M?%^nKxDy&t-}W`%%Ki<*c1>l zLRiXUgajGnHyKT01~1^D5|_xtj37g1dnjU6xTK|;2<#6dXrdOk$V2QT278aFpdl6j zxsAYU5;v#-7uU$f4xVoj55t`z_$EU3rGrV82tXV6$j7@u&`)mR9wQWRJwmj=j*Y{_ z7y8J^MncPn9N7cSmgKkslyM`KvjhvM;K)vTazHP9!~(d+2pT-V1rCtoMy_}X4}9{K zu=ESnM)Wb{ECYpWd_fj`z{_6xAPZSIfOWFq0blac1Hr@)F^%a1WC}BuRjQ>l7lB7j zG(e00G8h2_kOYAM{IV}u*Z`7ZFajAo(=Xv1XF1Plkp=|do$!pOJm1Mn8K`lGUYuqv zPqz#tF0leE&>kTmumKOSlOHb#fI#;!f-ICJp$l#3MY6EaLU{9@EPSIr|B=aMY(R+~ zsOT^@;828aQ=~C)WlUah(u$_kBH|P&A!6WzB&x7L8>PzNoPp66QdFkH=xH|s3e-Ks zK!X?|Do~HQj~5iR5F@Z@2O*hLWWbFbMA%^ro@&v3gp{j$2!K@e@l~#hRUbY8>mZ`q z!BAF}UqNxlB3mc}wGu+5-H0hzA%Meu=#{H{^~M3Vs@A}AaF%aH20z;o15UEA0dR`{ z!3KIc0)>_%1_#|mO9vuZUT#3C1KB`kH9OA9`rxxj5^Xois#X>V)pf&5?1&b#kiM?a zvJBe5SZh&%27q=Dw%rDjf;)>B_<*qGaIH6ndkfdV!U@22k^je zhjHHNY1F${Ey*=+%b*zO;{ZN5=|{Oiqw&(>0DqlteQ!}=USL?i8@9y=2EyK2WTCu< z2!MrMhEwl$Ev_c1Ly4z1;(`3v!x7#?NqK?dLUbdo<=8Ke8T4ZiZ{q;+CB%gPcah`d zu9#y~O>DBZvg8f|xg6VlFm|~C*@1Y2wHoF{m&@^GBlF_Q!`QJdUNB%nu;9t}a;tY` zH5xFeumTLaabN06;xY$$#gr3E73*q1+*BH8R9v5Q0>#5POV1@UOzBR#&L23ubJPbX$ht`HDa5r!b)m`wK z5W42_K!S~n9`8ZCc^$}tIoI99dQCT5a4ZL%+Gp!fyBv|OMVkka=stGta#-ZZ(^&S5-~a%l~kLM4OGJf5t_o8I*2Z zK%E!^*GGSc(P*m+-08O1x*@u*i>Vvc8)9d4@FrbL?=5{2C+A?z_fTb8q@6|v@59{d z&W#M`I~RNBhu{Cri@VP}*`tPSRh#p6N*KL-<1V+cO}>qw>qFv)wy@>Bf%$>v{HAul>(=@p^{;5`7>UcbU5}i26zd zpL2$Gb7tpG46*|r)cZK~*qID{eMn#JLNCYTpI;8XOHIx-QF`(JfJ+bJJk+%~fOXeD zcX{KS*t~%K&4;}Y`ICI#ao@$cvAuF>x_$hUP<7>V0ON*!ykK^rrwar~f8H>8@ONS3 z_JFzIfZLFK+|~{D$2mwx6^sXfM+A0Kvw)>mcnnB#X6JjmHhLylg4^(GgW!C*ux*${ zVY}x#Z1)ek~OaD9c~eP-io z2BL$NkVY#6P*k^Ky_bKvpoGJ~0!}x0gfN7(AclrOhTCBOhJ%2Hv|xr=rwfx8R^`)d z|DX(5SP5CRLLwMs$2WJ!mxkkJSh-MgHK>1uxM_%34)*4QhCqdVZ~!Q5HSvFY zI0Y!L)k4fSP?J?%*5!gwn1VFoO~2#=>O~`PXbZ|n2+p`m(a0dv2w*2DQ-cUJ zEY}D*7>twfjjodg-B?j`7=^o7Q6NYQGSH3-^^O)OQwcad8)!1*XbJb|iN&~3l86hR zXjT?6kWY1qyHJMEf4l9HDYkRJ2`4N#NKS5p`v z0~VQxF@cm7#gOSIj|>t3AZa%4R!u%h33kRry)|xQ=mUAjd8Y-HY~>fmwE<%Jjx?t| z-Q-OkfR>8mi;1vUS2+oNxJA2kTJyw9Q@IZnP)rpUPb1(1=HwoIiI;#Wm=Fg|xIk49 zIhU0Xdx{yElIcW_fRc{+2g5j-nz@;^z;9vq`8`(^hXYZ znwT(?tT~%)bSfPMo0G7Tw7Hv&Dlo0Nb>ki0pZS_BxM37nOXmBhK6Tm%58iJX(* yS`{#z)LEU@d7apqo!Ysb+}WMp`JLbyp5i&4 + + + Breaking keyword ciphers + + + + + + + + + + + + + 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-break.html b/slides/keyword-break.html new file mode 100644 index 0000000..49160bb --- /dev/null +++ b/slides/keyword-break.html @@ -0,0 +1,224 @@ + + + + Breaking keyword ciphers + + + + +

+
+# Breaking keyword 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
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+k | e | y | w | o | r | d | a | b | c | f | g | h | i | j | l | m | n | p | q | s | t | u | v | x | z
+
+---
+
+# Duplicate and extend your `affine_break()` function
+
+* How to cycle through all the keys? What _are_ all the keys?
+
+* Look at `words.txt`
+
+---
+
+# Test it. 
+
+* `2013/4a.ciphertext`
+* `2013/4b.ciphertext`
+
+This will take a while. Fire up a system monitor. What's wrong?
+
+---
+
+# Python, threads, and the GIL
+
+Thread-safe shared-memory code is hard.
+
+Python's Global Interpreter Lock prevents shooting yourself in the foot.
+
+Where you want true parallelism, need different threads (Python processes).
+
+* Thread-safe shared-memory code is hard.
+
+The `multiprocessing` library makes this easier.
+
+But before we get there, a couple of diversions...
+
+---
+
+# DRYing code
+
+Three cipher breaking tasks so far.
+
+All working on the same principle:
+
+```
+find a way to enumerate all the possible keys
+initialise 'best so far'
+for each key:
+    decipher message with this key
+    score it
+    if it's better than the best so far:
+        update best so far
+```
+
+Repetition of code is a bad smell.
+
+Separate the 'try all keys, keep the best' logic from the 'score this one key' logic.
+
+---
+
+# map()
+
+A common task is to apply a function to each item in a sequence, returning a sequence of the results.
+
+```python
+def double(x):
+    return x * 2
+
+>>> map(double, [1,2,3])
+[2,4,6]
+```
+
+* `map()` is a higher-order function: its first argument is the function that's applied.
+
+How can we use this for keyword cipher breaking?
+
+---
+
+# Mapping keyword decipherings
+
+Define a function that takes a possible key (keyword and cipher type) and returns the key and its fitness.
+
+* (Also pass in the message and the fitness function)
+
+Use `map()` and `max()` to find the best key
+
+---
+
+# Arity of print()
+
+How many arguments does this take?
+
+How do you write a function that takes this many arguments?
+
+---
+
+# Function arguments
+
+## Positional, keyword
+
+* Common or garden parameters, as you're used to.
+* `def keyword_encipher(message, keyword, Keyword_wrap_alphabet.from_a):`
+
+## Excess positional
+* `def mean(x, *xs):`
+
+First number goes in `x`, remaining go in the tuple `xs`
+
+## Excess keyword
+
+* `def myfunc(arg1=0, **kwargs):`
+
+`kwargs` will be a Dict of the remaining keywords (not `arg1`)
+
+---
+
+# Back to `multiprocessing`
+
+What does `Pool.starmap()` do?
+
+---
+
+```python
+from multiprocessing import Pool
+
+def keyword_break_mp(message, wordlist=keywords, fitness=Pletters, chunksize=500):
+    helper_args = [??? for word in wordlist] # One tuple for each possible key
+    with Pool() as pool:
+        breaks = pool.starmap(keyword_break_worker, helper_args, chunksize) 
+        return max(breaks, key=lambda k: k[1])
+
+def keyword_break_worker(???):
+    ???
+    return (key, fitness)
+```
+
+* Gotcha: the function in `Pool.starmap()` must be defined at the top level
+    * This is definitely a "feature"
+
+---
+
+# Performance and chunksize
+
+Try the multiprocessing keyword break. Is it using all the resources?
+
+Setting `chunksize` is an art.
+
+## Map-reduce as a general pattern for multiprocessing
+
+

+ + + + + + + diff --git a/slides/keyword-encipher.html b/slides/keyword-encipher.html new file mode 100644 index 0000000..168bb5f --- /dev/null +++ b/slides/keyword-encipher.html @@ -0,0 +1,209 @@ + + + + Keyword ciphers + + + + +

+
+# Keyword 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
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+k | e | y | w | o | r | d | a | b | c | f | g | h | i | j | l | m | n | p | q | s | t | u | v | x | z
+
+* Taking a more Pythonic approach
+
+---
+
+# The cipher
+
+* Still character-by-character substitution, still monosubstitution.
+
+Ciphertext alphabet: start with a keyword, write out the rest of the alphabet, removing duplicates.
+
+## Three variants
+
+Write out the rest of the alphabet...
+
+1. ...starting from 'a' (keywordabcf...)
+2. ...starting from the last letter of the keyword (keywordfgh...)
+3. ...starting from the largest letter of the keyword (keywordzabc...)
+
+---
+
+# A more Pythonic way
+
+_string_`.translate()` and _string_`.maketrans()`
+
+* Make the 'ciphertext' alphabet, relate to the 'plaintext' alphabet (`string.ascii_lowercase`)
+* Use those to make the translation table
+* Enciphering is simply applying `plaintext.translate(enciphering_table)`
+* Deciphering just uses a different table
+
+---
+
+# Making the cipher alphabet from a keyword
+
+Three challenges:
+
+1. How to say which type of cipher alphabet to use
+2. Where to start the rest of the alphabet
+3. Removing duplicate letters
+
+Solutions:
+
+1. Keyword arguments for procedures
+2. sort and slices
+3. Use something like an ordered set
+
+Both enciphering and deciphering need the same keyword-based alphabet, so pull this out into another procedure.
+
+---
+
+# Keyword arguments
+
+Used to:
+
+1. give a default value for a parameter
+2. allow parameters to be named (not just positional)
+
+Give our `keyword_encipher` and `keyword_decipher` procedures a keyword parameter of `wrap_alphabet`.
+
+Pass this parameter to the `keyword_alphabet` procedure.
+
+## wrap_alphabet has no inherent meaning
+Use Python 3.4's `Enum`
+```python
+from enum import Enum
+
+class Keyword_wrap_alphabet(Enum):
+    from_a = 1
+    from_last = 2
+    from_largest = 3
+```
+
+(Use integers in earlier Pythons)
+---
+
+# Deduplicating a sequence
+
+We need
+
+* Something set-like
+* Something ordered
+
+No ordered set in Python, but do have an ordered dict.
+
+* Keys of a dict are a set. 
+* Keys in an ordered dict retain their order (subsequent instances are ignored)
+
+`deduplicated_list = list(collections.OrderedDict.fromkeys(list))`
+
+---
+
+# Sorts and slices
+
+## Recap 
+Write out the rest of the alphabet...
+
+1. ...starting from 'a' (keywordabcf...)
+2. ...starting from the last letter of the keyword (keywordfgh...)
+3. ...starting from the largest letter of the keyword (keywordzabc...)
+
+* Santitise the keyword before we use it
+
+---
+# Making the keyword alphabet
+
+## Cases
+1. As we're deduplicating anyway, just add the entire alphabet to the end of the keyword, then deduplicate. 
+`deduplicate(keyword + string.ascii_lowercase)`
+
+2. and 3. How to find the appropriate letter of the keyword.
+
+`deduplicate(keyword + string_ascii_lowercase[from:] + string.ascii_lowercase)`
+
+Question: why not take a slice of the second alphabet copy?
+
+Question: what do we use as the last letter of 'character'? 'r' or 'e'?
+
+`sorted()` will put a string in lexicographical order.
+`.find()` will find an item in a sequence
+
+---
+
+# Keyword enciphering
+
+Now we've got the keyword-based cipher alphabet, simply use `.translate()` to do the enciphering/deciphering.
+
+Use `''.maketrans()` to make the translation table.
+
+Sorted!
+
+Does it pass the tests?
+
+

+ + + + + + + diff --git a/slides/transposition-encipher.html b/slides/transposition-encipher.html new file mode 100644 index 0000000..0c09a4b --- /dev/null +++ b/slides/transposition-encipher.html @@ -0,0 +1,258 @@ + + + + Keyword ciphers + + + + +

+
+# Transposition ciphers
+
+ attack the fort at dawn
+
+ a t t a c
+ k t h e f
+ o r t a t
+ d a w n
+
+ akod ttra aean cft
+
+---
+
+# Transposition ciphers
+
+Rather than changing symbols (substitution ciphers),
+
+Rearrange them.
+
+Still disguises the message.
+
+(Good ciphers do both, and more.)
+
+---
+
+# Scytale
+
+Even older than Caesar cipher.
+
+* Wrap a strip round a pole
+* Write the message along it
+* Unwind the strip
+* "Unreadable" unless reader has pole of same diameter
+
+ attack the fort at dawn
+
+ a t t a c
+ k t h e f
+ o r t a t
+ d a w n
+
+ akod ttra aean cft
+
+---
+
+# Generalising: column transposition ciphers
+
+Scytale essentially fills a grid by rows, then reads it by columns
+
+* (Deciphering is the reverse)
+
+Column transposition ciphers:
+
+* Fill a grid
+* Reorder columns based on keyword
+* Read the grid (perhaps different direction)
+
+Scytale is just a special case of column transposition.
+
+---
+
+# Grids and data structures
+
+How to represent a grid?
+
+What operations do we need to do on it?
+
+---
+
+# Grids and data structures
+
+How to represent a grid?
+
+* List of strings
+* Each row is a string
+* Rows in order in the list
+
+What operations do we need to do on it?
+
+* Fill, by rows or columns
+* Empty, by rows or columns
+* Rearrange columns
+* Calculate the size of the grid
+* Pad message to fit a rectangle of the required size
+
+---
+
+# Finding sizes
+
+Know number of columns
+
+Number of rows = ceiling(message length / columns)
+
+Paddding is (rows * columns) - message length
+
+* What to use as default padding? 
+* Keyword parameter!
+
+## Fit 'thequickbrownfox' (16 letters) into grid of 
+
+* 4 columns
+* 5 columns
+
+---
+
+# Fill and empty grid by rows
+
+Split message into row-sized chunks
+
+* slices and ranges
+
+Append all the rows together
+
+* `<string>.join()`
+
+Keep thinking about test cases!
+
+---
+
+# Fill and empty grid by columns
+
+Idea: fill and empty by rows, with a transposition.
+
+`zip(*rows)` and `itertools.zip_longest(*rows)`
+
+---
+
+# Swapping columns
+
+How to represent a transposition (_permutation_, to mathematicians)?
+
+How to create it from a keyword?
+
+---
+
+# Idea of a transposition
+
+Says, for each element, where it should go
+
+```
+0 1 2 3 4 5 6
+t r e a s o n
+
+a e n o r s t 
+3 2 6 5 1 4 0
+```
+
+The transposition `(3, 2, 6, 5, 1, 4, 0)` says that what was in position 3 moves to position 0, what was in position 2 moves to position 1, what was in position 6 moves to position 2, ...
+
+`enumerate(_iterable_)` yields an iterator that walks over the iterator, including the element indexes.
+
+```python
+>>> [i for i in enumerate('treason')]
+[(0, 't'), (1, 'r'), (2, 'e'), (3, 'a'), (4, 's'), (5, 'o'), (6, 'n')]
+>>> [i for i in enumerate((3, 2, 6, 5, 1, 4, 0))]
+[(0, 3), (1, 2), (2, 6), (3, 5), (4, 1), (5, 4), (6, 0)]
+```
+
+Write the `transpose` and `untranspose` functions.
+
+---
+
+# Transposition from a keyword
+
+Deduplicate the keyword
+
+Sort it
+
+Use `<iterable>.index()` to find the positions of the letters in the sorted keyword
+
+---
+
+# Transposition ciphers
+
+Put it all together 
+
+---
+
+# Masking the fill characters
+
+Padding characters can be distinctive.
+
+Make a function that generates a random letter, based on the `normalised_english_counts`
+
+Use `callable()` to check if the `fillvalue` should be called or just inserted
+
+

+ + + + + + + diff --git a/slides/word-segmentation.html b/slides/word-segmentation.html new file mode 100644 index 0000000..16fcb0a --- /dev/null +++ b/slides/word-segmentation.html @@ -0,0 +1,370 @@ + + + + Word segmentation + + + + + +

+
+# Word segmentation
+
+`makingsenseofthis`
+
+`making sense of this`
+
+---
+
+# The problem
+
+Ciphertext is re-split into groups to hide word bounaries.
+
+* HELMU TSCOU SINSA REISU PPOSE KINDI NTHEI ROWNW AYBUT THERE ISLIT TLEWA RMTHI NTHEK INDNE SSIRE CEIVE 
+
+How can we rediscover the word boundaries?
+
+* helmut s cousins are i suppose kind in their own way but there is little warmth in the kindness i receive
+
+---
+
+# Simple approach
+
+1. Try all possible word boundaries
+2. Return the one that looks most like English
+
+What's the complexity of this process?
+
+* (We'll fix that in a bit...)
+
+---
+
+# What do we mean by "looks like English"?
+
+NaÃ¯ve Bayes bag-of-words worked well for cipher breaking. Can we apply the same intuition here?
+
+Probability of a bag-of-words (ignoring inter-word dependencies).
+
+Finding the counts of words in text is harder than letters.
+
+* More tokens, so need more data to cover sufficient words.
+
+---
+# Data sparsity and smoothing
+
+`counts_1w.txt` is the 333,333 most common words types, with number of tokens for each, collected by Google.
+
+Doesn't cover a lot of words we want, such as proper nouns.
+
+We'll have to guess the probability of unknown word.
+
+Lots of ways to do this properly (Laplace smoothing, Good-Turing smoothing)...
+
+...but we'll ignore them all.
+
+Assume unknown words have a count of 1.
+
+---
+
+# Storing word probabilities
+
+We want something like a `defaultdict` but with our own default value
+
+Subclass a dict!
+
+Constructor (`__init__`) takes a data file, does all the adding up and taking logs
+
+`__missing__` handles the case when the key is missing
+
+
+```python
+class Pdist(dict):
+    def __init__(self, data=[]):
+        for key, count in data2:
+            ...
+        self.total = ...
+    def __missing__(self, key):
+        return ...
+
+Pw = Pdist(data...)
+
+def Pwords(words):
+    return ...
+```
+
+---
+
+# Testing the bag of words model
+
+
+```python
+>>> 'hello' in Pw.keys()       >>> Pwords(['hello'])
+True                           -4.25147684171819
+>>> 'inigo' in Pw.keys()       >>> Pwords(['hello', 'my'])
+True                           -6.995724679281423
+>>> 'blj' in Pw.keys()         >>> Pwords(['hello', 'my', 'name'])
+False                          -10.098177451501074
+>>> Pw['hello']                >>> Pwords(['hello', 'my', 'name', 'is'])
+-4.25147684171819              -12.195018236240843
+>>> Pw['my']                   >>> Pwords(['hello', 'my', 'name', 'is', 'inigo'])
+-2.7442478375632335            -18.927603013570945
+>>> Pw['name']                 >>> Pwords(['hello', 'my', 'name', 'is', 'blj'])
+-3.102452772219651             -23.964487301167402
+>>> Pw['is']                   
+-2.096840784739768             
+>>> Pw['blj']                  
+-11.76946906492656
+```
+
+---
+
+# Splitting the input
+
+```
+To segment a string:
+    find all possible splits into a first portion and remainder
+    for each split:
+        segment the remainder
+    return the split with highest score
+```
+
+Indexing pulls out letters. `'sometext'[0]` = 's' ; `'keyword'[3]` = 'e' ; `'keyword'[-1]` = 't'
+
+Slices pulls out substrings. `'keyword'[1:4]` = 'ome' ; `'keyword'[:3]` = 'som' ; `'keyword'[5:]` = 'ext'
+
+`range()` will sweep across the string
+
+## Test case
+
+```python
+>>> splits('sometext')
+[('s', 'ometext'), ('so', 'metext'), ('som', 'etext'), ('some', 'text'), 
+ ('somet', 'ext'), ('somete', 'xt'), ('sometex', 't'), ('sometext', '')]
+```
+
+The last one is important
+
+* What if this is the last word of the text?
+
+---
+
+# Effeciency and memoisation
+
+* helmut s cousins are i suppose kind in their own way but there is little warmth in the kindness i receive
+
+At any stage, can consider the sentence as prefix, word, suffix
+
+* `littlewarmthin | the | kindness i receive`
+* `littlewarmthi | nthe | kindness i receive`
+* `littlewarmth | inthe | kindness i receive`
+* `littlewarmt | hinthe | kindness i receive`
+
+P(sentence) = P(prefix) Ã P(word) Ã P(suffix)
+
+* We're assuming independence of sections.
+* For a given word/suffix split, there is only one best segmentation of the suffix.
+* Best segmentation of sentence (with split here) must have the best segmentation of the suffix.
+* Once we've found it, no need to recalculate it.
+
+## What's the complexity now?
+
+---
+
+# Memoisation
+
+* Maintain a table of previously-found results
+* Every time we're asked to calculate a segmentation, look in the table.
+* If it's in the table, just return that.
+* If not, calculate it and store the result in the table.
+
+Wrap the segment function in something that maintains that table.
+
+In the standard library: `lru_cache` as a function decorator.
+
+```python
+from functools import lru_cache
+
+@lru_cache()
+def segment(text):
+    ...
+```
+* (Plenty of tutorials online on function decorators.)
+
+---
+
+# Implmentation detail
+
+You'll hit Python's recursion level limit.
+
+Easy to reset:
+
+```python
+import sys
+sys.setrecursionlimit(1000000)
+```
+
+---
+
+# Testing segmentation
+
+```python
+>>> segment('hello')
+['hello']
+>>> segment('hellomy')
+['hello', 'my']
+>>> segment('hellomyname')
+['hello', 'my', 'name']
+>>> segment('hellomynameis')
+['hellomynameis']
+```
+
+Oh.
+
+Why?
+
+---
+
+# A broken language model
+
+```python
+>>> Pwords(['hello'])
+-4.25147684171819
+>>> Pwords(['hello', 'my'])
+-6.995724679281423
+>>> Pwords(['hello', 'my', 'name'])
+-10.098177451501074
+>>> Pwords(['hello', 'my', 'name', 'is'])
+-12.195018236240843
+
+>>> Pw['is']                   
+-2.096840784739768             
+>>> Pw['blj']                  
+-11.76946906492656
+```
+
+Need a better estimate for probability of unknown words.
+
+Needs to take account of length of word.
+
+* Longer words are less probable.
+
+## To IPython for investigation!
+
+---
+
+# Making Pdist more flexible
+
+Want to give a sensible default for unknown elements
+
+* But this will vary by referent
+* Different languages, *n*-grams, etc. 
+
+Make it a parameter!
+
+---
+
+# Hint
+
+```python
+class Pdist(dict):
+    def __init__(self, data=[], estimate_of_missing=None):
+        for key, count in data2:
+            ...
+        self.total = ...
+    def __missing__(self, key):
+        if estimate_of_missing:
+            return estimate_of_missing(key, self.total)
+        else:
+            return ...
+
+def log_probability_of_unknown_word(key, N):
+    return -log10(N * 10**((len(key) - 2) * 1.4))
+
+Pw = Pdist(datafile('count_1w.txt'), log_probability_of_unknown_word)            
+```
+
+---
+
+# Testing segmentation again
+
+```python
+>>> segment('hello')
+['hello']
+>>> segment('hellomy')
+['hello', 'my']
+>>> segment('hellomyname')
+['hello', 'my', 'name']
+>>> segment('hellomynameis')
+['hello', 'my', 'name', 'is']
+>>> ' '.join(segment(sanitise('HELMU TSCOU SINSA REISU PPOSE KINDI NTHEI ROWNW '
+                              'AYBUT THERE ISLIT TLEWA RMTHI NTHEK INDNE SSIRE CEIVE ')))
+'helmut s cousins are i suppose kind in their own way but there is 
+ little warmth in the kindness i receive'
+```
+
+Try it out on the full decrypt of `2013/2b.ciphertext` (it's a Caesar cipher)
+
+
+

+ + + + + + + -- 2.34.1