Computer Security and Cryptography

3.6 PARTIAL MAXIMUM LIKELIHOOD ESTIMATION OF A MONOALPHABETIC SUBSTITUTION

Can we find the substitution without a crib? We suppose ciphertext y = (y₀, y₁,…, y_n−1) results from a monoalphabetic substitution of plaintext x = (x₀, x₁,…, x_n−1), both written with letters in the alphabet with an unknown substitution θ.

We assume the substitution θ has been chosen randomly independent of x and according to the uniform distribution Pr_{a priori}{Θ = θ} = 1/m. The cryptanalysis problem

Given:	y
Evaluate:	the likelihood of the hypothesis H(τ) that Θ = τ

is solved by the maximum likelihood estimation (MLE). Computation of the MLE assumes the plaintext has been generated by a Markov language model with parameters (π, P). Knowledge of the ciphertext changes the likelihood of Θ:

Using Baye's Law

we have

The MLE of the substitution is any which satisfies

Assuming and Pr_{a posteriori}{Y = y} does ...