Ciphertext-only Attack on a Vatican Cipher (1573) by Albert C. Leighton

Deciphering ciphertexts in archives without a key have been achieved by many, as described in, among others, the chapter "Ciphers in the Past Tense" in David Kahn, The Codebreakers (1967) and "Some examples of historical cryptanalysis" (1977) by Albert C. Leighton (whose works I came to know by Klausis Krypto Kolumne).

The present article describes Leighton's deciphering of a Vatican ciphertext on a sheet enclosed in a letter from Korakow, 18 November 1573 of Antonio Maria Gratiani to the Papal Secretary of State, Cardinal Como. Gratiani was secretary to Cardinal Commendone at the time. Among many diplomatic missions of Commendone , he was papal nuncio to Poland in 1563-1563 and, later, promoted the election of Henry, Duke of Anjou, as King of Poland in May 1573. The letter was written some months after the election.

The ciphertext consists of an unbroken series of figures. The first task was to split the sequence of figures into individual cipher symbols. It was clear that "there is a tendency for numbers to be linked in pairs" with a few exceptions of three-digit groups ("608", "508", "308", "108", highlighted in yellow in the image). Then, it was natural to assume that the two-digit groups were symbols of a substitution alphabet, with the three-digit groups and some pairs having a dot over the first digit representative of names or words. There is also a symbol like an inverted 4 (underlined in blue in the image).

By listing the occurrences of the pairs, Leighton found that, with a few exceptions, the pairs ended in odd numbers. So, the cipher symbols may be mapped in a matrix, in which the row and column numbers refer to the first and second digits in the pairs:

 1 3 5 7 9 1 11 13 15 17 19 2 23 25 27 29 3 31 33 35 37 39 4 41 5 51 53 55 57 59 6 7 75 77 79 8 83 9 91 97 99
(The figures in the cells are
cipher symbols that
occurs in the ciphertext.)

From the number of different symbols, one might assume that there were homophones. Then, Leighton had an idea that "1" and "2" in the fist digit were equivalent; similarly for other pairs "3" and "4", "5" and "6", and "7" and "8." There is no reason that this is so but Leighton just tried it as "an example of an easy way" for accommodating homophones. This working hypothesis, which seemed "too obvious and simple to be of any use" turned out to be successful. Codebreaking efforts are often rewarded when one pursues every faint possibility. One who brings up a bunch of reasons to deny a hypothesis before working it out to the full tends to miss a hit.

The working hypothesis reduces the matrix as follows.

 1 3 5 7 9 1 or 2 * * * * * 3 or 4 * * * * * 5 or 6 * * * * * 7 or 8 * * * * 9 * * *
 symbol freq. 25 78 29 45 17 43 77 42 13 38 79 33 59 32 99 29 37 25 75 24 11 21 55 15 ... ...

Referring now to symbol statistics, Leighton noticed that no less than four of the five most frequent symbols began with "1" or "2". So, he considered the symbols beginning with "1" and "2" ("1*" and "2*") might all be vowels. With this in mind, he recounted the frequencies. For example, "25" (78 times) and "15" (4 times) were counted together as "15 or 25" (82 times). Such consolidation made predominance of the suspected vowels even more conspicuous. (By the way, although he adds that "1" and "2" in the manuscript are hard to differentiate because the writer knew it did not matter, I have encountered such a similarity between "1" and "2" in Benedict Arnold's correspondence (see another article and also in French archives, where the difference mattered.)

Of the five vowels, "U" is the least frequent, even if we consider that "U" also served as a consonant "V" at the time. So, Leighton picked for "U" the least frequent group beginning with "1" or "2", that is, "11" (21 times; "21" does not occur).

Turning to consonants, the most common consonant in Italian "N" may be assigned the most frequent "consonant" symbol "77." Then, Leighton also noticed that the three next most frequent "consonant" symbols ("79", "59", "99") ended in "9". If the assignment follows the alphabetical order in some way, one might assume that these three "59", "79", "99", which align on top of each other in the matrix, might be "R", "S", "T." The next frequent symbol is "37", which would correspond to "L" according to letter statistics of Italian.

Filling these findings in the matrix yields:

 1 3 5 7 9 1 or 2 U * * * * 3 or 4 * * * L * 5 or 6 * * * * R 7 or 8 * * N S 9 * * T

Now, the alphabetical ordering assumed for "R", "S", "T" seems to be consistent with the positions of "L" and "N". Then, the vowels "I" and "O" in the top row can be inferred. "M" can be put by the alphabetical ordering. Similarly for "P", because "Q" always occur as "QU" and may not be in the substitution alphabet on its own.

 1 3 5 7 9 1 or 2 U * * I O 3 or 4 * * * L P 5 or 6 * * * M R 7 or 8 * * N S 9 * * T

A-B-C-D and E-F-G-H are yet to be assigned to either the second or third column. The frequency count shows "75" and "55" are relatively frequent among the remaining symbols and it is more likely that they correspond to "C" and "D" rather than "F" and "G" (Leighton appears to have foreseen that the silent letter "H" is not used in the substitution alphabet (Leighton (1977) p.322)).

 1 3 5 7 9 1 or 2 U E A I O 3 or 4 Z F B L P 5 or 6 * G C M R 7 or 8 * D N S 9 * * T

The above result is based on the simplest hypotheses but its application to the beginning of the ciphertext produced plausible Italian words: 608(*) 53(G) 17(I) 11(U) 75(D) 17(I) 55(C) 25(A) 77(N) 75(D) 29(O) 97(*) 41(*) ....

This verifies Leighton's too-good-to-be-true hypotheses. The cipher has indeed an alphabetical assignment in a matrix and provides homophones simply by the equivalence of pairs "1" and "2", "3" and "4", ... in the first digit. (Similar ciphers are described in another article.)

After identifying the meaning of some of the remaining figures from the context in Italian, Leighton set on "a long search for similar ciphers" and found the complete cipher in Aloys Meister (1906), Die Geheimschrift im Dienste der päpstlichen Kurie, pp.235-237. It was a cipher given to Commendone during his nunciature in Poland.

The complete cipher assigns single digits "5", "3", "7", "9", "1" to represent the vowels. If these single digit cipher symbols had been used in Gratiani's letter, the initial step of splitting the figure sequence into individual cipher symbols of one to three digits would have been more difficult. (In theory, there is no unique division. For example, "5553" can be "5 5 5 3" (aaae) or "5 5 53" (aag) or "5 55 3" (ace) or "55 5 3" (c a e) or "55 53" (c g). A decipherer having the key would be able to pick the most natural division but this ambiguity adds a complexity to the task of codebreaking.)

References

Albert C. Leighton (1969), "A Papal Cipher and the Polish Election of 1573" (Jahrbücher für Geschichte Osteuropas) (BSB)

Albert C. Leighton (1971), "Further Information on a Papal Cipher of 1573", Jahrbücher für Geschichte Osteuropas (JSTOR)

Albert C. Leighton (1977) "Some examples of historical cryptanalysis" in Historia Mathematica (Elsevier)