Chi-squared, index of coincidence, and why classical ciphers fall

Classical ciphers are worth taking seriously, not because anyone deploys them, but because they are the cleanest possible demonstration of the idea that underpins all of cryptanalysis: a wrong key leaves statistical fingerprints, and a right key removes them. Everything from breaking Caesar to distinguishing a block cipher mode is a variation on that theme.

Two statistics do almost all of the work. Chi-squared tells you whether a piece of text looks like English. The index of coincidence tells you whether a piece of text was encrypted with one alphabet or several. Together they break every classical cipher a CTF is likely to hand you, without a wordlist and without a guess.

Chi-squared: scoring a candidate plaintext

English letter frequencies are stable: E is about 12.7% of letters, T about 9.1%, Z about 0.07%. Given a candidate decryption of length N, you expect letter *i* to appear E_i = N × p_i times. Chi-squared measures the total squared disagreement between what you expected and what you counted, normalised by the expectation:

ENGLISH = [0.08167,0.01492,0.02782,0.04253,0.12702,0.02228,0.02015,0.06094,
           0.06966,0.00153,0.00772,0.04025,0.02406,0.06749,0.07507,0.01929,
           0.00095,0.05987,0.06327,0.09056,0.02758,0.00978,0.02360,0.00150,
           0.01974,0.00074]

def chi_squared(text: str) -> float:
    letters = [c for c in text.upper() if 'A' <= c <= 'Z']
    n = len(letters)
    if n == 0:
        return float('inf')
    score = 0.0
    for i in range(26):
        observed = letters.count(chr(65 + i))
        expected = n * ENGLISH[i]
        score += (observed - expected) ** 2 / expected
    return score

def break_caesar(ct: str):
    # Try all 26 shifts, keep the one that looks most like English.
    best = min(range(26), key=lambda k: chi_squared(shift(ct, -k)))
    return best, shift(ct, -best)

def shift(text: str, k: int) -> str:
    out = []
    for c in text:
        if c.isalpha():
            base = 65 if c.isupper() else 97
            out.append(chr((ord(c) - base + k) % 26 + base))
        else:
            out.append(c)
    return ''.join(out)

The value is not meaningful on its own - only the ranking is. For a hundred characters of correct English you will typically see something in the tens; for a wrong shift, several hundred. The gap widens with length, which is why chi-squared is reliable on a paragraph and unreliable on a single word.

Index of coincidence: one alphabet or many?

Pick two letters at random from a text. The probability they match is the index of coincidence. For English it is about 0.0667; for uniformly random letters it is 1/26 ≈ 0.0385. A monoalphabetic cipher - Caesar, Atbash, any substitution - just permutes the alphabet, so it *preserves* the IoC. A polyalphabetic cipher like Vigenère spreads each plaintext letter across several alphabets, flattening the distribution toward random.

def index_of_coincidence(text: str) -> float:
    letters = [c for c in text.upper() if 'A' <= c <= 'Z']
    n = len(letters)
    if n < 2:
        return 0.0
    total = 0
    for i in range(26):
        f = letters.count(chr(65 + i))
        total += f * (f - 1)
    return total / (n * (n - 1))

Breaking Vigenere in two moves

A Vigenère cipher with key length *k* is just *k* independent Caesar ciphers interleaved. So the attack has exactly two steps: find *k*, then solve each column separately with the chi-squared break above.

Move one: find the key length

The direct method is to split the ciphertext into *k* columns for each candidate *k*, compute the IoC of every column, and average. When *k* is correct, each column is a monoalphabetic ciphertext of English and the average jumps toward 0.066. When it is wrong, the columns stay flat near 0.038.

def key_length(ct: str, max_k: int = 20):
    letters = ''.join(c for c in ct.upper() if 'A' <= c <= 'Z')
    scores = []
    for k in range(1, max_k + 1):
        cols = [letters[i::k] for i in range(k)]
        avg = sum(index_of_coincidence(c) for c in cols) / k
        scores.append((k, avg))
    return sorted(scores, key=lambda kv: -kv[1])[:5]

Two classical alternatives are worth knowing. Kasiski examination looks for repeated trigrams in the ciphertext and takes the greatest common divisor of the distances between them, on the reasoning that a repeated plaintext fragment aligned with the same key position produces identical ciphertext. The Friedman test estimates the length directly from the overall IoC:

# Friedman’s estimate. I is the IoC of the whole ciphertext, N its length.
k_estimate = (0.0265 * N) / ((0.0665 - I) + N * (I - 0.0385))

Move two: solve each column

With *k* known, take every *k*-th letter starting at offset 0; that column was enciphered with a single shift, namely the first letter of the key. Run the Caesar break on it. Repeat for offsets 1 through *k*-1 and read the key off the shifts. The whole attack is O(k × 26) chi-squared evaluations, which is nothing.

General substitution: when there is no shift to find

An arbitrary substitution has 26! keys, so brute force is out, but the statistics still win. The standard approach is hill climbing on quadgram scores: start from a key ranked by single-letter frequency, then repeatedly swap two letters and keep the swap if the log-probability of the resulting text under English quadgram statistics improves. Restart from random keys a few hundred times to escape local maxima.

Quadgrams rather than single letters matter here because single-letter frequency cannot distinguish THE from TEH. Positional structure is what pins the last few letters down, and the last few letters are the ones hill climbing struggles with.

Two shortcuts help when the automated solve stalls. Word patterns: if word boundaries survived, a three-letter word appearing five times is THE with high probability, and a one-letter word is A or I. Doubled letters: LL, SS, EE, OO, TT cover most doubles in English, and a doubled ciphertext letter narrows the candidate fast.

The rest of the classical zoo

• Atbash - reverse the alphabet, no key. Try it first because it costs one operation and CTFs love it.
• Affine - E(x) = (ax + b) mod 26 with gcd(a, 26) = 1. Only 12 × 26 = 312 keys, so brute force with chi-squared scoring is instant.
• Rail fence and columnar transposition - letter frequencies are untouched. Brute force the rail count (2-8) and every offset, then score the results.
• Bacon - each letter becomes five binary symbols, hidden in *some* two-way distinction: upper/lower case, two fonts, vowels versus consonants. If the text is exactly 5x as long as it should be, this is it.
• Playfair - digraph cipher on a 5x5 grid, so J is missing and no letter is ever enciphered as itself within a pair. Simulated annealing on digram statistics breaks it.
• Polybius / Nihilist / ADFGX - coordinate systems. Ciphertext restricted to five distinct letters or to digit pairs in the range 1-5 is the giveaway.

Notice that the identification step for every one of these is a statistic or a character-set observation, not a guess. Build the habit of measuring first - IoC, alphabet size, length ratio - and the correct attack usually selects itself.