Frequency Analysis

Chi-square comparison with English

χ² = —

χ² = Σ (O_i − E_i)² / E_i, where O_i is the count of a letter and E_i = N × its typical English frequency. A lower value means the letter counts are closer to the reference table, not that the text is English. The value grows with the length of the text, so compare it only between texts of similar length.

N-gram boundaries

Count n-grams within words only

Unchecked, spaces and punctuation are removed first, so THE END also gives the digram EE. Checked, an n-gram must lie inside one unbroken run of letters, and the percentages are taken of the windows that do. The letter counts are the same either way.

Friedman estimate

Friedman estimate: —

This is a rough estimate, not a recovered key length.

k ≈ N(I_E − I_R) / [(N − 1)(IC − I_R) + (I_E − I_R)]

Here IC is the overall index of coincidence, N the number of letters, I_E = 0.066 and I_R = 1/26. The formula assumes English plaintext, a repeating key whose letters are unrelated to one another, and columns of equal length. It reads “No stable estimate” for fewer than 50 letters, when the IC is at or below the uniform value, and when the result would leave fewer than 20 letters per column or exceed 50.

Key-length range

From 2 to 50. Longer keys mean shorter columns: a bar is striped when one of its columns has fewer than 20 letters, which is a rule of thumb for “too few to compare”, not a threshold with a guarantee.

Shift coincidence

Slide the text along itself by s places and count the positions where the two copies agree: M(s) = matches / (N − s). This is related to the index of coincidence but is not one. Under a repeating key, shifts that are multiples of the key length tend to agree more often; ordinary English also agrees a little more at some small shifts, with no key involved.

Show shift coincidence

Shift	Compared	Matches	M(s)

What is counted

Letter frequency measures how often each letter appears. An n-gram frequency counts overlapping runs of n neighbouring letters (digrams, trigrams, and so on up to 6): the window moves one letter at a time. Each percentage is a count divided by the number of windows of that size, and a text of N letters has max(0, N − n + 1) of them.

ABABA  →  letters A = 3, B = 2  ·  digrams AB = 2, BA = 2  ·  trigrams ABA = 2, BAB = 1  ·  4-grams ABAB = 1, BABA = 1

What n-grams add

AABB and ABAB have the same letter counts, and therefore the same index of coincidence and the same entropy. Their digrams differ: AABB has AA, AB, BB and ABAB has AB, BA, AB. Single-letter statistics cannot tell the order of the letters; n-grams can, which is why a transposition changes them while leaving every letter count alone.

Shannon entropy

H = −Σ p_i log₂(p_i)

Entropy measures the uncertainty in the letter distribution, with p_i = n_i/N; it is always taken over single letters, whichever n-gram is charted. A text made of a single letter has entropy 0. Twenty-six equally frequent letters give the maximum, log₂(26) ≈ 4.70 bits per letter. It does not measure cryptographic security: a Caesar ciphertext has exactly the entropy of its plaintext.

The English reference

“Compare with English” and the chi-square statistic use one table of 26 letter frequencies: the conventional table reproduced in most cryptography texts, with the values given in Lewand, Cryptological Mathematics (2000), rounded to two decimals (E 12.70%, T 9.06%, A 8.17%, …). It is a typical profile, not an exact law: frequencies vary with the corpus, the genre, the length of the sample and the language. N-grams are shown without a reference.

Limitations

Frequency analysis is statistical evidence, not a guaranteed decryption method. It is weakened by:

• very short messages, unusual vocabulary and names;
• text that is not English;
• letter distributions that were manipulated on purpose;
• polyalphabetic encryption and block transformations.

What the index of coincidence measures

IC = Σ n_i(n_i − 1) / [N(N − 1)]

Here n_i is the count of each letter and N the number of letters. The IC is the probability that two distinct positions, chosen at random without replacement, hold the same letter. It needs at least two letters. Letters drawn evenly and independently give about 1/26 ≈ 0.0385; typical English gives about 0.066. These are reference points, not boundaries: a short sample can land far from either.

Why substitutions and transpositions preserve it

AAABBC  →  A = 3, B = 2, C = 1  →  IC = [3·2 + 2·1 + 1·0] / [6·5] = 8/30 ≈ 0.2667

The formula uses the counts only, not which letter has which count or where the letters stand. Any rearrangement of these six letters (CABABA, say) has the same IC, and so does any one-to-one replacement of the alphabet (XXXQQM): both keep the list of counts 3, 2, 1.

Why Vigenère changes it, and periodic columns

A Vigenère key of length k uses k Caesar shifts in turn. Mixing several shifted alphabets tends to even out the overall letter counts, so the overall IC may fall towards 0.0385. But the letters at positions j, j + k, j + 2k, … were all shifted by the same amount: each such column is a Caesar ciphertext, and its IC may resemble that of English. The chart splits the text into k columns for every suspected k and shows the average IC of the columns.

The average is weighted by pairs: the equal pairs of all columns divided by all their pairs, Σ_j Σ_i n_ij(n_ij − 1) / Σ_j n_j(n_j − 1). A column of fewer than two letters has no IC and is left out. The column details also give the plain average of the column values.

Peaks at multiples

If the true period is 5, then splitting into 10, 15 or 20 columns also puts letters of one shift together, so those lengths may score high as well. The highest bar therefore does not identify the key length, and the shortest of a family of peaks is usually the one to examine first. This page points out lengths worth a look; it does not name a key length.

Limits of key-length estimates

• Short columns vary a lot: with a few dozen letters, a column of random letters can score like English and the reverse.
• The references assume English. Other languages, and text without ordinary vocabulary, have other values.
• A high IC at every length, including 1, points to no period at all: a plaintext, a monoalphabetic substitution or a transposition.
• Ciphers that are not periodic substitutions (Playfair, Hill, running keys) are not described by this picture.

About the Vigenère example

The example was encrypted with the keyword LEMON, of length 5. Its chart also rises at 10, 15 and 20.

What each cipher does to the statistics

“Preserved” assumes that only letters are encrypted and none are added: padding a transposition with extra letters changes the counts. A transposition keeps the IC and the entropy but generally changes the n-grams. Encryption does not have to lower the IC: the first five ciphers leave it exactly as it was.