Pariah Moonshine Part II: For Whom the Moon Shines

by Joshua Holden

This post originally appeared on The Aperiodical. We republish it here with permission. 

HoldenI ended Part I with the observation that the Monster group was connected with the symmetries of a group sitting in 196883-dimensional space, whereas the number 196884 appeared as part of a function used in number theory, the study of the properties of whole numbers.  In particular, a mathematician named John McKay noticed the number as one of the coefficients of a modular form.  Modular forms also exhibit a type of symmetry, namely if F is a modular form then there is some number k for which

Figure 1

for every set of whole numbers a, b, c, and d such that adbc=1.  (There are also some conditions as the real part of z goes to infinity.)

Modular forms, elliptic curves, and Fermat’s Last Theorem

In 1954, Martin Eichler was studying modular forms and observing patterns in their coefficients.  For example, take the modular form

Figure 2

(I don’t know whether Eichler actually looked at this particular form, but he definitely looked at similar ones.)  The coefficients of this modular form seem to be related to the number of whole number solutions of the equation

y2 = x3 – 4 x2 + 16

This equation is an example of what is known as an elliptic curve, which is a curve given by an equation of the form

y2 = x3 + ax2 + bx + c

Note that elliptic curves are not ellipses!  Elliptic curves have one line of symmetry, two open ends, and either one or two pieces, as shown in Figures 1 and 2. They are called elliptic curves because the equations came up in the seventeenth century when mathematicians started studying the arc length of an ellipse.  These curves are considered the next most complicated type of curve after lines and conic sections, both of which have been understood pretty well since at least the ancient Greeks.   They are useful for a lot of things, including cryptography, as I describe in Section 8.3 of The Mathematics of Secrets.

Figure 1

Figure 1. The elliptic curve y2= x3 + x has one line of symmetry, two open ends, and one piece.

Figure 2

Figure 2. The elliptic curve y2 = x3 – x has one line of symmetry, two open ends, and two pieces.

 

In the late 1950’s it was conjectured that every elliptic curve was related to a modular form in the way that the example above is.  Proving this “Modularity Conjecture” took on more urgency in the 1980’s, when it was shown that showing the conjecture was true would also prove Fermat’s famous Last Theorem.  In 1995 Andrew Wiles, with help from Richard Taylor, proved enough of the Modularity Conjecture to show that Fermat’s Last Theorem was true, and the rest of the Modularity Conjecture was filled in over the next six years by Taylor and several of his associates.

Modular forms, the Monster, and Moonshine

Modular forms are also related to other shapes besides elliptic curves, and in the 1970’s John McKay and John Thompson became convinced that the modular form

J(z) = e -2 π i z + 196884 e 2 π i z + 21493760 e 4 π i z  + 864299970 e 6 π i z  + …

was related to the Monster.  Not only was 196884 equal to 196883 + 1, but 21493760 was equal to 21296876 + 196883 + 1, and 21296876 was also a number that came up in the study of the Monster.  Thompson suggested that there should be a natural way of associating the Monster with an infinite-dimensional shape, where the infinite-dimensional shape broke up into finite-dimensional pieces with each piece having a dimension corresponding to one of the coefficients of J(z).   This shape was (later) given the name V♮, using the natural sign from musical notation in a typically mathematical pun.  (Terry Gannon points out that there is also a hint that the conjectures “distill information illegally” from the Monster.) John Conway and Simon Norton formulated some guesses about the exact connection between the Monster and V♮, and gave them the name “Moonshine Conjectures” to reflect their speculative and rather unlikely-seeming nature. A plausible candidate for V♮ was constructed in the 1980’s and Richard Borcherds proved in 1992 that the candidate satisfied the Moonshine Conjectures.  This work was specifically cited when Borcherds was awarded the Fields medal in 1998.

The construction of V♮ turned out also to have a close connection with mathematical physics.  The reconciliation of gravity with quantum mechanics is one of the central problems of modern physics, and most physicists think that string theory is likely to be key to this resolution.  In string theory, the objects we traditionally think of as particles, like electrons and quarks, are really tiny strings curled up in many dimensions, most of which are two small for us to see.  An important question about this theory is exactly what shape these dimensions curl into.  One possibility is a 24-dimensional shape where the possible configurations of strings in the shape are described by V♮.  However, there are many other possible shapes and it is not known how to determine which one really corresponds to our world.

More Moonshine?

Since Borcherds’ proof, many variations of the original “Monstrous Moonshine” have been explored.  The other members of the Happy Family can be shown to have Moonshine relationships similar to those of the Monster.  “Modular Moonshine” says that certain elements of the Monster group should have their own infinite dimensional shapes, related to but not the same as V♮.  (The “modular” in “Modular Moonshine” is related to the one in “modular form” because they are both related to modular arithmetic, although the chain of connections is kind of long. )  “Mathieu Moonshine” shows that one particular group in the Happy Family has its own shape, entirely different from V♮, and “Umbral Moonshine” extends this to 23 other related groups which are not simple groups.  But the Pariah groups remained outsiders, rejected by both the Happy Family and by Moonshine — until September 2017.

Joshua Holden is professor of mathematics at the Rose-Hulman Institute of Technology. He is the author of The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption.

Pariah Moonshine Part I: The Happy Family and the Pariah Groups

by Joshua Holden

This post originally appeared on The Aperiodical. We republish it here with permission. 

HoldenBeing a mathematician, I often get asked if I’m good at calculating tips. I’m not. In fact, mathematicians study lots of other things besides numbers. As most people know, if they stop to think about it, one of the other things mathematicians study is shapes. Some of us are especially interested in the symmetries of those shapes, and a few of us are interested in both numbers and symmetries. The recent announcement of “Pariah Moonshine” has been one of the most exciting developments in the relationship between numbers and symmetries in quite some time. In this blog post I hope to explain the “Pariah” part, which deals mostly with symmetries. The “Moonshine”, which connects the symmetries to numbers, will follow in the next post.

What is a symmetry?

First I want to give a little more detail about what I mean by the symmetries of shapes. If you have a square made out of paper, there are basically eight ways you can pick it up, turn it, and put it down in exactly the same place. You can rotate it 90 degrees clockwise or counterclockwise. You can rotate it 180 degrees. You can turn it over, so the front becomes the back and vice versa. You can turn in over and then rotate it 90 degrees either way, or 180 degrees. And you can rotate it 360 degrees, which basically does nothing. We call these the eight symmetries of the square, and they are shown in Figure 1.

Figure1

Figure 1. The square can be rotated into four different positions, without or without being flipped over, for eight symmetries total.

If you have an equilateral triangle, there are six symmetries. If you have a pentagon, there are ten. If you have a pinwheel with four arms, there are only four symmetries, as shown in Figure 2, because now you can rotate it but if you turn it over it looks different. If you have a pinwheel with six arms, there are six ways. If you have a cube, there are 24 if the cube is solid, as shown in Figure 3. If the cube is just a wire frame and you are allowed to turn it inside out, then you get 24 more, for a total of 48.

Figure 2

Figure 2. The pinwheel can be rotated but not flipped, for four symmetries total.

Figure 3

Figure 3. The cube can be rotated along three different axes, resulting in 24 different symmetries.

These symmetries don’t just come with a count, they also come with a structure. If you turn a square over and then rotate it 90 degrees, it’s not the same thing as if you rotate it first and then flip it over. (Try it and see.) In this way, symmetries of shapes are like the permutations I discuss in Chapter 3 of my book, The Mathematics of Secrets: you can take products, which obey some of the same rules as products of numbers but not all of them. These sets of symmetries, which their structures, are called groups.

Groups are sets of symmetries with structure

Some sets of symmetries can be placed inside other sets. For example, the symmetries of the four-armed pinwheel are the same as the four rotations in the symmetries of the square. We say the symmetries of the pinwheel are a subgroup of the symmetries of the square. Likewise, the symmetries of the square are a subgroup of the symmetries of the solid cube, if you allow yourself to turn the cube over but not tip it 90 degrees, as shown in Figure 4.

Figure 4

Figure 4. The symmetries of the square are contained inside the symmetries of the cube if you are allowed to rotate and flip the cube but not tip it 90 degrees.

In some cases, ignoring a subgroup of the symmetries of a shape gets us another group, which we call the quotient group. If you ignore the subgroup of how the square is rotated, you get the quotient group where the square is flipped over or not, and that’s it. Those are the same as the symmetries of the capital letter A, so the quotient group is really a group. In other cases, for technical reasons, you can’t get a quotient group. If you ignore the symmetries of a square inside the symmetries of a cube, what’s left turns out not to be the symmetries of any shape.

You can always ignore all the symmetries of a shape and get just the do nothing (or trivial) symmetry, which is the symmetries of the capital letter P, in the quotient group. And you can always ignore none of the nontrivial symmetries, and get all of the original symmetries still in the quotient group. If these are the only two possible quotient groups, we say that the group is simple. The group of symmetries of a pinwheel with a prime number of arms is simple. So is the group of symmetries of a solid icosahedron, like a twenty-sided die in Dungeons and Dragons. The group of symmetries of a square is not simple, because of the subgroup of rotations. The group of symmetries of a solid cube is not simple, not because of the symmetries of the square, but because of the smaller subgroup of symmetries of a square with a line through it, as shown in Figures 5 and 6. The quotient group there is the same as the symmetries of the equilateral triangle created by cutting diagonally through a cube near a corner.

Figure 5

Figure 5. The symmetries of a square with line through it. We can turn the square 180 degrees and/or flip it, but not rotate it 90 degrees, so there are four.

Figure 6

Figure 6. The symmetries of the square with a line through it inside of the symmetries of the cube.

Categorizing the Pariah groups

As early as 1892, Otto Hölder asked if we could categorize all of the finite simple groups. (There are also shapes, like the circle, which have an infinite number of symmetries. We won’t worry about them now.)  It wasn’t until 1972 that Daniel Gorenstein made a concrete proposal for how to make a complete categorization, and the project wasn’t finished until 2002, producing along the way thousands of pages of proofs. The end result was that almost all of the finite simple groups fell into a few infinitely large categories: the cyclic groups, which are the groups of symmetries of pinwheels with a prime number of arms, the alternating groups, which are the groups of symmetries of solid hypertetrahedra in 5 or more dimensions, and the “groups of Lie type”, which are related to matrix multiplication over finite fields and describe certain symmetries of objects known as finite projective planes and finite projective spaces. (Finite fields are used in the AES cipher and I talk about them in Section 4.5 of The Mathematics of Secrets.)

Even before 1892, a few finite simple groups were discovered that didn’t seem to fit into any of these categories. Eventually it was proved that there were 26 “sporadic” groups, which didn’t fit into any of the categories and didn’t describe the symmetries of anything obvious — basically, you had to construct the shape to fit the group of symmetries that you knew existed, instead of starting with the shape and finding the symmetries. The smallest of the sporadic groups has 7920 symmetries in it, and the largest, known as the Monster, has over 800 sexdecillion symmetries. (That’s an 8 with 53 zeros after it!) Nineteen of the other sporadic groups turn out to be subgroups or quotient groups of subgroups of the Monster. These 20 became known as the Happy Family. The other 6 sporadic groups became known as the ‘Pariahs’.

The shape that was constructed to fit the Monster lives in 196883-dimensional space. In the late 1970’s a mathematician named John McKay noticed the number 196884 turning up in a different area of mathematics. It appeared as part of a function used in number theory, the study of the properties of whole numbers. Was there a connection between the Monster and number theory? Or was the idea of a connection just … moonshine?

Joshua Holden is professor of mathematics at the Rose-Hulman Institute of Technology. He is the author of The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption.

Craig Bauer: Attacking the Zodiac Killer

While writing Unsolved! The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies, it soon became clear to me that I’d never finish if I kept stopping to try to solve the ciphers I was covering. It was hard to resist, but I simply couldn’t afford to spend months hammering away at each of the ciphers. There were simply too many of them. If I was to have any chance of meeting my deadline, I had to content myself with merely making suggestions as to how attacks could be carried out. My hope was that the book’s readers would be inspired to actually make the attacks. However, the situation changed dramatically when the book was done.

I was approached by the production company Karga Seven Pictures to join a team tasked with hunting the still unidentified serial killer who called himself the Zodiac. In the late 1960s and early 70s, the Zodiac killed at least five people and terrorized entire cities in southern California with threatening letters mailed to area newspapers. Some of these letters included unsolved ciphers. I made speculations about these ciphers in my book, but made no serious attempt at cracking them. With the book behind me, and its deadline no longer a problem, would I like to join a code team to see if we could find solutions where all others had failed? The team would be working closely with a pair of crack detectives, Sal LaBarbera and Ken Mains, so that any leads that developed could be investigated immediately. Was I willing to take on the challenge of a very cold case? Whatever the result was, it would be no secret, for our efforts would be aired as a History channel mini-series. Was I up for it? Short answer: Hell yeah!

The final code team included two researchers I had corresponded with when working on my book, Kevin Knight (University of Southern California, Information Sciences Institute) and David Oranchak (software developer and creator of Zodiac Killer Ciphers. The other members were Ryan Garlick (University of North Texas, Computer Science) and Sujith Ravi (Google software engineer).

My lips are sealed as to what happened (why ruin the suspense?), but the show premieres Tuesday November 14, 2017 at 10pm EST. It’s titled “The Hunt for the Zodiac Killer.” All I’ll say for now is that it was a rollercoaster ride. For those of you who would like to see how the story began for me, Princeton University Press is making the chapter of my book on the Zodiac killer freely available for the duration of the mini-series. It provides an excellent background for those who wish to follow the TV team’s progress.

If you find yourself inspired by the show, you can turn to other chapters of the book for more unsolved “killer ciphers,” as well challenges arising from nonviolent contexts. It was always my hope that readers would resolve some of these mysteries and I’m more confident than ever that it can be done!

BauerCraig 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 Secret History: The Story of Cryptology. He lives in York, Pennsylvania.

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.

Craig Bauer: The Ongoing Mystery of Unsolved Ciphers (and new hope)

When a civilization first develops writing and few people are literate, simply putting a message down on paper can be all that is required to keep an enemy from understanding it. As literacy spreads, a more sophisticated method is needed, which is why codes and ciphers, a.k.a. “secret writing,” always follow closely on the heels of the discovery of writing. Over the millennia, ciphers have become extremely sophisticated, but so too have the techniques used by those attempting to break them.

In recent decades, everyone from mathematicians and computer scientists to artists and authors have created ciphers as challenges to specialists or the general public, to see if anyone is clever enough to unravel the secrets. Some, like the first three parts of James Sanborn’s sculpture Kryptos and the ciphers appearing in the television show Gravity Falls, have been solved, while others remain mysteries. The highly secretive online society known as Cicada 3301 has repeatedly issued such challenges as a means of talent scouting, though for what purpose such talented individuals are sought remains unknown. One unsolved cipher was laid down as a challenge by former British army intelligence officer Alexander d’Agapeyeff in his book Codes & Ciphers (1939). Sadly, when frustrated letters of enquiry reached the author, he admitted that he had forgotten how to solve it! Another was made by the famous composer Edward Elgar in 1897 as a riddle for a young lady friend of his. She, along with various experts, all failed to ferret out the meaning and Elgar himself refused to reveal it.

 

Elgar's cipher

Elgar’s cipher

 

Many unsolved ciphers appear in much more serious contexts. The serial killer who referred to himself as “The Zodiac” was responsible for at least five murders, as well as the creation of several ciphers sent to San Francisco newspapers. While the first of these ciphers was solved, others remain unbroken. Could a solution to one of these lead to an identification of the killer? Although many have speculated on his identity, it has never been firmly established. The Zodiac is not the only murderer to have left us such mysterious communiques, he is just the best known. Other killers’ secrets have persisted through relative obscurity. How many readers have heard of Henry Debsonys? In 1883, a jury sentenced him to death for the murder of his wife, after deliberating for only nine minutes. But this unfortunate woman was Henry’s third wife and the first two died under strange circumstances. Had Henry killed all of them? Will the ciphers he left behind confirm this? I think his ciphers will be among the first to fall this year, thanks to a major clue I provide in my book, Unsolved: The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. There are many more such criminal ciphers. One deranged individual even sent threatening letters containing ciphers to John Walsh of America’s Most Wanted fame! The FBI’s codebreakers maintain a list of their top unsolved ciphers. At present, only two of these are known to the public, but many others that didn’t make the top 10 are available for anyone to try to crack.

How do codebreakers, whether amateur or professional, meet the challenges they face? Statistics and other areas of mathematics often help, as do computers, but two of the codebreakers’ most powerful tools are context and intuition. This is why ciphers have often been broken by amateurs with no programming skills and little knowledge of mathematics. Enter Donald Harden, a high school history teacher, who with assistance from his wife Bettye, broke one of the Zodiac killer’s ciphers by guessing that the egotistical killer’s message would begin with “I” and contain the word “KILL.” Context allows the attacker to guess words, sometimes entire phrases, that might appear in the message. These are known as cribs. During World War II, the German word eins (meaning one) appeared in so many Nazi messages that a process known as “einsing” was developed, searching the cipher for the appearance of this word in every possible position. In today’s ciphers, the word President appears frequently.

Of course, time and again cribs and intuition can lead in the wrong direction. Indeed, the single most important attribute for a codebreaker is patience. A good codebreaker will have the ability to work on a cipher for months, for that is sometimes what it takes to reach a solution, ignoring the body’s normal demands for food and sleep; during World War I, the French codebreaker Georges Painvin lost 33 pounds over three months while sitting at a desk breaking the German ADFGX and ADFGVX ciphers.

Fig 2

Fig 3Is it possible that some of the earliest known ciphers, dating from the ancient world, have survived unread by anyone other than those they were created for? I believe this is the case and that they’ve been hiding in plain sight, like the purloined letter in Poe’s classic tale. Those studying ancient cultures have long been aware of so-called “nonsense inscriptions.” These appear on Egyptian sarcophagi, Greek vases, runestones, and elsewhere. They are typically dismissed as the work of illiterates imitating writing, merely because the experts cannot read them. But all of these cultures are known to have made use of ciphers and some of the contexts of the inscriptions are so solemn (e.g. sarcophagi) that it’s hard to believe they could be meaningless. I’d like to see a closer examination of these important objects. I expect some of the messages will be read in the near future, if cryptologists can form collaborations with linguists. These two groups have worked together successfully in military contexts for many decades. It is time that they also join forces for historical studies.

With a very large number of unsolved ciphers, spanning millennia, having been composed by a diverse group of individuals, it seems likely that it will take a diverse group of attackers, with skills ranging over many disciplines, to solve them. Some mysterious texts may reveal themselves to clever computer programmers or linguists, others to those taking the psychological approach, getting into the creator’s head and guessing phrases he or she used in the cipher, and some may be broken by readers who manage to discover related material in government archives or private hands that provides just enough extra information to make the break. I look forward to seeing the results!

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

Keith Devlin: Fibonacci introduced modern arithmetic —then disappeared

More than a decade ago, Keith Devlin, a math expositor, set out to research the life and legacy of the medieval mathematician Leonardo of Pisa, popularly known as Fibonacci, whose book Liber abbaci has quite literally affected the lives of everyone alive today. Although he is most famous for the Fibonacci numbers—which, it so happens, he didn’t invent—Fibonacci’s greatest contribution was as an expositor of mathematical ideas at a level ordinary people could understand. In 1202, Liber abbaci—the “Book of Calculation”—introduced modern arithmetic to the Western world. Yet Fibonacci was long forgotten after his death. Finding Fibonacci is a compelling firsthand account of his ten-year quest to tell Fibonacci’s story. Devlin recently answered some questions about his new book for the PUP blog:

You’ve written 33 math books, including many for general readers. What is different about this one?

KD: This is my third book about the history of mathematics, which already makes it different from most of my books where the focus was on abstract concepts and ideas, not how they were discovered. What makes it truly unique is that it’s the first book I have written that I have been in! It is a first-person account, based on a diary I kept during a research project spread over a decade.

If you had to convey the book’s flavor in a few sentences, what would you say?

KD: Finding Fibonacci is a first-person account of a ten-year quest to uncover and tell the story of one of the most influential figures in human history. It started out as a diary, a simple record of events. It turned into a story when it became clear that it was far more than a record of dates, sources consulted, places visited, and facts checked. Like any good story, it has false starts and disappointments, tragedies and unexpected turns, more than a few hilarious episodes, and several lucky breaks. Along the way, I encountered some amazing individuals who, each for their own reasons, became fascinated by Fibonacci: a Yale professor who traced modern finance back to Fibonacci, an Italian historian who made the crucial archival discovery that brought together all the threads of Fibonacci’s astonishing story, an American math professor who fought against cancer to complete the world’s first (and only) modern language translation of Liber abbaci, and the widow who took over and brought his efforts to fruition after he lost that battle. And behind it all, the man who was the focus of my quest. Fibonacci played a major role in creating the modern commercial world. Yet he vanished from the pages of history for five hundred years, made “obsolete,” and in consequence all but forgotten forever, by a new technology.

What made you decide to write this book?

KD: There were really two key decisions that led to this book. One was deciding, back in the year 2000, to keep a diary of my experiences writing The Man of Numbers. My first history book was The Unfinished Game. For that, all I had to do was consult a number of reference works. It was not intended to be original research. Basic Books asked me to write a short, readable account of a single mathematical document that changed the course of human history, to form part of a series they were bringing out. I chose the letter Pierre De Fermat wrote to his colleague Blaise Pascal in 1654, which most experts agree established modern probability theory, in particular how it can be used to predict the future.

In The Man of Numbers, in contrast, I set out to tell a story that no one had told before; indeed, the consensus among the historians was that it could not be told—there simply was not enough information available. So writing that book would require engaging in a lot of original historical research. I had never done that. I would be stepping well outside my comfort zone. That was in part why I decided to keep a diary. The other reason for keeping a record was to ensure I had enough anecdotes to use when the time came to promote the book—assuming I was able to complete it, that is. (I had written enough popular mathematics books to appreciate the need for author promotional activities!)

The second decision, to turn my diary into a book (which only at the end found the title, Finding Fibonacci), came after The Man of Numbers was published in 2011. The ten-year process of researching and writing that book had turned out to be so rich, and so full of unexpected twists and turns, including several strokes of immense luck, that it was clear there was a good story to be told. What was not clear was whether I would be able to write such a book. All my other books are third-person accounts, where I am simply the messenger. In Finding Fibonacci, I would of necessity be a central character. Once again, I would be stepping outside my comfort zone. In particular, I would be laying out on the printed page, part of my inner self. It took five years and a lot of help from my agent Ted Weinstein and then my Princeton University Press editor Vickie Kearn to find the right voice and make it work.

Who do you expect will enjoy reading this book?

KD: I have a solid readership around the world. I am sure they will all read it. In particular, everyone who read The Man of Numbers will likely end up taking a look. Not least because, in addition to providing a window into the process of writing that earlier book, I also put in some details of that story that I did not fully appreciate until after the book had been published. But I hope, and in fact expect, that Finding Fibonacci will appeal to a whole new group of readers. Whereas the star of all my previous books was a discipline, mathematics, this is a book about people, for the most part people alive today. It’s a human story. It has a number of stars, all people, connected by having embarked on a quest to try to tell parts of the story of one of the most influential figures in human history: Leonardo of Pisa, popularly known as Fibonacci.

Now that the book is out, in one sentence if you can, how would you summarize writing it?

KD: Leaving my author’s comfort zone. Without a doubt. I’ve never been less certain how a book would be received.

DevlinKeith Devlin is a mathematician at Stanford University and cofounder and president of BrainQuake, an educational technology company that creates mathematics learning video games. His many books include The Unfinished Game: Pascal, Fermat, and the Seventeenth-Century Letter That Made the World Modern and The Man of Numbers: Fibonacci’s Arithmetic Revolution. He is the author of Finding Fibonacci: The Quest to Rediscover the Forgotten Mathematical Genius Who Changed the World.

Cipher challenge #3 from Joshua Holden: Binary ciphers

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 last post was on subliminal channels. Today’s is on binary ciphers:

Binary numerals, as most people know, represent numbers using only the digits 0 and 1.  They are very common in modern ciphers due to their use in computers, and they frequently represent letters of the alphabet.  A numeral like 10010 could represent the (1 · 24 + 0 · 23 + 0 · 22 + 1 · 2 + 0)th = 18th letter of the alphabet, or r.  So the entire alphabet would be:

 plaintext:   a     b     c     d     e     f     g     h     i     j
ciphertext: 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010

 plaintext:   k     l     m     n     o     p     q     r     s     t
ciphertext: 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100

 plaintext:   u     v     w     x     y     z
ciphertext: 10101 10110 10111 11000 11001 11010

The first use of a binary numeral system in cryptography, however, was well before the advent of digital computers. Sir Francis Bacon alluded to this cipher in 1605 in his work Of the Proficience and Advancement of Learning, Divine and Humane and published it in 1623 in the enlarged Latin version De Augmentis Scientarum. In this system not only the meaning but the very existence of the message is hidden in an innocuous “covertext.” We will give a modern English example.

Suppose we want to encrypt the word “not” into the covertext “I wrote Shakespeare.” First convert the plaintext into binary numerals:

   plaintext:   n      o     t
  ciphertext: 01110  01111 10100

Then stick the digits together into a string:

    011100111110100

Now we need what Bacon called a “biformed alphabet,” that is, one where each letter can have a “0-form” and a “1-form.”We will use roman letters for our 0-form and italic for our 1-form. Then for each letter of the covertext, if the corresponding digit in the ciphertext is 0, use the 0-form, and if the digit is 1 use the 1-form:

    0 11100 111110100xx
    I wrote Shakespeare.

Any leftover letters can be ignored, and we leave in spaces and punctuation to make the covertext look more realistic. Of course, it still looks odd with two different typefaces—Bacon’s examples were more subtle, although it’s a tricky business to get two alphabets that are similar enough to fool the casual observer but distinct enough to allow for accurate decryption.

Ciphers with binary numerals were reinvented many years later for use with the telegraph and then the printing telegraph, or teletypewriter. The first of these were technically not cryptographic since they were intended for convenience rather than secrecy. We could call them nonsecret ciphers, although for historical reasons they are usually called codes or sometimes encodings. The most well-known nonsecret encoding is probably the Morse code used for telegraphs and early radio, although Morse code does not use binary numerals. In 1833, Gauss, whom we met in Chapter 1, and the physicist Wilhelm Weber invented probably the first telegraph code, using essentially the same system of 5 binary digits as Bacon. Jean-Maurice-Émile Baudot used the same idea for his Baudot code when he invented his teletypewriter system in 1874. And the Baudot code is the one that Gilbert S. Vernam had in front of him in 1917 when his team at AT&T was asked to investigate the security of teletypewriter communications.

Vernam realized that he could take the string of binary digits produced by the Baudot code and encrypt it by combining each digit from the plaintext with a corresponding digit from the key according to the rules:

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

For example, the digits 10010, which ordinarily represent 18, and the digits 01110, which ordinarily represent 14, would be combined to get:

1 0 0 1 0
0 1 1 1 0


1 1 1 0 0

This gives 11100, which ordinarily represents 28—not the usual sum of 18 and 14.

Some of the systems that AT&T was using were equipped to automatically send messages using a paper tape, which could be punched with holes in 5 columns—a hole indicated a 1 in the Baudot code and no hole indicated a 0. Vernam configured the teletypewriter to combine each digit represented by the plaintext tape to the corresponding digit from a second tape punched with key characters. The resulting ciphertext is sent over the telegraph lines as usual.

At the other end, Bob feeds an identical copy of the tape through the same circuitry. Notice that doing the same operation twice gives you back the original value for each rule:

(0 ⊕ 0) ⊕ 0 = 0 ⊕ 0 = 0
(0 ⊕ 1) ⊕ 1 = 1 ⊕ 1 = 0
(1 ⊕ 0) ⊕ 0 = 1 ⊕ 0 = 1
(1 ⊕ 1) ⊕ 1 = 0 ⊕ 1 = 1

Thus the same operation at Bob’s end cancels out the key, and the teletypewriter can print the plaintext. Vernam’s invention and its further developments became extremely important in modern ciphers such as the ones in Sections 4.3 and 5.2 of The Mathematics of Secrets.

But let’s finish this post by going back to Bacon’s cipher.  I’ve changed it up a little — the covertext below is made up of two different kinds of words, not two different kinds of letters.  Can you figure out the two different kinds and decipher the hidden message?

It’s very important always to understand that students and examiners of cryptography are often confused in considering our Francis Bacon and another Bacon: esteemed Roger. It is easy to address even issues as evidently confusing as one of this nature. It becomes clear when you observe they lived different eras.

Answer to Cipher Challenge #2: Subliminal Channels

Given the hints, a good first assumption is that the ciphertext numbers have to be combined in such a way as to get rid of all of the fractions and give a whole number between 1 and 52.  If you look carefully, you’ll see that 1/5 is always paired with 3/5, 2/5 with 1/5, 3/5 with 4/5, and 4/5 with 2/5.  In each case, twice the first one plus the second one gives you a whole number:

2 × (1/5) + 3/5 = 5/5 = 1
2 × (2/5) + 1/5 = 5/5 = 1
2 × (3/5) + 4/5 = 10/5 = 2
2 × (4/5) + 2/5 = 10/5 = 2

Also, twice the second one minus the first one gives you a whole number:

2 × (3/5) – 1/5 = 5/5 = 1
2 × (1/5) – 2/5 = 0/5 = 0
2 × (4/5) – 3/5 = 5/5 = 1
2 × (2/5) – 4/5 = 0/5 = 0

Applying

to the ciphertext gives the first plaintext:

39 31 45 45 27 33 31 40 47 39 28 31 44 41
 m  e  s  s  a  g  e  n  u  m  b  e  r  o
40 31 35 45 46 34 31 39 31 30 35 47 39
 n  e  i  s  t  h  e  m  e  d  i  u  m

And applying

to the ciphertext gives the second plaintext:

20  8  5 19  5  3 15 14  4 16 12  1  9 14 
 t  h  e  s  e  c  o  n  d  p  l  a  i  n
20  5 24 20  9 19  1 20 12  1 18  7  5
 t  e  x  t  i  s  a  t  l  a  r  g  e

To deduce the encryption process, we have to solve our two equations for C1 and C2.  Subtracting the second equation from twice the first gives:


so

Adding the first equation to twice the second gives:


so

Joshua Holden is professor of mathematics at the Rose-Hulman Institute of Technology.

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.