Keyword ciphers

From: Neil Smith Date: Sat, 5 Jul 2014 13:12:19 +0000 (+0100) Subject: Done transposition slides X-Git-Url: https://git.njae.me.uk/?p=cipher-training.git;a=commitdiff_plain;h=00bd8aa9109f421a9fda6bdc5cb4c1fb33bc79c6 Done transposition slides --- diff --git a/language_models.py b/language_models.py index 52e7ac4..59d8588 100644 --- a/language_models.py +++ b/language_models.py @@ -123,6 +123,7 @@ Pw = Pdist(datafile('count_1w.txt'), log_probability_of_unknown_word) Pw_wrong = Pdist(datafile('count_1w.txt'), lambda _k, N: log10(1/N)) Pl = Pdist(datafile('count_1l.txt'), lambda _k, _N: 0) P2l = Pdist(datafile('count_2l.txt'), lambda _k, _N: 0) +P3l = Pdist(datafile('count_3l.txt'), lambda _k, _N: 0) def Pwords(words): """The Naive Bayes log probability of a sequence of words. @@ -146,6 +147,12 @@ def Pbigrams(letters): """ return sum(P2l[p] for p in ngrams(letters, 2)) +def Ptrigrams(letters): + """The Naive Bayes log probability of the trigrams formed from a sequence + of letters. + """ + return sum(P3l[p] for p in ngrams(letters, 3)) + def cosine_similarity_score(text): """Finds the dissimilarity of a text to English, using the cosine distance diff --git a/slides/index.html b/slides/index.html new file mode 100644 index 0000000..dad47e7 --- /dev/null +++ b/slides/index.html @@ -0,0 +1,83 @@ + + + + Keyword ciphers + + + + + + + + + + + + diff --git a/slides/transposition-break.html b/slides/transposition-break.html new file mode 100644 index 0000000..5d8202a --- /dev/null +++ b/slides/transposition-break.html @@ -0,0 +1,157 @@ + + + + Keyword ciphers + + + + +

+
+# Breaking 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
+
+Generally quite familiar...
+
+## Try all the keys, pick the one that looks most like Englilsh
+
+---
+
+# ...Pick one that looks most like English
+
+But the naÃ¯ve Bayes score will always be the same!
+
+* Same letters, just a different order.
+
+Score by probability of substrings of letters
+
+* Bigrams, trigrams, _n_-grams
+
+---
+
+# Finding _n_-grams
+
+Given `count_2l.txt` and `count_3l.txt`, counts of bigrams and trigrams in English
+
+# Write a function that returns all the _n_-grams for a text, given _n_
+    * Assume the text is already sanitised
+
+# Build `P2l`, `P3l` (after `Pl`), `Pbigrams`, `Ptrigrams` (after `Pletters`)
+
+---
+
+# Breaking scytale
+
+What are the possible keys? 
+
+---
+
+# Try all the keys...
+
+*All* the keys?
+
+What's the transposition of 'cat'?
+
+* 'bat'?
+* 'car'?
+* 'wry'?
+* 'babe'?
+* 'powwow'?
+
+---
+
+# Equivalence classes and canonical forms
+
+Lots of words yield the same transposition
+
+* They're all in the same equivalence class
+* Only need to test one from the class
+
+General idea: if there are different ways to represent something, pick one to make comparisons easier
+
+* Canonical form, canonical representation
+
+---
+
+# Finding the transpositions to try
+
+```
+For each word:
+    if it's a new transposition:
+        add it to the list
+```
+
+What data structure to use to store the transpositions?
+
+
+

+ + + + + + + + diff --git a/slides/transposition-encipher.html b/slides/transposition-encipher.html index 0c09a4b..2fea8e3 100644 --- a/slides/transposition-encipher.html +++ b/slides/transposition-encipher.html @@ -223,6 +223,20 @@ Put it all together --- +# Back to the scytale + +Key is number of rows. + +No transposition of columns. + +* What does a null transposition look like? + +How to fill and empty? + +(Transposing the grid is easier) + +--- + # Masking the fill characters Padding characters can be distinctive.