Global Math Week: Around the World from Unsolved to Solved

by Craig Bauer

BauerWhat hope do we have of solving ciphers that go back decades, centuries, or even all the way back to the ancient world? Well, we have a lot more hope than we did in the days before the Internet. Today’s mathematicians form a global community that poses a much greater threat to unsolved problems, of every imaginable sort, than they have every faced before.

In my Princeton University Press book, Unsolved! The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies, I collected scores of the most intriguing unsolved ciphers. It’s a big book, in proper proportion to its title, and I believe many of the ciphers in it will fall to the onslaught the book welcomes from the world’s codebreakers, both professionals and amateurs. Why am I making this prediction with such confidence? Well, I gave a few lectures based on material from the book, while I was still writing it, and the results bode well for the ciphers falling.

Here’s what happened.

Early in the writing process, I was invited to give a lecture on unsolved ciphers at the United States Naval Academy. I was surprised, when I got there, by the presence of a video camera. I was asked if I was okay with the lecture being filmed and placed on YouTube. I said yes, but inside I was cursing myself for not having gotten a much needed haircut before the talk. Oh well. Despite my rough appearance, the lecture went well.[1] I surveyed some of the unsolved ciphers that I was aware of at the time, including one that had been put forth by a German colleague and friend of mine, Klaus Schmeh. It was a double transposition cipher that he had created himself to show how difficult it is to solve such ciphers. He had placed it in a book he had written on unsolved ciphers, a book which is unfortunately only available in German.[2] But to make the cipher as accessible as possible, he assured everyone that that particular bit of writing was in English.

 

VESINTNVONMWSFEWNOEALWRNRNCFITEEICRHCODEEA

HEACAEOHMYTONTDFIFMDANGTDRVAONRRTORMTDHE

OUALTHNFHHWHLESLIIAOETOUTOSCDNRITYEELSOANGP

VSHLRMUGTNUITASETNENASNNANRTTRHGUODAAARAO

EGHEESAODWIDEHUNNTFMUSISCDLEDTRNARTMOOIREEY

EIMINFELORWETDANEUTHEEEENENTHEOOEAUEAEAHUHI

CNCGDTUROUTNAEYLOEINRDHEENMEIAHREEDOLNNIRAR

PNVEAHEOAATGEFITWMYSOTHTHAANIUPTADLRSRSDNOT

GEOSRLAAAURPEETARMFEHIREAQEEOILSEHERAHAOTNT

RDEDRSDOOEGAEFPUOBENADRNLEIAFRHSASHSNAMRLT

UNNTPHIOERNESRHAMHIGTAETOHSENGFTRUANIPARTAOR

SIHOOAEUTRMERETIDALSDIRUAIEFHRHADRESEDNDOION

ITDRSTIEIRHARARRSETOIHOKETHRSRUAODTSCTTAFSTHCA

HTSYAOLONDNDWORIWHLENTHHMHTLCVROSTXVDRESDR

Figure 1. Klaus Schmeh’s double transposition cipher challenge.

When the YouTube video went online, it was seen by an Israeli computer scientist, George Lasry, who became obsessed with it. He was not employed at the time, so he was able to devote a massive amount of time to seeking the solution to this cipher. As is natural for George, he attacked it with computer programs of his own design. He eventually found himself doing almost nothing other than working on the cipher. His persistence paid off and he found himself reading the solution.

I ended up being among the very first to see George’s solution, not because I’m the one who introduced him to the challenge via the YouTube video, but because I’m the editor-in-chief of the international journal (it’s owned by the British company Taylor and Francis) Cryptologia. This journal covers everything having to do with codes and ciphers, from cutting edge cryptosystems and attacks on them, to history, pedagogy, and more. Most of the papers that appear in it are written by men and women who live somewhere other than America and it was to this journal that George submitted a paper describing how he obtained his solution to Klaus’s challenge.

George’s solution looked great to me, but I sent it to Klaus to review, just to be sure. As expected, he was impressed by the paper and I queued it up to see print. The solution generated some media attention for George, which led to him being noticed by people at Google (an American company, of course). They approached him and, after he cleared the interviewing hurdles, offered him a position, which he accepted. I was very happy that George found the solution, but of course that left me with one less unsolved cipher to write about in my forthcoming book. Not a problem. As it turns out there are far more intriguing unsolved ciphers than can be fit in a single volume. One less won’t make any difference.

Later on, but still before the book saw print, I delivered a similar lecture at the Charlotte International Cryptologic Symposium held in Charlotte, North Carolina. This time, unlike at the Naval Academy, Klaus Schmeh was in the audience.

One of the ciphers that I shared was fairly new to me. I had not spoken about it publicly prior to this event. It appeared on a tombstone in Ohio and seemed to be a Masonic cipher. It didn’t look to be sophisticated, but it was very short and shorter ciphers are harder to break. Brent Morris, a 33rd degree Mason with whom I had discussed it, thought that it might be a listing of initials of offices, such as PM, PHP, PIM (Past Master, Past High Priest, Past Illustrious Master), that the deceased had held. This cipher was new to Klaus and he made note of it and later blogged about it. Some of his followers collaborated in an attempt to solve it and succeeded. Because I hadn’t even devoted a full page to this cipher in my book, I left it in as a challenge for readers, but also added a link to the solution for those who want to see the solution right away.

Bauer

Figure 2. A once mysterious tombstone just south of Metamora, Ohio.

So, what was my role in all of this? Getting the ball rolling, that’s all. The work was done by Germans and an Israeli, but America and England benefited as well, as Google gained yet another highly intelligent and creative employee and a British owned journal received another great paper.

I look forward to hearing from other people from around the globe, as they dive into the challenges I’ve brought forth. The puzzles of the past don’t stand a chance against the globally networked geniuses of today!

Craig P. Bauer is professor of mathematics at York College of Pennsylvania. He is editor in chief of the journal Cryptologia, has served as a scholar in residence at the NSA’s Center for Cryptologic History, and is the author of Unsolved!: The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. He lives in York, Pennsylvania.

 

[1] It was split into two parts for the YouTube channel. You can see them at https://www.youtube.com/watch?v=qe0JhEajfj8 (Part 1) and https://www.youtube.com/watch?v=5L12gjgMOMw (Part 2). A few years later, I got cleaned up and delivered an updated version of the talk at the International Spy Museum. That talk, aimed at a wider audience, may be seen at https://www.youtube.com/watch?v=rsdUDdkjdQg.

[2] Schmeh, Klaus, Nicht zu Knacken, Carl Hanser Verlag, Munich, 2012.

Cipher challenge #2 from Joshua Holden: Subliminal channels

The Mathematics of Secrets by Joshua Holden takes readers on a tour of the mathematics behind cryptography. Most books about cryptography are organized historically, or around how codes and ciphers have been used in government and military intelligence or bank transactions. Holden instead focuses on how mathematical principles underpin the ways that different codes and ciphers operate. Discussing the majority of ancient and modern ciphers currently known, The Mathematics of Secrets sheds light on both code making and code breaking. Over the next few weeks, we’ll be running a series of cipher challenges from Joshua Holden. The first was on Merkle’s puzzles. Today’s focuses on subliminal channels:

As I explain in Section 1.6 of The Mathematics of Secrets, in 1929 Lester Hill invented the first general method for encrypting messages using a set of multiple equations in multiple unknowns.  A less general version, however, had already appeared in 1926, submitted by an 18-year-old to a cryptography column in a detective magazine.  This was Jack Levine, who would later become a prolific researcher in several areas of mathematics, including cryptography.

Levine’s system was billed as a way of encrypting two different messages at the same time.  Maybe one of them was the real message and the other was a dummy message–if the message was intercepted, the interceptor could be thrown off the scent by showing them the dummy message.  This sort of system is now known as a subliminal channel.

The system starts with numbering the letters of the alphabet in two different ways:

   a  b  c  d  e  f  g  h  i  j  k  l  m
  27 28 29 30 31 32 33 34 35 36 37 38 39
   1  2  3  4  5  6  7  8  9 10 11 12 13
  
   n  o  p  q  r  s  t  u  v  w  x  y  z
  40 41 42 43 44 45 46 47 48 49 50 51 52
  14 15 16 17 18 19 20 21 22 23 24 25 26

Suppose the first plaintext, or unencrypted message, is “tuesday” and the second plaintext is “tonight.”  We use the first set of numbers for the first plaintext:

   t  u  e  s  d  a  y
  46 47 31 45 30 27 51

and the second set for the second plaintext:

   t  o  n  i  g  h  t
  20 15 14  9  7  8 20

The encrypted message, or ciphertext, is made up of pairs of numbers.  The first number in each pair is half the sum of the two message numbers, and the second number is half the difference:

    t       u        e       s       d       a        y
   46      47       31      45      30      27       51
  
    t       o        n       i       g       h        t
   20      15       14       9       7       8       20
  
33,13    31,16  22½,8½   27,18 18½,11½  17½,9½  35½,15½

To decrypt the first message, just take the sum of the two numbers in the pair, and to decrypt the second message just take the difference.  This works because if P1 is the first plaintext number and P2 is the second, then the first ciphertext number is

and the second is

Then the plaintext can be recovered from the ciphertext using

and

This system is not as secure as Hill’s because it gives away too much information.  For starters, the existence and nature of the fractions is a clue to the encryption process.  (The editor of the cryptography column suggested doubling the numbers to avoid the fractions, but then the pattern of odd and even numbers would still give information away.)  Also, the first number in each pair is always between 14 and 39 and is always larger than the second number, which is always between ½ and 25 ½.  This suggests that subtraction might be relevant, and the fact that there are twice as many numbers as letters might make a codebreaker suspect the existence of a second message and a second process.  Hill’s system solves some of these issues, but the problem of information leakage continues to be relevant with modern-day ciphers.

With those hints in mind, can you break the cipher used in the following message?

11 3/5, 15 4/5   10 4/5,  9 2/5   17,     11        14 1/5, 16 3/5
 9 4/5,  7 2/5   12 3/5,  7 4/5    9 2/5, 12  1/5   13 1/5, 13 3/5
18,     11       12 2/5, 14 1/5    8 4/5, 10  2/5   12 1/5,  6 3/5
15 4/5, 12 2/5   13 3/5, 13 4/5   12,     16        11 2/5,  8 1/5
 9 1/5, 16 3/5   14,     17       16 3/5, 12  4/5    9 4/5, 14 2/5
12 1/5,  6 3/5   11 3/5, 15 4/5   10,     11        11 4/5,  6 2/5
10 2/5, 14 1/5   17 2/5, 12 1/5   14 3/5,  9  4/5

Once you have the two plaintexts, can you deduce the process used to encrypt them?

 

Answer to Cipher Challenge #1: Merkle’s Puzzles

The hole in the version of Merkle’s puzzles is that the shift we used for encrypting is vulnerable to a known-plaintext attack. That means that if Eve knows the ciphertext and part of the plaintext, she can get the rest of the plaintext. In Cipher Challenge #1, she knew that the word “ten” is part of the plaintext. So she shifts it until she finds a ciphertext that matches one of the puzzles:

ten
UFO
VGP

“Aha!” says Eve. “The first puzzle starts with VGP, so it must decrypt to ten!” Then she decrypts the rest of the puzzle:

VGPVY QUGXG PVYGP VAQPG UKZVG GPUGX GPVGG PBTPU XSNHT JZFEB
whqwz rvhyh qwzhq wbrqh vlawh hqvhy hqwhh qcuqv ytoiu kagfc
xirxa swizi rxair xcsri wmbxi irwiz irxii rdvrw zupjv lbhgd
yjsyb txjaj sybjs ydtsj xncyj jsxja jsyjj sewsx avqkw mcihe
                             ⋮
qbkqt lpbsb kqtbk qvlkb pfuqb bkpbs bkqbb kwokp snico euazw
rclru mqctc lrucl rwmlc qgvrc clqct clrcc lxplq tojdp fvbax
sdmsv nrdud msvdm sxnmd rhwsd dmrdu dmsdd myqmr upkeq gwcby
tentw oseve ntwen tyone sixte ensev entee nzrns vqlfr hxdcz

So the secret key is 2, 7, 21, 16.

The hole can be fixed by using a cipher that is less vulnerable to known-plaintext attacks. Sections 4.4 and 4.5 of The Mathematics of Secrets give examples of ciphers that would be more secure.