Cryptology Autocoincidence of a Text

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Definition

For the cryptanalysis of periodic polyalphabetic ciphers the following construction is especially useful:

Take a text a and cyclycally shift it to the right by q positions. In this way you get a text a_(q). Call

κ_q(a) := κ(a,a_(q))

        COINCIDENCESBETWEENTHETEXTANDTHESHIFTEDTEXT <--- original text
        EDTEXTCOINCIDENCESBETWEENTHETEXTANDTHESHIFT <--- shifted by 5
                     |  |      | |           |    | <--- 6 coincidences

Note: This is not a common notation. Usually this concept is not given an explicit name.

Application

Now we take a periodically polyalphabetically encrypted ciphertext c. When we determine the index κ_q(c), and the shift q is not a multiple of the period l, then in general we meet pairs of letters that are encrypted by independent monoalphabetic substitutions. Therefore we expect a result about the random value ≈ 1/n.

But in the case where q is a multiple of l we encounter letter pairs encrypted by the same monoalphabetic substitution. That is, the two ciphertext letters coincide exactly if the two plaintext letters coincide. Therefore for κ_q(c) we expect a value near the typical coincidence index of two plaintexts.

This is the second application of coincidence indices: Recognize the period of a polyalphabetic substitution by the autocoincidence indices.

Compared with the search for repetitions after KASISKI this method also takes account of repetitions of length 1 or 2. In this way we make much more economical use of the traces that the period leaves in the ciphertext.

To get a more concrete idea of these vague statements we treat an example. The Perl program for this is here [online call].

Because of the obvious relevance of the sequence κ₁(a), ... κ_r-1(a) of autocoincidence indices of a text a of length r we call it the autocoincidence spectrum of a.

Typical autocoincidence spectra look like this.

[Note that this notation too is not standard.]