In his ground-breaking book “The Codebreakers”, David Kahn mentions a manual encryption method from 1929 he calls “ingenious”. However, neither Kahn’s book nor any other literature source I know gives a description of this method.
Frequent readers of this blog certainly know that designing a secure and convenient manual cipher is a challenge that has never been solved in a satisfactory way. Here are the best manual cipher designs I am aware of:
- The Double Column Transposition (DCT, also known as “double cube”) is considered a good manual cipher. For the DCT to be secure, both keywords need to have at least 25 letters.
- ADFGVX (a World War I cipher) is another potentially secure manual cipher, provided that the second step of this method (a transposition) is carried out twice.
- There’s an encryption algorithm based on Rubik’s Cube. While this method is not purely manual, it doesn’t require a computer.
- Solitaire is a cipher invented by Bruce Schneier. It uses a deck of cards. While Solitaire is considered secure, it is too complicated for longer messages.
- Handycipher was invented by Bruce Kallick. I blogged about it in 2017.
- LC4 is another cipher that can be computed by hand. According to its creator, it is both secure and easy to use.
- Pocket-RC4, Mirdek, and Card-Chameleon are other manual ciphers. I have not looked at them in detail yet.
The Playfair Cipher
Another manual encryption systems that is easy to use and secure at least for short messages is the Playfair Cipher. The Playfair cipher substitutes letter pairs (bigrams). So, the cleartext needs to be written as a sequence of letter pairs (the following cleartext is a Shakespeare quote taken from Robert Thouless’ life-after-death experiment):
BA LM OF HU RT MI ND SG RE AT NA TU RE SS EC ON DC OU RS EC HI EF NO UR IS HE RI NL IF ES FE AS T
The Playfair cipher requires that no letter pair consist of two equal letters. Therefore, we add an X between the two Ss:
BA LM OF HU RT MI ND SG RE AT NA TU RE SX SE CO ND CO UR SE CH IE FN OU RI SH ER IN LI FE SF EA ST
If the number of letters in the cleartext was odd, another X would have to be added at the last position, but this is not necessary here. Next, we choose a keyword: SURPRISE. Now, we set up a 5×5 matrix, which starts with the keyword (repeating letters are omitted), followed by the remaining alphabet (I and J are considered equal in order to get an alphabet of 25 letters):
S U R P I
E A B C D
F G H K L
M N O Q T
V W X Y Z
Now, we replace the cleartext letter pairs (BA, LM, OF, HU, …) according to the three Playfair rules. Here are the rules in a diagram:
Here are the same rules as a text (I refer to the letter pair to be replaced as XY):
- If X and Y are not in the same column and not in the same row (this is the most frequent case), form a rectangle and replace the two letters by the other two corner letters (the upper cleartext letter is replaced by the other upper letter in the rectangle, the lower cleartext letter by the lower one). For instance, LM becomes FT.
- If the two letters stand in the same row, each one is replaced by its right neighbor. Here, BA becomes CB.
- If the two letters stand in the same column, each one is replaced by its lower neighbor. In our example, AN becomes GW.
When we apply the Playfair rules on our cleartext with our 5×5 matrix, we get the following ciphertext:
CB FT MH GR IO TS TA UF SB DN WG NI SB RV EF BQ TA BQ RP EF BK SD GM NR PS RF BS UT TD MF EM AB IM
Breaking a Playfair cryptogram consisting of a few dozen letters was quite a challenge before the computer age. However, since computers are available, techniques like Hill Climbing or dictionary attacks break a Playfair Ciphers within seconds, unless the ciphertext is very short.
Trigram substitution
Already by the end of the 19th century, cryptologists tried to generalize the concept of the Playfair Cipher by substituting letter triples (trigrams) instead of letter pairs (bigrams). In his seminal book The Codebreakers, David Kahn, …
… the founder of crypto history research, wrote:
Cryptographers tried to extend the Playfair cipher to trigraphic substitutions. Nearly all have failed. Perhaps the best known effort was that of Count Luigi Gioppi di Türkheim, who in 1897 produced a pseudo-trigrapphic system in which two letters were monoalphabetically enciphered and the third depended only on the second. Finally, about 1929, a young American mathematician, Jack Levine, used six 5×5 squares to encipher trigraphs in an ingenious extension of the Playfair. But he did not disclose his method. This was the situation when a 38-year-old assistant professor of mathematics at Hunter College in New York published a seven-page paper entitled “Cryptography in an Algebraic Alphabet” in The American Mathematical Monthly for June-July 1929. He was Lester S. Hill.
In fact, the Hill cipher, as this system is referred to today, became the best-known trigraph substitution method. It is based on matrix multiplications. A good description of it is available on Wikipedia. Hill even constructed a machine that implemented this method. This machine was used by the US Army during World Word II to encrypt three-letter identification codes. Apart from this, the Hill Cipher never saw widespread use. As matrix multiplications are invertible, it proved not secure enough.
The Levine method
Whille the Hill Cipher is described in many crypto books and on several web pages, the “ingenious extension of the Playfair” mentioned in the The Codebreakers is a mystery to me. No literature source I am aware of describes it. The only thing I have found online is another trigram-based Playfair extension (“Playfair for Three“), which is described on John Savard’s website. I don’t know if it is similar to Levine’s scheme.
Strangely, it is very likely that two years ago I had a description of Levine’s trigram method in my hands. This is because in spring 2016 I spent a day in the James B. Hunt Library at the University of Raleigh, NC, where the crypto research files Levine left behind are kept. Apparently, Levine was a very active cryptologist, so his files fill dozens of boxes.
When I searched through this collection, the trigram method mentioned by Kahn was not in my focus. Anyway, I noticed hundreds of handwritten pages about trigram substitution, which indicates that Levine was quite interested in this kind of encryption and that he invested a lot of work in the development of the method he published in 1929. However, I didn’t come across a paper that described this particular algorithm.
Now my question is: Does a reader know a detailed description of the Levine trigram substitution? If so, please leave a comment.
Follow @KlausSchmeh
Further reading: A mird in the hand is worth two in the mush: Solving ciphers with Hill Climbing
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (11)