Matching the distribution of English characters under two distributions

Question

I'm working on some cryptography homework and part of it is to do statistical analysis on the ciphered text and based on the letter frequencies of the ciphered text, match them to the proper English letters. So if 'w' is the most frequent letter in the ciphered text, it was likely 'e' in the original text, given that 'e' is the most frequent letter of the English language.

I'm currently matching it in order, such that I sort both lists and match them in the order of their probability. This works for the most frequent letters, but as the list goes on, where some letters have very similar probabilities, this approach fails.

Is there a better approach to this?

Answer 1

The general statistics give you a the probability $p_l$ for $l \in \{a,\dots,b\}$ that a certain letter occurs. Your text is a sample of a multinomial distribution of letters for the number of occurences of a letter $n_l$ with probability $\mathbb P(n_{\sigma(a)},\dots,n_{\sigma(z)|p_a,\dots,p_z})$. $\sigma$ is the permutation/encryption that maps a the encrypted letter to the original one. There are $26!$ permutations you could test for. Since the most frequent letters can be identified quiet easily, thous should be fixed to reduce this number. Then you could have a computer sample permutations with high probability with e.g. Metropolis Hastings and look for words that occur in a dictionary.

But it might be faster to look for recognizable patterns after substituting the obvious candidates per hand and continue the substitution until everything is resolved.

Answer 2

Use first-order statistics (frequencies of individual letters) for the most-frequent letters, then use second-order statistics (frequencies of ordered letter pairs) for the rest. That is, once you've identified (and eliminated) as many letters as you can based on frequency, take all ${k \choose 2} = k \cdot (k-1)$ ordered pairs of the remaining letters. Find the most frequent pair

Alternatively (or additionally) go to second-order statistics based on the identified letters. Suppose, for instance, you know that $b$ in the cypher text corresponds to $q$ in the (decrypted) plain text. Use known pair frequencies in plain text to find the most-frequent letter paired after $q$: certainly it is $u$. So test whether the most-frequent letter following $b$ in the cypher text could correspond to $u$ in plain text.

You can use the above approach for letter pairs in which the last (or second) letter in the pair is one found through the first-order method you know well.