Computer Security and Cryptography

3.4 THE χ²-TEST OF A HYPOTHESIS

Suppose a large number n of independent trials of a chance experiment ∈ are performed. A trial has r possible outcomes O₀, O₁, …, O_r−1 that occur with probabilities q(0), q(1), …, q(r − 1). The number of times the outcome O_i occurs, N_i, is recorded.

How likely is it that the observed outcome-counts {N_i} are consistent with the hypothesis : q(i) is the probability of occurrence of O_i, (0 ≤ i < r). In the context of cribbing

• The experiment ∈ is the generation of plaintext by an iid language model with 1-gram probabilities π followed by monoalphabetic substitution θ;
• The r outcomes correspond to the occurrence of the letters of a ciphertext r-gram u;
• u = (u₀, u₁, …, u_{r − 1}) is a ciphertext isomorph of the plaintext crib v = (v₀, v₁, …, v_{r − 1}); and
• The probabilities q(i) = π(v_i) are those that would be true if the ciphertext u was the encipherment of the plaintext crib v – that is, if θ : v → u.

If the hypothesis is true, then for each possible outcome O_i, the law of large numbers asserts

The χ²-statistic is the quantity defined by

The ith term in the sum above is the product of two factors. The first,

increases without bound with n, and the second has ...