Skip to main content

Section 4.2 A Seventeenth Century Idea

Subsection 4.2.1 Falconer's Attack on Polyalphabetics

“There is an invention of secrecy much insisted on (though none of the swiftest) by the author of the Secret and Swift Messenger, and others, beyond any yet mentioned, for intricacy, wherein each particular line, word, or letter, is written by a new alphabet: but the cited author himself acknowledges it too tedious for a current correspondence;” - John Falconer [4, p.17 (45)]

So begins John Falconer's discussion of using the polyalphabetic cipher. Falconer agrees with other cryptographers of his time that the cipher, while secure, is to slow and cumbersome and so not worth the trouble of using. However, for the sake of giving a complete account of the current state of the science of cryptography in his time, Falconer goes on to discuss in detail how to encipher and decipher messages with this type of cipher. What is interesting and more significant is that he makes a solid attempt at cracking this cipher, possibly the first real attack since its invention[9, p.155].

For his first example of how to attack a polyalphabetic cipher Falconer assumes each line is enciphered by a separate cipher alphabet. [4, pp.20-23 (48-51)]

I. Example in the Lines

Y pb vdgrts id ztte ixt Hdafytgh
idcb wofr rihm obr rihm rxfh
dfaawi fd ze espi gtww cpfzwe ez
cqn Nwuxg bynnmrtg. qibc.
I am forced to keep the Soldiers
upon hard duty and hard diet:
Supply us, or they will revolt to
the enemy speedily. Hast.

“1. When there is only one alphabet used for a line, the writing might be discovered an in plain cipher, if you make a new operation for each line. But there may be other ways to decypher any such writing: for,”

“2. If you find out but one letter in a line, (and that may certainly be done by a few suppositions) it will of itself give an alphabet for the whole line, as you may perceive by the counter-table, which follows: ... you need only to search for i in the upper line of it, and try in what line Y is opposite to it; and those two lines give you an alphabet.”

“Having found one alphabet for the first line, you have likewise by this means the first letter of the key. e.g. In the fifteenth line of the table, Y standing against i, and P beginning that line (as you may perceive) P must be the first letter of the key;”

“... you may proceed to find the alphabet of the second, third, or any other line, as you did the first;”

For reference, here is a copy of the Vigenere table (what Falconer calls the counter-table) as Falconer was using it:

Figure 4.2.1. Falconer's Counter-Table

Comprehension Check:

  • Looking at Falconer's cipher text, why would you assume that the Y represented i? What other letter might it represent?
  • How did He decide that line 15, which starts with P, was the one that was used to encipher the first line of the cipher text?
  • Verify that the fifteenth line, the one labeled P, is the correct one to use for the first line by deciphering the rest of the line.
  • Looking at the next three lines of the cipher text try, without looking at the accompanying plain text, to decide which row of the counter-table was used to encipher them. What can you look at to try and help you decide?
  • Finally, what is the keyword of phrase that was used to encipher this message?

In the next section of his text Falconer tackles the problem of deciphering a message in which we switch alphabet with each new word. It is here that he makes a significant observation that can help us find the length of the keyword.

“1. Having found an alphabet for the first, second, or indeed any word near the beginning of the epistle, go through all the immediate following words, until you find another that is decyphered by the same alphabet.”

“2. From the last found word count the like number, and you have a new word decypherable by the found-alphabet: and thus you may go on until you have once gone through the whole writing, marking the whole series with some particular mark: And then,”

“3. Begin the epistle again at some word immediately before or after that which was first found, and count forwards as before, until you come to the end of the epistle. [Repeat this process until each word is marked as part of a series.]” - John Falconer [4, pp.24-25 (52-53)]

Comprehension Check: Refer to this cipher text when answering the comprehension check questions.

     1  2    3          4      5      6            7      8
1 -  MX EIB  WKG        LOCD   SK     GWZRF,
2 -  BM ZEW  CQN        YQTUW  YP     YNQIX,
3 -  WG OSL  XLH        IPN    QH     FSCNYW,
4 -  NY INF  MAX        EKH    XO     HQQNLUKPGUU,
5 -  SD AEX  GUR        XHGUA  RI     KNTRNO,
6 -  LW FKC  YMI        RCBPU  GY     MQFUHGYOMXB,
7 -  RC YCU  DRO        XIEXSR BS     DBZAM,
8 -  MX EIB  WKG        COKCYX SK     QNEXARFF,
9 -  BM ZEW  CQN        URTLPI YP     MSTI,
10 - WG OSL  XLH        ERWCNA QH     NOCZKSB,
11 - AI UNQ  XNXKQMABFY FHIRUH DB,
12 - YG TKN  RSYMNRL    ORSBER NL,
13 - ZH ENAN CNN        QYSXQ  HNWIGY GB           AXNXF,
14 - ZH ENAN CNN        QYSXQ  HNNIGY GUR          GMAXK  ZDB

  • Start by trying to find some repeated pieces of text. Falconer seems to imply that these are enciphered using the same alphabet from his counter-table; thinking about how we use the Vigenère cipher normally why could we end up getting theses repetitions?
  • How far apart are the repeated strings? What factors do they have in common?
  • Follow Falconer's advice and break the message into groups of strings which were enciphered (hopefully) with the same shift.
  • Now use what we learned about frequency analysis to figure out the words in each group. Keep in mind that each shift corresponds to a row in Falconer's counter-table and that the row markers should spell out a keyword.
  • What does our message say? What was the keyword?
  • How did finding the length of the keyword help reduce this problem to one we had already solved?
Reflection:.

Exactly one hundred years after Vigenère published his work Falconer lead us in the right direction to crack the polyalphabetic substitution cipher. First, he pointed out that whether we encipher each new line, word, or letter by a different alphabet if we can group elements of the message which were enciphered the same way together then we can treat each group as a monoalphabetic substitution cipher. Additionally, if we can identify the length of the key then we can use that to figure out how to group the strings or characters together. However, Falconer was still very much tied down to the use of word spacings, without them his descriptions and attacks would not work. It would be another century and a half before Charles Babbage and Friedrich Kasiski would recognize how to expand these ideas into a general plan of attack.