Letter frequency analysis

What is going on here?

In every language, letters appear with a fixed, characteristic frequency. In Polish the most frequent are A, I, O, E, in English E, T, A. This “signature” of a language is very robust — a few hundred characters are enough for it to show.

Relative letter frequency:

where $n_i$ is the number of occurrences of the letter and $N$ — the total number of letters in the text. The set of values $\{f_i\}$ is exactly the frequency distribution that we draw as a histogram.

Why does this break a substitution cipher?

A substitution cipher replaces each letter with another fixed symbol (here: a shift of $s$ positions). This is only a relabelling — the letter assigned to a symbol still occurs just as often:

That is why the ciphertext histogram has exactly the same shape as the plaintext histogram — only shifted and relabelled. The most frequent ciphertext symbol almost certainly corresponds to the most frequent letter of the language. Matching the tallest bars reveals the substitution.

The invariant:

Substitution preserves the frequency distribution — it only changes the names of the symbols. The shape of the histogram is invariant under substitution, and it is the shape, not the text length, that gives the cipher away.

A bit of history:

Frequency analysis was described as early as the 9th century by the Arab scholar al-Kindi in a treatise on reading encrypted messages — the first known account of cryptanalysis. The same idea later broke the famous Vigenère cipher and still forms the foundation of classical cryptanalysis.

Why you need this for the exam:

Frequency analysis is a flagship example that information can “leak” even through a seemingly secure cipher. The trick: look for what a transformation leaves unchanged — the invariant. Here it is the frequency distribution.

Remember: substitution shuffles labels but not frequencies — the most frequent cipher symbol is the most frequent letter of the language.