Section 4.1 A Simple Solution
Objectives
- Factoring Integers
- Falconer's Solution to the Columnar Transposition
Subsection 4.1.1 The Power of Prime Factors
The strength of Falconer's keyed columnar transposition cipher is the almost astronomical number of combinations of keys that can be used. As we have seen previously with just three characters we have six row keys which, depending on how many of them we use and how we arrange them, can give us one thousand nine hundred fifty six subtly different ciphers. If we increase the number of characters to four or five then that number goes up to
and
respectively. This would seem to offer security in the extreme, but as we will see, Falconer himself gives us two relatively simple ways to crack this cipher. We begin with the more mathematical approach.
... take the number of partitions of the seeming words in the epistle, and find out their several divisors, which may be performed by the following rules.
How to find out the equal divisors of any number.
1. Divide the number given by some prime number (i.e.) such a number that cannot be divided, but by it self, or unity; and the quotient by some or other prime number, and the last quotient again by a prime number; and so go on until the last quotient of all be one; and thus you shall find a certain number of prime divisors.
2. Make a rectangular table that shall consist of as many columns as you have prime divisors, which you must place one after another at the tops of the columns; ...
By multiplying the first prime divisor towards the left hand of the table by the second, and writing the product under the second.
Next, by the third prime divisor, multiplying all the figures in the table towards the left hand, setting the several products in the third column: and so forth, throughout all the prime divisors; ...
Example to find out all the divisors of 450
| 450 | 225 | 75 | 25 | 5 | 1 |
| 2 | 3 | 3 | 5 | 5 |
The first line contains the first divided, and the respective quotients; the lowest line is the several prime divisors.
Now 450, the number given, being divided by 2, a prime divisor, the quotient is 225, which being divided by 3, you have 75 for a new quotient; and again divided by 3, you have 25 for another quotient. This last divided by 5, gives 5, which being a prime number, you have 1, or unity in the last quotient of all: so that your prime divisors are, 2, 3, 3, 5, 5, all which set down in the tops of the columns [of a new table], and multiplying them according to the [second] rule given, the operation will stand thus.
| 2 | 3 | 3 | 5 | 5 |
| 6 | 9 | 10 | 25 | |
| 18 | 15 | 50 | ||
| 30 | 75 | |||
| 45 | 150 | |||
| 90 | 225 | |||
| 450 |
All the divisors of 450, are 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225; and one of them (supposing the epistle to have consisted of 450 seeming words) should have been the number of letters combined for the key: ...
- John Falconer [4, pp. 44-47 (72-75)]
Comprehension Check:
- What are prime numbers and what are the prime divisors of a number?
- How did Falconer decide to start dividing by 2?
- Have you ever learned a rule that may have told you that 225 and 75 were divisible by 3?
- Looking at the second table in the above quote, where do we get the numbers in the top row?
- In the second column of the second table there is a 6 under the 3, how did Falconer come up with that?
- In the third column how did he get the 9 and the 18?
- What about the other columns, where did those numbers come from?
- Falconer tells us to multiply each prime in the second table by all the figures to its left, why don't we get duplicate numbers then? What rule did he not explicitly state?
- In the last paragraph Falconer tells us that if 450 were the number of blocks of text in the enciphered message then one of the factors of 450 is the number of key letters in the message. Looking back at how Falconer's transposition cipher works why is this the case?
Checkpoint 4.1.1.
Test your understanding of what Falconer has described by factoring 210 into prime factors and then writing out all the different divisors
| 210 | 105 | 35 | 7 | 1 |
| 2 | 3 | 5 | 7 |
| 2 | 3 | 5 | 7 |
| 6 | 10 | 14 | |
| 15 | 21 | ||
| 30 | 42 | ||
| 35 | |||
| 70 | |||
| 105 | |||
| 210 |
First make a table of the primes factors by writing down the 210 and under that a 2 (since it is even), then next to the 210 write 105=210/2. Next, with a little work, we see that 105 is divisible by 3, so write 3 under the 105 and 35 next to 105, since 35=105/3. Continue this process to fill in Table 4.1.4 with the rest of the prime factors.
Now make a table with the prime factors written across the top. Starting with the second column, multiply each number in the table by all the numbers to its left by which it has not already been multiplied. So, we multiply 3 by 2 to get 6, then 5 by 2 to get 10 and so on. Try to finish filling in Table 4.1.5.
| 210 | 105 | 35 | ||
| 2 | 3 |
| 2 | 3 | 5 | 7 |
| 6 | 10 | 14 | |
| 21 | |||
| 210 |
Checkpoint 4.1.6.
Test your understanding of what Falconer has described by factoring 980 into prime factors and then writing out all the different divisors
| 980 | 490 | 245 | 49 | 7 | 1 |
| 2 | 2 | 5 | 7 | 7 |
| 2 | 2 | 5 | 7 | 7 |
| 4 | 10 | 14 | 49 | |
| 20 | 28 | 98 | ||
| 35 | 196 | |||
| 70 | 245 | |||
| 140 | 490 | |||
| 980 |
Checkpoint 4.1.9.
Look at the text enciphered below using Falconer's transposition cipher. Using the techniques described above, how many key letters may have been used to encipher this message?
NILOEOTHIETTSGTN HCITRTSRNIAEOIOC TATEUOOOETURHVFS LNEURRHYMSIHHIHQ EELHEFETTMRDUNRO NEAMTDPLHYETLOAS TTEPEEYTPEOESTTA THMOIITESHTEUPUE ETDSEBASETFEONOU OEKEBDAFASNHDSRT NSECLSEREWHHEICM EMTWKRIEBRNTAYTK TUEEFUWEREIAPTHA IYWAEUHBIFTWDRUD WHSLSNTOPLFNTEMN GRVEDCGTEPTDATIM RMSIIYLDEEECRBOE AEEBEINOTPNLEOAR SEOTLWLAIHTOTEOW RRMHLHINTAEULNFO DHLTAAAROREANLOH ETAUHHOEFEMEIETT HOTYTPNTRTSTGFBI AURSUPTHOHRHTWEN GEIATHLHNIIDVSRS FSRSNHFTNOUTIDHR EIUASTSREHGFLETI DDSEISTOTTIIELAE DEAREEAEENFOELEH NBETSIHENAEDHIDE
- Start by counting the number of blocks of letters.
- Use what we have learned to factor the number of blocks into its prime factors, and find all the possible divisors.
- Look back at how Falconer's transposition works (Subsection 3.4.2), what can the factors tell us about the enciphering process?
There are thirty blocks of text. Factoring that, we get the prime factors 2,3, and 5. Putting these together, the complete list of factors of 30 is 2, 3, 5, 6, 10, 15, and 30. Since Falconer's cipher requires writing letters into a table, we can conclude that the table's dimensions were likely 3 by 10, 5 by 6, 6 by 5, or 10 by 3. (It is unlikely that the table was 1 by 30 or 2 by 15.) Using this information we can conclude that there were likely 3, 5, or 6 key letters and we could try to pick apart the message.
Subsection 4.1.2 But Really There's an Easier Way (sort of)
After walking us through a careful exposition of how to find all the factors of a number and encouraging us to use this in order to find out the number of letters used for our key, Falconer lets us know that there is effectively an easier way to attack his own cipher.
“or rather for dispatch, take out the seeming words, and write them down in [columns] beginning at the first, and then proceed to the second, third, fourth, fifth, etc., until you have gone through them” - John Falconer [4, p.47 (75)]
Let's follow Falconer's advice using the message we used when we introduced his cipher in Section 3.4:
“\(\scriptsize\triangle\) EUS HJY TXZ UPE ISE QML COP BEN KVI WHO RRG OTD FL NEG OA”
Which transforms to the following when we rewrite it following Falconer's directions:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | E | H | T | U | I | Q | C | B | K | W | R | O | F | N | O |
| 2 | U | J | X | P | S | M | O | E | V | H | R | T | L | E | A |
| 3 | S | Y | Z | E | E | L | P | N | I | O | G | D | \(\cdot\) | G | \(\cdot\) |
“1. Search in the several lines for some of the particles [(words or n-grams)] of that language you shall suppose the epistle to have been writ in. If in English, make suppositions, e.g. for such little words as the, that, for, of, to, and, etc. and the like, without some of which no man can well express business of any moment.”
“2. Having supposed in any of the lines; for some one of those mentioned, or the like particles, you may prove the truth of your supposition, by taking out the opposite letters of all the lines: And if they do not make words, or syllables, or produce such letters as can probably follow one another in that order, your first supposition is false, and you must suppose anew.”
“3. Having by fresh suppositions found some useful word: And the letters of the other lines (in the same order) agreeing, the words or syllables arising from them, will direct you to some new [column] that goes before or after in the true order: And thus you may proceed till you have found out the whole writing, which by this time will be no great difficulty.” - John Falconer [4, pp.48-49 (76-77)]
Comprehension Check:
Taking Falconer's advice from step one look at each line of Table 4.1.10 we created above as you consider the following.
- Are there three letters in line one which we would expect to go together assuming this is written in English?
- There is a Q in row one column six, what needs to come after that? What column is it in?
- Looking now at line two what three letters do we again see that should go together?
- In line three are there three letters you could put together to get a common English ending? Are there other letters you could arrange with them in order to get an entire word?
- Finally, columns thirteen and fourteen only have two characters in them each, where do you think they belong if we were to rearrange the lines?
Use the observations you just made in order to rearrange the columns in the table, you should make a copy of this table to help you.
| Col's | |||||||||||||||
| 1 | |||||||||||||||
| 2 | |||||||||||||||
| 3 |
Test your understanding by working on the following exercises of increasing size, be patient they are finicky and time consuming. As a hint, all of the quotes contain the word WINTER.
Checkpoint 4.1.12.
Try to use this new method to decipher this quote.
IRPL WPDL FSNE INIH NIEE RBY OFY TNRY CEB EGC MAS SBH ERS CEE AHS
- Transpose each block, you will end up with a table of four lines and fifteen columns like Table 4.1.10.
- Can you find common or even not so common words or combinations in any lines?
- When you rearrange the columns do you see more words?
- Stay organized, if you don't keep things lined up this will never work
“If winter comes, can spring be far behind” By Percy Bysshe Shelly
Begin by writing each block of text vertically and looking for scrambled words. From the hint we know to look for the word WINTER. Spotting the letters to spell WINTER in the top row we rearrange the columns and then start to look for other words.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 I W F I N R O T C E M S E C A R P S N I B F N E G A B R E H P D N I E Y Y R B C S H A E S L L E H E Y
You should notice that columns 3 and 4 can spell IF in the first row and if we put them at the beginning we also get the word SPRING in the second row.
2 1 5 8 10 6 3 4 7 9 11 12 13 14 15 W I N T E R F I O C M E S C A P R I N G B S N F E A B R E H ...
Reassuringly we see that this also gives us the name PERCY in the third row and SHELLY wrapping around from row 3 to 4. Finally, you may notice that swapping columns 9 and 7, and columns 12 and 13 will give us the word COMES in the first row.
4 3 2 1 5 8 10 6 7 9 11 12 13 14 15 I F W I N T E R O C M S E C A N S P R I N G B F E A B R E H I N D P E R C Y Y B S H S E S H E L L E Y
After make those last two swaps we can now read off an entire message.
4 3 2 1 5 8 10 6 9 7 11 13 12 14 15 I F W I N T E R C O M E S C A N S P R I N G B E F A R B E H I N D P E R C Y B Y S S H E S H E L L E Y
“If winter comes, can spring be far behind” By Percy Bysshe Shelly
Checkpoint 4.1.13.
Try to use this new method to decipher this quote.
UIA ARM LDU GVN EWC RIE TSA HEF INV HRT STI TEC NMU EFO SRR UOH AE TTG TH HHO
- Transpose each block, you will end up with a table of four lines and fifteen columns like Table 4.1.10.
- Can you find common or even not so common words or combinations in any lines?
- When you rearrange the columns do you see more words?
- Stay organized, if you don't keep things lined up this will never work
“Laughter is the sun that drives winter from the human face.” Victor Hugo
Checkpoint 4.1.14.
Try to use this new method to decipher this quote.
WYTWIA TAODLH IDHLES ASAHGD NETIAH ENHTNA OHDNTC SWNEHE OTEIDR HSNUNS FHWSWL TEISIE MHORIK OUDMTD SNBMEI ESLERC CECTHS AIWINE HSOHE RNSNTN
- Transpose each block, you will end up with a table of four lines and fifteen columns like Table 4.1.10.
- Can you find common or even not so common words or combinations in any lines?
- When you rearrange the columns do you see more words?
- Stay organized, if you don't keep things lined up this will never work
“It was one of those March days, when the sun shines hot and the wind blows cold. When it is summer in the light and winter in the shade.” Charles Dickens
Part of what helped you in the previous three examples was knowing that the word WINTER was in each quote, this is called a crib.
Definition 4.1.15. Cryptologic Crib.
In cryptology a crib is a piece of information about a cipher text, such as a known piece of the plain text, which helps you decrypt the cipher.
A few closing observations:
- Look carefully at how the blocks of characters (columns in the tables) are grouped after they are deciphered, i.e. did you ever get column one next to column thirteen or fourteen?
- Why do you think this happened? How might it be related to the number of key letters?
- Given your answers to the previous questions, how can we make use of Falconer's strategies for finding divisors and the number of key letters?
Subsection 4.1.3 Mathematical Interlude
Prime numbers and factors are significant in mathematics and play a central role not just here but in modern cryptographic systems used by computers. Therefore, a clear definition of primes and divisibility are crucial.
Definition 4.1.16. Divisibility.
We say that one whole number \(a\) is divisible by another whole number \(b\) if there exists a unique whole number \(q\) called the quotient such that \(a=qb\text{.}\)
Definition 4.1.17. Prime Number and Factor.
A number is prime if it is divisible only by one and its self. A prime factor of a number is a prime number which divides evenly, without remainder, into that number.