Cryptology Analysis of Periods after KASISKI

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

Historical Approaches at Cryptanalysis of periodic polyalphabetic ciphers

Already in the 16th Century PORTA and the ARGENTIs occasionally broke polyalphabetic encryptions by

• guessing the key
• or a probable word.

Attack with Known Plaintext

An attack with known plaintext is

• easy against a disk cipher as soon as the primary alphabet is compromised, for example by a lost cipher disk
• trivial against the BELLASO cipher that uses the standard alphabet
• quite difficult against ciphers that use independent alphabets.

The attack with known plaintext was propagated by KERCKHOFFS, together with his method of »symmetry of position« that works for dependent secondary alphabets. This approach apparently was known to BABBAGE as early as 1846, but he never got around to publish it.

Source: O. I. Franksen: Babbage and cryptology. Or the mystery of Admiral Beaufort's cipher. Math. Comput. Simul. 35/4 (1993), 327–367, Abstract.

Historical Example

In World War I the British Navy used the GRONSFELD cipher (among others), that is a BELLASO cipher with shifts of at most nine letters. The key is given by a sequence of some decimal digits that are periodically repeated. The Mathematician Ludwig Föppl who served as radio operator in the German Army observed that a certain group of 18 letters occurred frequently in British radio messages. He supposed this to be a standard phrase, and had success after trying »What is your position?« even without in advance knowing the type of cipher used.

Exercise. Determine the key under the assumption that Pöppel observed the ciphertext AIGYL UCPAW SQWJZ NRP.

Source: Hilmar-Detlef Brückner: Germany's first Cryptanalysis on the western front: Decrypting british and french naval ciphers in World War I. Cryptologia 29 (2005), 1–22.

Attack on short »Vigenère« ciphertexts:

Tobias Schrödel: Breaking short Vigenère ciphers. Cryptologia 32 (2008), 334–347.

KASISKI's Approach

[F. W. KASISIKI, Prussian Major, 1805–1881]

1. step: Determine the period l.
2. step: Arrange the ciphertext in rows of length l. Then the columns each are encrypted by a (different) monoalphabetic substitution.
3. Break the monoalphabetic columns.

In step 3, that is in cryptanalyzing the monoalphabetically encrypted columns, we face the complication that the columns don't represent connected meaningful texts. Pattern search is pointless. However frequency analysis makes sense.

There are some simplifications for dependent alphabets:

• Adjusting the frequency curves. This works when the primary alphabet is known, see Sections 7 and 8.
• Symmetry of position (not treated here, but see later). This method, proposed by KERCKHOFFS, uses regularities in the alphabet table to infer further entries from already known entries, for example by completing the diagonals in the alphabet table of a disk cipher.

Especially simple is the situation with BELLASO's cipher, as soon as the period is known: Each column is CAESAR encrypted. Therefore we need to identify only one plaintext letter in each column.

How to Determine the Period

Three approaches to determining the period of a periodic polyalphabetic cipher are

1. Exhaustion: Try the lengths l = 1, 2, 3, ... one after each other. The correct l reveals itself by the appropriate frequency distribution of the letters in each column. We'll study appropriate methods in Chapter 3.
2. Search for repetitions, see the next subsection. This is an instance of the general method »pattern search«.
3. Coincidence analysis after FRIEDMAN, KULLBACK und SINKOV: This is also a subject of Chapter 3, and is an instance of the general method »statistical analysis«.

KASISKI in 1863 published his method and thereby immediately demolished the belief in the security of periodic polyalphabetic ciphers.

[PORTA in a single case already had used this method, but never thought of a systematic approach. BABBAGE (1791–1871) had found the method ten years earlier than KASISKI's publication but never published it and didn't influence the developement of Cryptology. Therefore it is appropriate to credit the method to KASISKI.]

In contrast to the exhaustion approach the other two methods immediately identify the situation where there is no period.

Search for Repetitions

We start with three observations:

1. If a plaintext is encrypted using l alphabets in cyclic order, and if a sequence of letters occurs k times in the plaintext, than this sequence occurs in the ciphertext about k/l times encrypted with the same sequence of alphabets.
2. In each of these occurrences where the sequence is encrypted the same way the ciphertext contains a repeated pattern in a distance that is a multiple of l. See pictures above and below.
3. Not every repeated pattern in the ciphertext necessarily arises in this way. It could be by accident, see picture below. However the probability of this event is noticeably smaller.

Causal and accidental repetitions
First line: repeated key, second line: plaintext (by Bruce Schneier), third line: ciphertext

An assessment of this probability is related to the birthday paradox of probability theory, and is contained in the appendix of this chapter. It was published in

K. Pommerening: Kasiski's Test: Couldn't the repetitions be by accident? Cryptologia 30 (2006), 346-352.

A Perl program that searches for repetitions is here. It may be called online by a web form.

Exercise. Search for repetitions in one of the formerly generated polyaphabetic ciphertexts.