Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

First post on Crypto SE, so I've attempted to search the term "English" and looked through the first 10 pages of results, to see if this was a common question, I couldn't find a suitable answer.

I'm currently attempting the Matasano Crypto Challenges as a basic intro to cryptography. For solving some of the earlier challenges I utilised n-grams to determine which is going to be the most likely English plain text. It has been quite successful.

I'm up to attempting to break repeating XOR, which involves grouping bytes in their suspected single byte XOR group, and cracking them in this fashion. As this will be disjointed text, it appears I will need to use frequency analysis as opposed to n-grams.

I implemented a basic scoring system (similar to the below source code) source.

function getEntropy(str) {
    var sum = 0;
    var ignored = 0;
    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if      (c >= 65 && c <=  90) sum += Math.log(ENGLISH_FREQS[c - 65]);  // Uppercase
        else if (c >= 97 && c <= 122) sum += Math.log(ENGLISH_FREQS[c - 97]);  // Lowercase
        else ignored++;
    return -sum / Math.log(2) / (str.length - ignored);

With short cipher texts though I've had the issue that garbled text with more printable ASCII has scored higher than correctly formed English. I.e. FKDASDOFD may score higher than THE RIVER, as it's got a space which isn't counted towards its score.

From this, I've been trying to come up with a way of perhaps scoring the letter count against it's expected frequency, while penalising the score for each letter the further it is away from it's expected value according to normal distribution.

For example, a very rough though process of algorithm I'm trying to implement.

1) "a" has a frequency of 8.167%. 
2) Evaluate the frequency in the candidate plain text and compare that      against the expected value (8.167%). 
3) Penalise the 'score' by multiplying it by [1-(std dev cumulative prob)]. For example if it was 1 std dev away from expected, multiply the score by [1-0.68], 3 std deviations, [1-0.997], etc.
4) Add the cumulative score for each letter to evaluate the most likely plain text. 

My questions are.

  1. Is there a better, established, algorithm out there for performing frequency analysis?
  2. Is it simply the nature of short cipher / plain texts that there will be inherent inaccuracy in evaluating the probability of English plain text?
  3. Is my proposed method ridiculous / naive / stupid in some way?

Thanks folks, attempting to learn so sorry if there are trivial mistakes or invalid assumptions in this question.

share|improve this question
Your metric is maximized with eeeeeee.... Perhaps it would be best to calculate the sample frequency of each letter and compare those to the expected frequencies. – otus Oct 31 at 6:31

2 Answers 2

up vote 4 down vote accepted

As otus suggests in the comments, it's better to first calculate the frequency of each letter in the decrypted message, and then compare the frequency distribution to what would be expected for English text.

For the comparison, you can use chi-squared ($\chi^2$) testing. (Actually, for just comparing the likelihoods of different decryptions, you don't even need the complete test.) To do this, start by comparing the actual observed number of occurrences $N_{\rm obs}(c)$ of each character $c$ in the decrypted message with the expected number of occurrences $N_{\rm exp}(c)$ of that character in a piece of English text of the same length (i.e. its expected frequency times the length of the message), and calculate the test statistic $$\chi^2 = \sum_c \frac{\left( N_{\rm obs}(c) - N_{\rm exp}(c) \right)^2}{N_{\rm exp}(c)},$$ i.e. the sum of the squared differences between the observed and the expected frequency, divided by the expected frequency. The smaller this $\chi^2$ is, the more closely the decrypted message resembles English.*

Here's some basic JS code to calculate $\chi^2$ for English ASCII text:

var english_freq = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,  // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,  // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,  // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074                     // V-Z

function getChi2 (str) {
    var count = [], ignored = 0;
    for (var i = 0; i < 26; i++) count[i] = 0;

    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if (c >= 65 && c <= 90) count[c - 65]++;        // uppercase A-Z
        else if (c >= 97 && c <= 122) count[c - 97]++;  // lowercase a-z
        else if (c >= 32 && c <= 126) ignored++;        // numbers and punct.
        else if (c == 9 || c == 10 || c == 13) ignored++;  // TAB, CR, LF
        else return Infinity;  // not printable ASCII = impossible(?)

    var chi2 = 0, len = str.length - ignored;
    for (var i = 0; i < 26; i++) {
        var observed = count[i], expected = len * english_freq[i];
        var difference = observed - expected;
        chi2 += difference*difference / expected;
    return chi2;

If you're only interested in finding the most likely decryption(s), that's all you need to do. Just sort the decryptions (and corresponding candidate keys) by $\chi^2$ in increasing order, and print out the first few entries.

If you also wish to estimate the actual likelihood of the message being English (or, rather, the likelihood that picking random letters with frequencies matching English text could yield such a message), you'll also need to determine the number of degrees of freedom $k$ for the model (which, for a simple model like this, is simply the size of the plaintext alphabet minus one**) and then integrate the chi-squared distribution for $k$ degrees of freedom up to $\chi^2$ (or just compare it to a precalculated table). But just for comparing the likelihood of different decryptions, the raw $\chi^2$ value is enough.

*) You have to calculate this sum over all the letters in the alphabet, including those that don't actually occur in the message, for which $N_{\rm obs}(c)$ simply equals $0$. Conversely, any characters that don't occur in your frequency table would, in principle, have $N_{\rm exp}(c) = 0$, and thus yield $\chi^2 = \infty$ if they occur in the message. In practice, to avoid such infinite results, you may wish to either ignore such characters or assign them some more or less arbitrary small frequency. One reasonable choice, if you're compiling your own frequency tables from a corpus of text, is to use additive smoothing by incrementing the observed count of each character in the corpus by one.

**) The one degree of freedom is lost because the sum of the character counts must obviously equal the length of the message, which is fixed a priori. Thus, we're not completely free to choose how many times each character occurs in the message; having chosen all but one of the counts, the last count is unique determined by the others.

share|improve this answer

you could also use some grammar to eliminate false positives, for example, in portuguese, before the letter "p" or "b" there should be a "m" and after the letter "q" there is always a "u", after the letter "l" it will be a vogal or the letter "h".

There are patterns like these in english, i just can't seem to remember now xD

share|improve this answer
This is essentially what the OP did before, using $n$-gram frequencies. Alas, if one is only looking at every $k$-th letter in the text, for $k \ge 2$, such pairwise correlations are not very useful. – Ilmari Karonen Nov 2 at 22:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.