O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

2.8 MARKOV SCORING

Given: columnar transposition ciphertext y;

Find: the transposition width N and transposition τ.

Our plan is to test N as a possible width by computing a Marko score for the adjacency of columns in the ciphertext, assuming each of the N! transpositions of width N are equally likely to have been used.

Testing a width N is formulated as a hypotheses testing problem; for each pair (i, j) with ij, decide which of the two hypotheses is the most likely to be true.

image, jth column is read from X immediately after theith column is read from X.
image, jth column is not from X immediately after theith column is read from X.

When ADJ(i, j) is true, the ith and jth columns must be columns (k, k + 1) in X for some k with 0 ≤ k < n−1. As the N! transpositions τ have been chosen with equal probability, the a priori4 probabilities of the hypotheses ADJ(i, j) and image are

image

and

image

The ratio of these probabilities is the a priori odds of ADJ(i, j) over

The term ODDS has the same interpretation ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required