Can we find the substitution without a crib? We suppose ciphertext *y* = (*y*_{0}, *y*_{1},…, *y*_{n−1}) results from a monoalphabetic substitution of plaintext *x* = (*x*_{0}, *x*_{1},…, *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 ...

Start Free Trial

No credit card required