Nineteenth Century Revelations

Section 4.3 Nineteenth Century Revelations

Objectives

Babbage/Kasiski's Attack

Subsection 4.3.1 Kasiski's Attack

Subsubsection 4.3.1.1 Initial Observations

What follows are excerpts from Friedrich Kasiski's 1863 text on cryptography Die Geheimschriften und die Dechiffrir-Kunst, which was translated into English and privately published by R. W. Pettengill in 1954 as Secret Writings and the Art of Deciphering[10]. For brevity we will only examine a few of Kasiski's key points and we will use a long English rather than a short German quote in order to make his points. While these adjustments have been made to aid in understanding, whenever possible we will remain faithful to the original.

For this section we will use the following example quote for our analysis. It is enciphered using a Vigenère cipher with the keyword BERLIN. You may find it useful to redo the enciphering for yourself.

Example 4.3.1. Sample Vigenère Enciphering.

Plain Text: ¹

Kasiski's original quote was “Die Armee wird mobil gemacht” also enciphered with BERLIN.






Tell the general, Remarque,

that the army has mobilized

to attack the Russians on the

eastern front, and the French,

the English, and the Americans

on the western front which

is currently all quiet.

Cipher Text:

     123456  123456  123456  123456 
 
Key: BERLIN  BERLIN  BERLIN  BERLIN 
 
 (1) UICWBU  FKVYME  BPIPUN  SULPBU  
 
 (2) BXKSMN  SQPSIF  NSSTTV  AIUEWN  
 
 (3) UXRNSG  IIIFAF  JEEDWA  ULVPIF 
 
 (4) UIIYNE  PRKLVQ  ULVQZR  OGYEPR  
 
 (5) FRXWQF  IEEOBU  FEDPZV  DEEDWA  
 
 (6) ULVHMF  UIIYNE  PRKHPV  DLZDKH 
 
 (7) SVVYBY  ZECWYH  JIK

VI. The Actual Art of Decipherment [Cryptanalysis].

A. General Remarks.

72. The actual art of deciphering consists in deciphering any unknown cipher text without previous knowledge of the meaning of the ciphers and without the key.

...

It is impossible to discover the key from a few words of cipher text ... . Consequently we must have available at least four to six rows of cipher text if we are to be able to recover the key.

...

75. The influence of the key finds expression in the fact that at intervals of as many ciphers as the key contains letters repetition of single ciphers or of several ciphers can occur, which can only be due to the fact that, when the same letters of the key were united with a repetition of the plain text to form ciphers. If we have a relatively long cipher text which is enciphered with the key “Berlin,” and if we divide it off into rows of six ciphers and number the ciphers of each row from one to six, we shall find that among the ciphers numbered 1 of each row the cipher U occurs most frequently, among the ciphers numbered 2 I is most frequent, the most frequent among the ciphers numbered 3 is V, among the ciphers numbered 4 Y, among the ciphers numbered 5 B, and among the ciphers numbered 6 F. This is because the ciphers U, I, V, Y, B and F have [likely] arisen by combination of the letters b, e, r, l, i, n of the key with the letter e of the text; since according to [previous observations] the letter e occurs most frequently in the text, naturally the above ciphers must occur most frequently under the numbers mentioned.

Next most frequent in this cipher text are the ciphers S in column one, E in column two, K in column three, P in column four, W in column five and V in column six because these ciphers S, E, K, P, W and V result from a combination of the letters b, e, r, l, i, n of the key with the letter t of the text and t is the next most common letter letter after e. [10, pp.29-30 (34-35)]

Comprehension Check:

In section (75) Kasiski writes about letters of the key uniting with repetitions of plain text, how does this compare to Falconer's observations in Section 4.2?
We know that the Vigenère cipher can encipher many different plain text letters as the same cipher text letter, so why is it reasonable for Kasiski to believe that all the U's in column 1 should represent e or that all the P's in column 5 might represent t? (Answer in terms of how we know the Vigenère cipher works.)
Break the plain text message in Example 4.3.1 into blocks of six then use the key BERLIN and the modern Vigenère table Figure C.0.8 to encipher it, you should get the same cipher text as that which is in the figure.
Is Kasiski right about his guesses, that is do the U and I in the first and second columns represent e, or do the E and K in the second and third columns represent t? How do your answers to this question relate to Kasiski's comments in section (72)?

Further observations by Kasiski:

76. ... where repetitions of two or more ciphers are found in the cipher text one can conclude that these are due to the fact that, in enciphering, repetitions in the plain text were repeatedly combined with the same letters or the key.

If we encipher with the key “BERLIN” as above, we shall frequently find in the cipher text in columns 1 and 2 the ciphers UL, in 2 and 3 XY, in 3 and 4 KS, in 4 and 5 EP, and in 5 and 6 BU because these ciphers UL, XY, KS, EP and BU have arisen by combining the letters BE, ER, RL, LI and IN in the key with the [repetitions of] th in the text. [10, pp.30-31 (35-36)]

Comprehension Check: (For these it will be helpful for you to look at the work you did in the above questions.)

Look carefully at the cipher text in Example 4.3.1, how often do you find the bi-grams UL, XY, KS, EP and BU? Do they always line up with the cipher key so that they give th when you decipher them?
For this observation Kasiski enciphered th using each of the pairs of letters BE, ER, RL, LI and IN from BERLIN, but he didn't consider enciphering it with NB (i.e. wrapping around from column 6 back to 1). Encipher the bi-gram th using the rows NB in the Vigenère table Figure C.0.8, what cipher bi-gram do you get? How often to you find that bi-gram in the cipher text in Example 4.3.1? (Remember that you need to look from columns 6 to 1.)
Can you find other repeated bi-grams? Can you find longer repeated n-grams?

Subsubsection 4.3.1.2 Determining the Key

Kasiski's observations above, and Falconer's previously, give us a way to attack Vigenere's cipher if we know the key length. But first we need to find the key length.

78. ... In a simple cipher text repetitions are more frequent and are merely accidental, that is to say, rarely occur at regular intervals, whereas in the composite cipher text [i.e. Vigenère cipher] these repetitions occur less often but usually at intervals such that the number of letters between them is divisible by a number which gives the number of letters in the key.

...

80. ... We now try to determine the number or letters in the key. For this purpose we look for all repetitions of two or more ciphers in the enciphered text, then count the interval from one another of like repetitions; write these out beneath the enciphered text with numbers indicating the intervals, and endeavor to break this number up into its factors.

For instance, we find 16 letters between two repeated ciphers UL, we add two ciphers to the number 16 and get 18 as the interval for the repetition UL.

We write UL \(= 18 = 2\cdot 9 = 3\cdot 6\text{.}\)

According to section (76) we can infer from this that the key contains either two, nine, three, or six letters.

Since the number of letters in the key is still uncertain and ... the repetition of the ciphers UL might be purely accidental, we write out one by one all the repetitions of several ciphers, noting the number representing their intervals, and break these numbers down into their factors.

Those factors which are found most frequent indicate the number or letters in the key. [10, pp.31-32 (36-37)]

Comprehension Check:

Why did Kasiski add two to the number of characters between the two repeated copies of UL?
The three letter cipher ULV also appears more than once, after counting the number of characters from one to the next how many letters should you add to that count before factoring it? What about for the repeated cipher UIIY?
Go through the entire cipher text in Example 4.3.1, look for all the repeated ciphers which are at least two characters long, then for each one write down the distance between them and the factors of those distances. What number(s) pop up most often? Why does this make sense?

Finally we find the key: In what follows Kasiski makes use of what he calls the key table which is a rearranged Vigenère table with plain text letters on the left, cipher letters along the top and the possible key letters on the interior. So it tells us that if we have a cipher letter J which we believe represents a plain text letter i then looking in the table we can see the corresponding key letter was a B.

Check that you understand the key table by trying to find the key for this message based on the given plain text and cipher text.
```
plain:  winter is at a close
CIPHER: OXEBRX AH RB N IDDJM
```
Why do you think that Kasiski ordered the plain text characters the way he did?
Why do you think that he didn't include all the possible plain text letters?

Finding the key:

85. ... If we have determined according to section 80, the number of letters in the key, we divide the cipher text into rows containing as many ciphers as the key contains letters and number the several columns. In theory those ciphers which occur most frequently in a given column should signify the letter e in the text;

...

86. After we have divided the cipher text into rows according to the number of letters in the key and have numbered the several columns, we take out all ciphers from column 1 and note the number o£ occurrences, then we do the same for columns, 2, 3, etc. [See Example 4.3.1]

If we have found in this way the cipher U, let us say, occurs seven times, cipher S three times and cipher F three times in column 1, we copy from the key table letters beneath the ciphers U, S and F on a separate sheet of paper as follows:

7 U - Q B U G M H C D N J
3 S - O Z S E K F A B L H
3 F - B M F R X S N O Y U

Among these letters must be found the first letter of the key. The letter B occurs as second letter under cipher U, as eighth under cipher S, and as first under cipher F. Hence B is combined seven times with t to form U, three times with r to form S, and three times with e to form F. From this we must conclude that B is the first letter of the key. The letter M also has a more remote probability of being the first letter of the key since it occurs as fifth under U, and as second under F ... . In the same way we just found the first letter of the key, we now look for the other letters. [10, pp.34-35 (39-40)]

Comprehension Check:

In the columns labeled 2 in the example we have been working with three most common ciphers are I, E, and L appearing 6, 5, and 4 times respectively. From this Kasiski would have us write down the following from the columns of the key table:
```
6 I - E P I U A V Q R B X F
5 E - A L E Q W R M N X T B
4 L - H S L X D Y T U E A I
```
Which two possible key letters appear in all three rows?
In the columns labeled 3 in the example we have been working with three most common ciphers are V, K, and I appearing 5, 4, and 4 times respectively. Follow Kasiski's lead and write down the corresponding columns from the key table:
```
6 V - 
5 K - 
4 I - 
```
Which possible key letters appear in all three rows?
In the columns labeled 4 in the example we have been working with three most common ciphers are Y, P, and W appearing 4, 4, and 3 times respectively. Repeat the steps from the previous two questions to try and find the fourth key letter.
In the columns labeled 5 in the example we have been working with three most common ciphers are B, W, and M appearing 4, 3, and 3 times respectively. Repeat the steps from the previous two questions to try and find the fifth key letter.
In the columns labeled 6 in the example we have been working with three most common ciphers are F, V, and U appearing 5, 3, and 3 times respectively. Repeat the steps from the previous two questions to try and find the sixth key letter.
Put together all the possible key letters we get for all the columns of the message, do they (or at least can they) spell “BERLIN” as we expect them to?

Try to practice what we have been looking at with these exercises. You can also look at the sample Vigenere analysis in the appendix (Section E.3).

Checkpoint 4.3.3.

The following text was enciphered using a key of CIPHER. Follow Kasiski's steps to see if you could have found this for yourself.

 (1) UQCJIR TIBPWJ UQCNYC CZIYEE UNDYQR VQDUME VWPJSE 
 (2) HMHZSI QNIOIF TLTYFR KATTIR WFLHWE QTDUKV TBWLWR 
 (3) OMBHRL RBDALR VXTYMF FBWLTC CKTDLZ EPPYED KAWHHY 
 (4) GTSPRK JMLVVK JGVVZV TVDYWV UBXTEK KWCDEJ VPPASW 
 (5) CXGLPR VMLOSD JMGLWG GKILHR PLPMVZ GVSASN JWBOIF 
 (6) YMSHHV DBDMKI CBXAYU GJJARF YPTMIC VPXTWV NNPUME 
 (7) HMGPSI CVSALR VIGHQZ UEPZLZ UUPZXV TPTOMD UMAMPZ 
 (8) IPILHR NICAII PAJTQF PMSHXL TVZLCR PLHHMU TMIBVE 
 (9) KVVASR TIBPWZ CUPACF WZDYHV TABVRJ GQVUIL TIGHQZ 
(10) UUTYIC AVDKHV FPXZLV CLPZQL EPPZXF UINCII AODVHR 
(11) PLHPKE GLIVLZ OEXALY KAWHRU VWALEU VPTDEP

Hint

Look for repeated strings.
For each pair of repeated strings write them down and next to them write down the number of characters from the start of one to the start of the next and the factors of that number.
Assuming that the most common factor is 6, which we know it should be, use the subset cell to find the most common letters in each column.
Use these letters and the key table (Figure 4.3.2) to try and find the key, which should be CIPHER.

Answer

“Since Aramis's singular transformation into a confessor of the order, Baisemeaux was no longer the same man. Up to that period, the place which Aramis had held in the worthy governor's estimation was that of a prelate whom he respected and a friend to whom he owed a debt of gratitude; but now he felt himself an inferior, and that Aramis was his master. He himself lighted a lantern, summoned a turnkey, and said, returning to Aramis, "I am at your orders, monseigneur." Aramis merely nodded his head, as much as to say, "Very good"; and signed to him with his hand to lead the way.” The Man in the Iron Mask, Alexandre Dumas

Checkpoint 4.3.4.

Follow Kasiski's steps to find the key for this message. Then use the Vigenère cipher cell to decipher it.

 (1) IERSDO EDPRHZ AMWXBU OEFAYX IEOPOO EWWUOG UNYRQJ 
 (2) OPFIGX BFHUQP SMMFTG TEZYZJ SYUKWK BIIROE FDILFT 
 (3) MVWEXY WFFHGE OYHFFO FYBYWA STZKBZ GGASSI BFSIQR 
 (4) QDPZBT TESCSV RUUMKO TWKUKT ZOSZBT TAVCME HSARZS 
 (5) USOPWW ZIBYSV DOFWIJ YUMDLR ZFKAFH WCQCJR DPDKBV 
 (6) OGFHWP MVHBRR SYCCOF FOLRMW WEETKE JASPFT ZOZVDY 
 (7) KWSCVV UNFINO PVYAQW JSOYHJ QLDDPR HGTECS VXGPML 
 (8) DSVXVV YWSCNI CZZEUO AJWGKH WCBZZY RUJDPV FXZEOD 
 (9) PRHYAU ACFZJZ GSLOFG SEUEFM MRBVYP WBQFIF PEKSZV 
(10) TBDAHB QMOGQC GXDVFF MTAYVN WGTOFO EYCZFH WZWJGR 
(11) ESAYVF TFGCZK AVQEQT HVITSQ ANSVMM SYIILR BYSUUG 
(12) ZOAKDB IEJCWW HUQKAX OUCZNU LKAKCF MYAXOV LNOTDI 
(13) EYOGFH WUQEUF IIKRER GQMRLK OEOARO MXLYWZ EEDPKF 
(14) ACXELO TPOGML GCAKVR YUKUMK SRDHSN VFRBGB LCMZHU 
(15) QRMZWE HUQRWK AFBJTI URPRRH DGWNBY SHZFGB BLBNFE 
(16) HRQCWC BELYZV JRMLZS ATVNDA UDMIOA PBABBY DUULAZ 
(17) XVPHDI WNNFFR HEJLME SNFHSW IJYBRS LOMCSK ULWNBF 
(18) OPAUFD ZPKUQR WDPVAR ZSWOUV RYUTLV MDCEQT ZKVJZN 
(19) HEKYNK VRQLWW MEHFBH AVQGDR PEHBQM SQQVWX WWHUQS 
(20) GMQVHL AFVKZK OTZAFG PFVNPL GKLVRU UMOSBY VBZOJC

Hint

Look for repeated strings.
For each pair of repeated strings write them down and next to them write down the number of characters from the start of one to the start of the next and the factors of that number.
Use the subset cell to find the most common letters in each “column” as if you had split up the cipher according to the length you found in the previous step.
Use these letters and the key table (Figure 4.3.2) to try and find the key.

Answer

The keyword is “ironmask”

The message is:

“And from that moment, D'Artagnan, accommodating his action to the pace of the horse, like a true centaur, gave up his thoughts to nothing - that is to say, to everything. He asked himself why the king had sent for him back; why the Iron Mask had thrown the silver plate at the feet of Raoul. As to the first subject, the reply was negative; he knew right well that the king's calling him was from necessity. He still further knew that Louis XIV. must experience an imperious desire for a private conversation with one whom the possession of such a secret placed on a level with the highest powers of the kingdom. But as to saying exactly what the king's wish was, D'Artagnan found himself completely at a loss. The musketeer had no doubts, either, upon the reason which had urged the unfortunate Philippe to reveal his character and birth. Philippe, buried forever beneath a mask of steel, exiled to a country where the men seemed little more than slaves of the elements; Philippe, deprived even of the society of D'Artagnan, who had loaded him with honors ...” The Man in the Iron Mask, Alexandre Dumas

Figure 4.3.5. Modern look at Kasiski

Sage Cell for counting instances of specific strings:

Sage cell for calculating subsets of letters in a message:

Sage cell for enciphering and deciphering the Vigenère Cipher:

Subsection 4.3.2 (*)Babbage's Contributions

Insert Information on Babbage's Cryptologic Work ...