Section 4.2 A Seventeenth Century Idea
Objectives
- Falconer's Attack
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:
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.