Cryptanalysis of Classical Ciphers

Cryptanalysis is the study of recovering plaintext or key from ciphertext without legitimate access to the key. Classical cryptanalysis of substitution and polyalphabetic ciphers rests on a single observation: natural language is redundant. English text is not a uniform random sequence over 26 letters; it has a highly skewed letter-frequency distribution, characteristic digrams and trigrams ("TH", "THE", "ING"), and repeated words. A cipher is secure against statistical attack only if it destroys this redundancy in the ciphertext; classical ciphers do not. A monoalphabetic substitution cipher applies a single fixed bijection $\pi$ from the plaintext alphabet to itself: every occurrence of a plaintext letter $p$ maps to the same ciphertext letter $\pi(p)$. Because $\pi$ is a bijection, the multiset of letter frequencies is merely permuted, not altered. If 'E' is the most common plaintext letter, then $\pi(E)$ will be the most common ciphertext letter. This is the invariant frequency analysis exploits. A polyalphabetic cipher such as Vigenère uses a repeating key of length $m$: the $i$-th plaintext letter is shifted by the key letter at position $i \bmod m$. This appears to defeat frequency analysis, since the same plaintext letter can map to $m$ different ciphertext letters depending on position. But the key repeats with period $m$, so the sub-sequence of ciphertext letters at positions $i, i+m, i+2m, \dots$ was all encrypted with the same Caesar shift — it is monoalphabetic. Kasiski examination locates the period $m$ by finding repeated plaintext patterns (which, because of the periodic key, produce repeated ciphertext patterns separated by multiples of $m$). The index of coincidence provides an independent, frequency-based estimate of $m$. Once $m$ is known, the ciphertext splits into $m$ Caesar ciphers, each breakable by ordinary frequency analysis.

Part 1 — Frequency analysis of monoalphabetic substitution. The attacker has ciphertext $C$ and a reference frequency table for the assumed plaintext language (e.g., standard English single-letter, digram, and trigram frequencies). The attack proceeds as a constrained search guided by statistics rather than brute force over all $26!$ keys. ``` ALGORITHM FrequencyAnalysis(ciphertext C, reference_freqs R) // Step 1: Tabulate ciphertext statistics count[26] <- 0 for each letter c in C: count[index(c)] <- count[index(c)] + 1 n <- length(C) freq[i] <- count[i] / n for i in 0..25 // Step 2: Rank letters by frequency ciphertext_rank <- sort letters 0..25 by freq[] descending reference_rank <- sort letters by R[] descending // e.g. E,T,A,O,I,N,S,H,R,D,L,U,... // Step 3: Initial guess -- align ranks mapping <- {} for i in 0..25: mapping[ciphertext_rank[i]] <- reference_rank[i] // Step 4: Refine using digram/trigram and structural evidence repeat candidate_plain <- apply(mapping, C) score <- LanguageScore(candidate_plain, R) // log-likelihood vs reference n-grams for each pair of letters (a, b) in mapping's range: trial_mapping <- swap(mapping, a, b) trial_plain <- apply(trial_mapping, C) trial_score <- LanguageScore(trial_plain, R) if trial_score > score: mapping <- trial_mapping score <- trial_score improved <- true until no improvement in a full pass over all swaps return mapping, apply(mapping, C) ``` The initial rank-alignment step (Step 3) is usually wrong in detail — English frequency order is a statistical tendency, not a law, and short ciphertexts especially will deviate. The refinement loop (Step 4) is a local-search (hill-climbing) step over the space of letter-swaps, scored against a language model, typically using single-letter frequencies plus digram/trigram frequencies or common short words ("THE", "AND", "TO") as anchors. A human cryptanalyst does this by hand, using distinctive patterns: doubled letters, a lone one-letter word (almost certainly "A" or "I" in English), and word-boundary shapes if spacing survives.

Part 2 — Kasiski examination and the index of coincidence for Vigenère. Kasiski's method exploits the fact that identical plaintext substrings encrypted at positions that differ by a multiple of the key length $m$ produce identical ciphertext substrings. ``` ALGORITHM KasiskiExamination(ciphertext C, min_len = 3) distances <- [] // Step 1: find repeated substrings of length >= min_len positions <- map from substring -> list of start indices for i in 0 .. length(C) - min_len: s <- C[i .. i+min_len-1] append i to positions[s] // Step 2: collect pairwise distances between repeats of the same substring for each substring s with positions list P where |P| >= 2: for each pair (p1, p2) in P, p1 < p2: distances.append(p2 - p1) // Step 3: candidate key length = a common divisor of many distances candidates <- {} for d in distances: for f in factors(d): if f >= 2: candidates[f] <- candidates[f] + 1 m_guess <- argmax_f candidates[f] // most frequently occurring factor return m_guess ``` ``` ALGORITHM IndexOfCoincidence(text T) n <- length(T) count[26] <- letter counts in T IC <- sum over i of count[i](count[i]-1) / (n(n-1)) return IC ALGORITHM ConfirmKeyLength(ciphertext C, max_m) best_m, best_score <- 1, -infinity for m in 1 .. max_m: avg_IC <- 0 for j in 0 .. m-1: subsequence <- C[j], C[j+m], C[j+2m], ... avg_IC <- avg_IC + IndexOfCoincidence(subsequence) avg_IC <- avg_IC / m // English monoalphabetic IC ~ 0.065-0.070; random ~ 0.038 score <- -(avg_IC - 0.0665)^2 if score > best_score: best_m, best_score <- m, avg_IC return best_m ``` ``` ALGORITHM BreakVigenere(ciphertext C) m <- KasiskiExamination(C) // or ConfirmKeyLength(C, max_m) key <- array of length m for j in 0 .. m-1: subsequence <- C[j], C[j+m], C[j+2m], ... // monoalphabetic (Caesar) slice best_shift, best_score <- 0, -infinity for shift in 0 .. 25: decrypted <- ShiftBack(subsequence, shift) score <- ChiSquaredFit(decrypted, EnglishFrequencies) // lower is better -> use -score if -score > best_score: best_shift, best_score <- shift, -score key[j] <- best_shift plaintext <- decrypt C using repeating key `key` return key, plaintext ``` The chi-squared statistic in the innermost loop compares the observed letter distribution of a candidate decryption against expected English frequencies:

where $O_i$ is the observed count of letter $i$ and $E_i = n \cdot p_i$ is the expected count under English frequency $p_i$. The correct shift minimizes $\chi^2$.

Frequency analysis (monoalphabetic).

• Time: Tabulating counts is $O(n)$ for ciphertext length $n$. The rank-alignment initial guess is $O(26 \log 26)$. The refinement (hill-climbing over swaps) examines $O(26^2)$ letter-pairs per pass and each scoring pass costs $O(n)$, so each full refinement pass is $O(26^2 n)$; the number of passes until convergence is small in practice (a constant in the tens), giving an overall practical running time of $O(n)$ to $O(26^2 n)$ — linear in ciphertext length for fixed alphabet size. This is exponentially cheaper than the brute-force $O(26!) \approx 4 \times 10^{26}$ key search.
• Space: $O(26)$ for counts and mapping, $O(n)$ to hold the text.
• Correctness intuition: Because substitution is a bijection on the alphabet, the ciphertext letter frequency vector is a permutation of the plaintext letter frequency vector (up to sampling noise for finite $n$). As $n \to \infty$, the empirical frequency of each letter converges (by the law of large numbers) to its true language probability, so the rank order of ciphertext frequencies converges to the rank order of $\pi$ applied to the true language rank order. For finite, realistic $n$ (a few hundred letters), rank order is usually only approximately preserved, which is precisely why the hill-climbing refinement step (using digrams/trigrams, which carry more bits of distinguishing information per character) is needed to correct errors the crude single-letter ranking makes.

Kasiski examination + index of coincidence.

• Time: Finding all repeated substrings of length $\ell$ naively is $O(n^2)$ (all pairs of starting positions), or $O(n)$ average with a hash map keyed by substring, as in the pseudocode. Computing all pairwise distances among repeats of a given substring is $O(k^2)$ for $k$ occurrences, but $k$ is small in practice, so total cost is dominated by $O(n)$ to $O(n^2)$ in the worst (pathological) case. The index-of-coincidence confirmation loop tries $m = 1 \dots M$ candidate lengths, each costing $O(n)$, for $O(Mn)$ total — trivial for realistic $M$ (say, up to 20).
• Space: $O(n)$ to index substrings and positions.
• Once $m$ is fixed: breaking each of the $m$ Caesar sub-streams costs $O(26 \cdot n/m)$ per stream (26 shift trials, each an $O(n/m)$ chi-squared computation), so $O(26n)$ total across all $m$ streams — again linear in $n$.
• Correctness intuition: If the key has period $m$ and the same plaintext substring of length $\ell \geq 3$ appears at two positions whose difference is a multiple of $m$, the key letters aligned with each occurrence are identical, so the ciphertext substrings are identical. Repeats at distances not a multiple of $m$ can occur by coincidence but are statistically rarer for $\ell \geq 3$ (a random trigram match probability is roughly $(1/26)^3 \approx 5.7 \times 10^{-5}$ per position pair). Hence the true period $m$ divides the overwhelming majority of observed repeat-distances, and $m$ emerges as the most frequent common factor — this is exactly why the algorithm takes the argmax over factor frequency rather than trusting a single repeat.

The index of coincidence formalizes this differently: for a random 26-letter alphabet uniformly distributed, $\mathrm{IC} \approx 1/26 \approx 0.038$. For natural English (a fixed monoalphabetic shift of English), $\mathrm{IC} \approx 0.065$–$0.070$, because skewed frequencies make two random letters more likely to coincide. Splitting ciphertext into subsequences at the true period $m$ yields subsequences that are each a straightforward Caesar-shifted English text, so each has $\mathrm{IC} \approx 0.065$. Splitting at the wrong period mixes multiple Caesar-shifted alphabets together, which smears the distribution toward uniform, dragging $\mathrm{IC}$ toward $0.038$. The algorithm's scoring function (distance from $0.0665$) is therefore a legitimate discriminator between correct and incorrect period guesses.

Tradeoffs and honesty about limits. Both attacks are attacks on statistics, so they degrade gracefully with less data: frequency analysis on a 40-letter ciphertext is unreliable (frequency estimates are noisy), while on 2,000 letters it is essentially deterministic. Kasiski examination needs enough repeated substrings to triangulate the period; short texts or very long keys (approaching text length) leave few or no repeats, and the index of coincidence becomes the more robust tool in that regime. Neither attack is a formal proof of insecurity in the modern sense (no reduction to a hardness assumption) — it is an empirical, information-theoretic argument: the ciphertext retains detectable redundancy from natural language, and that redundancy is quantifiably exploitable.

Consider the Vigenère-encrypted ciphertext (spaces added only for the exposition; a real ciphertext would omit them): ``` Ciphertext: LXFOPVEFRNHR VMTOENSVBM YOPKZOOKZ FKQVQOZ VAINP KFZM MP ``` Suppose Kasiski examination finds the trigram `VMT` at position 8 and again at position 32 (illustrative), and the substring `KZOOKZ` region repeats with distances 20 and 40. The distances collected are:

The factor 20's divisors of interest (2, 4, 5, 10, 20) dominate the vote, but among these, small factor 4 appears in all rows too — this is where the index of coincidence is decisive. Running `ConfirmKeyLength` for $m = 1..10$:

$m = 5$ gives $\mathrm{IC} \approx 0.066$, matching English's $\approx 0.0665$ far better than any other candidate — this confirms the key length is 5, consistent with `20 = 4 × 5` and `24` sharing the factor... (in practice the true period is validated by IC, not by picking the most common raw factor, since coincidental repeats muddy the vote — this is precisely why the two methods are used together). With $m = 5$ fixed, the ciphertext is split into 5 subsequences (every 5th letter starting at offsets 0..4). Each subsequence is a pure Caesar shift of English. Applying chi-squared shift search to subsequence 0:

Shift 9 minimizes $\chi^2$, so key letter 0 corresponds to a shift of 9, i.e., key letter `'J'` (since $A + 9 = J$). Repeating this for offsets 1–4 recovers the remaining key letters; suppose the process yields key = `LEMON` (as in the classical textbook example for this exact ciphertext). Decrypting the full ciphertext with the repeating key `LEMON` via $P_i = (C_i - K_{i \bmod 5}) \bmod 26$ recovers: ``` Plaintext: ATTACKATDAWN... ``` The key insight demonstrated end-to-end: nothing here required guessing the key `LEMON` directly out of $26^5 \approx 1.1\times10^7$ possibilities. The period reduced the search to five independent 26-way searches (a total of $5 \times 26 = 130$ trial shifts, each scored in linear time) — an enormous reduction achieved purely by exploiting the periodic structure of the key.

William Friedman, working at Riverbank Laboratories and later for the U.S. Army, formalized the intuitive "does this look monoalphabetic" question into the precise index-of-coincidence statistic used in the algorithm above, turning Kasiski's substring-counting heuristic into a quantitative, repeatable measurement — a shift from craft to statistical science that foreshadows the information-theoretic rigor Claude Shannon would later bring to cryptography as a whole.

Frequency analysis and Kasiski-style structural attacks are not merely museum pieces; they are the ancestors of every modern known-plaintext, ciphertext-only, and side-channel statistical attack. Historically, Allied cryptanalysts extended these ideas (alongside machine-assisted search) to attack the Enigma machine, whose designers had to work hard specifically to defeat frequency-style leakage. In modern systems, the same reasoning appears whenever engineers evaluate whether an encryption scheme leaks distinguishable statistics: ECB mode block ciphers are criticized precisely because identical plaintext blocks yield identical ciphertext blocks — a direct descendant of the "repeated substring" weakness Kasiski exploited. Compression-then-encryption side channels (e.g., the CRIME and BREACH attacks on TLS-compressed HTTP) are modern, high-tech reincarnations of frequency analysis: they exploit statistical leakage (compressed length) correlated with secret content. Security certifications and cryptographic protocol reviews still ask the Kasiski-style question first: "does anything about the ciphertext's length, timing, or repeated structure correlate with the plaintext or key?" Teaching these classical attacks builds the intuition that underlies modern definitions of security, most notably the demand for semantic security and, at the theoretical limit, the unconditional guarantee offered only by Perfect Secrecy and the One-Time Pad.

Ask the tutor: How does the index of coincidence formula change if the plaintext alphabet or language (e.g., non-English) has different letter-frequency statistics?