Trigraph

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:

Playfair-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, …

Kahn-01

… 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.

Klaus-Raleigh

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.


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/

Subscribe to Blog via Email

Gib Deine E-Mail-Adresse an, um diesen Blog zu abonnieren und Benachrichtigungen über neue Beiträge via E-Mail zu erhalten.

Kommentare (10)

  1. #1 Thomas
    5. September 2018

    I think Levine described the method in this article https://www.marksmath.com/old-papers/levine-1.pdf&ved=2ahUKEwiPkKbF1KTdAhWQb1AKHSo8DHgQFjABegQIBxAB&usg=AOvVaw39MASActcd2lsXbqvw97IQ. On page 172 he states to have developed matrix substitution for cryptographic purposes several years prior to Hill, most likely he refers to a publication in 1929.

  2. #3 Thomas
    5. September 2018

    @Klaus
    You wrote:”the method he published in 1929″. I’m not sure if Levine published the method in 1929. What Kahn says is that Livine had devised the method “about 1929”. Maybe this was Kahn’s conclusion from Levine’s claim in the linked article from 1958, that he had developed matrix substitution prior to Hill, i.e. prior to Hill’s article from 1929.

  3. #4 Thomas
    5. September 2018

    According to this excerpt from the Levine papers published by Craig Bauer, https://books.google.de/books?id=f4PNBQAAQBAJ&pg=PA227, Levine’s matrix encryption method was first published by ACA member Ohaver in 1926 in two issues of Fynn’s Weekly magazine. Apparently Levine himself published it not before 1958.

  4. #5 Klaus Schmeh
    5. September 2018

    @Thomas: Thank you very much! Apparently, the mystery is solved. Perhaps, I can use this method to create a challenge.

  5. #6 Tony
    6. September 2018

    For the benefit of readers (current or future) of this blog, I would like to point out that the matrix-based work of Levine and Hill, as described in the links Thomas provides above, as “mod 26”, were greatly extended by Professor Rodney Cooper to Galois Field GF(p^n) where p is the PRIME alphabet size, and for those not familiar with the notation “p^n”, that represents a POLYNOMIAL (as every element of the matrix or vector), and all the math is subject both to a prime modulus and also a monic irreducible polynomial. The citation to Cooper’s paper “Linear Transformations in Galois Fields and Their Application to Cryptography” is: Cryptologia, volume 4 number 3 (1980), pages 184-188. The abstract is: “A plaintext message is first subdivided into groups of n letters and then mapped on the Galois Field GF(p^n) where p is the [prime] alphabet size. The elements of the Galois Field so obtained are considered as the components of a vector V and submitted to a linear transformation within the field. In the event that n=1 the algorithm reduces to the famous Hill cipher.” Even with 1988 PC technology, it was possible to create matrices, not of size 2×2 or 3×3 or 4×4 as described in the links Thomas provided, but instead GF(17^10) polynomials in a 56×56 matrix, or 125,440 bits in the key matrix. Alternatively, using integers instead of polynomials, GF(2147483647) is one choice, which is a beautiful integer, the eighth Mersenne prime, equal to 2^31 − 1. According to Wikipedia at https://en.wikipedia.org/wiki/2,147,483,647 the primality of this number was proven by Leonhard Euler, who reported the proof in a letter to Daniel Bernoulli written in 1772. Consider that even with 1992 PC technology it was possible to implement GF(2147483647) and key matrices larger than 1000×1000, which is key matrices containing more than 50 million bits.

  6. #7 Thomas
    6. September 2018

    Ohaver’s explanation of Levines cipher in Flynn’s Weekly (22 Nov. 1926):

    “In Mr. Levine’s, No. 6, we have a remarkably simple and efficacious method of combining two messages in the same cryptogram. This cipher is based on the following two alphabets:

    A B C D E F G H I J K L M
    1 2 3 4 5 6 7 8 9 10 11 12 13
    27 28 29 30 31 32 33 34 35 36 37 38 39

    N O P Q R S T U V W X Y Z
    14 15 16 17 18 19 20 21 22 23 24 25 26
    40 41 42 43 44 45 46 47 48 49 50 51 52

    To illustrate the method of encipherment, take the first letters of the two present messages, C (29) of the first message, COME HERE, and S (19) of the second message, STAY AWAY. The substitute for these two letters is 24 5, one of which numbers (24) is half the sum of 29 and 19, and the other (5) the difference between this 24 and either 29 or 19. Mr. Levine expresses this relation algebraically, thus:

    x + y = 29 x — y = 19 2x = 48 x = 24 y = 5

    In deciphering, the numbers must be taken in pairs. To get the first message, COME HERE, add the numbers of each pair. The sums will indicate the letters in the 27-to-52 alphabet. The second message, STAY AWAY, is deciphered by taking the differences between the numbers of each pair, these indicating letters in the i-to-2 6 alphabet.

    Cryptogram: 24 5 30¼ 10¼ 20 19 28 3 … Sums: 29 41 39 31 Message No. 1: C O M E … Differences: 19 20 1 23 Message No. 2: S T A Y …

    A system of this kind offers the advantage of sending a real and a supposed message in the same cryptogram. Should the cryptogram be intercepted, suspicion might be diverted by explaining the supposed message. The real message might in this way escape detection. Incidentally, fractions could be avoided in this cipher by using only the even numbers from 2 to 104. Ingenious cipher fans will find a thousand and one occasions in which a cryptogram of this sort may be useful. Prying eyes are likely to accept the supposed message as the ultimate one and neglect further attempts to read it. Without having achieved an indecipherable cipher, its user may have accomplished similar ends.” ( https://toebes.com/Flynns/Flynns-19261113.htm)

    To put it mildly, a very simple predecessor of matrix encryption.

  7. #8 Joshua Holden
    8. September 2018

    The method of Levine’s that Thomas found is extremely interesting as a precursor to Hill’s method, and also as an early example of a subliminal channel, but it really doesn’t seem to be “six 5×5 squares to encipher trigraphs in an ingenious extension of the Playfair.” Kahn’s notes on Levine’s method refer to a letter from 1964 (unpublished?) and something in _The_Cryptogram_ from January-February 1961. Does anyone have a copy of that issue? (I wrote a short article on Levine’s 1926 method which is posted at , BTW.)

  8. #9 Joshua Holden
    8. September 2018

    Hmm, the site seems to have filtered out my URL. How are people getting URL’s into their comments?

  9. #10 Thomas
    8. September 2018

    This could be the article “Problems in Cryptanalysis: The Principle of Double Duty, a Trigraphic Playfair,” in “The cryptogram” 1961. Apparently “The cryptogram” isn’t online, but perhaps an ACA member (Klaus, isn’t there an ACA Facebook group?) has access to the issue 1/1961.