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:


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


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:


Adding the first equation to twice the second gives:


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


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:


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

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.

Cipher challenge #1 from Joshua Holden: Merkle’s Puzzles

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. Presenting the first, on Merkle’s puzzles. 

For over two thousand years, everyone assumed that before Alice and Bob start sending secret messages, they’d need to get together somewhere where an eavesdropper couldn’t overhear them in order to agree on the secret key they would use. In the fall of 1974, Ralph Merkle was an undergraduate at the University of California, Berkeley, and taking a class in computer security. He began wondering if there was a way around the assumption that everyone had always made. Was it possible for Alice to send Bob a message without having them agree on a key beforehand? Systems that do this are now called public-key cryptography, and they are a key ingredient in Internet commerce. Maybe Alice and Bob could agree on a key through some process that the eavesdropper couldn’t understand, even if she could overhear it.

Merkle’s idea, which is now commonly known as Merkle’s puzzles, was slow to be accepted and went through several revisions. Here is the version that was finally published. Alice starts by creating a large number of encrypted messages (the puzzles) and sends them to Bob.

The beginning of Merkle’s puzzles.

Merkle suggested that the encryption should be chosen so that breaking each puzzle by brute force is “tedious, but quite possible.” For our very small example, we will just use a cipher which shifts each letter in the message by a specified number of letters. Here are ten puzzles:


Alice explains to Bob that each puzzle consists of three sets of numbers. The first number is an ID number to identify the puzzle. The second set of numbers is a secret key from a more secure cipher which Alice and Bob could actually use to communicate. The last number is the same for all puzzles and is a check so that Bob can make sure he has solved the puzzle correctly. Finally, the puzzles are padded with random letters so that they are all the same length, and each puzzle is encrypted by shifting a different number of letters.

Bob picks one of the puzzles at random and solves it by a brute force search. He then sends Alice the ID number encrypted in the puzzle.

Bob solves the puzzle.

For example, if he picked the puzzle on the fifth line above, he might try shifting the letters:

zcktz etotk zkktz cktze lobky kbktl uaxyk bktzk ktgoz vabln
adlua fupul allua dluaf mpclz lclum vbyzl clual luhpa wbcmo
bemvb gvqvm bmmvb emvbg nqdma mdmvn wczam dmvbm mviqb xcdnp

qtbkq vkfkb qbbkq tbkqv cfsbp bsbkc lropb sbkqb bkxfq mrsce
ruclr wlglc rcclr uclrw dgtcq ctcld mspqc tclrc clygr nstdf
svdms xmhmd sddms vdmsx ehudr dudme ntqrd udmsd dmzhs otueg
twent ynine teent wenty fives evenf ourse vente enait puvfh

Now he knows the ID number is “twenty” and the secret key is 19, 25, 7, 4. He sends Alice “twenty”.

Alice has a list of the decrypted puzzles, sorted by ID number:

ID secret key check
zero nineteen ten seven twentyfive seventeen
one one six twenty fifteen seventeen
two nine five seventeen twelve seventeen
three five three ten nine seventeen
seventeen twenty seventeen nineteen sixteen seventeen
twenty nineteen twentyfive seven four seventeen
twentyfour ten one one seven seventeen

So she can also look up the secret key and find that it is 19, 25, 7, 4. Now Alice and Bob both know a secret key to a secure cipher, and they can start sending encrypted messages. (For examples of ciphers they might use, see Sections 1.6, 4.4, and 4.5 of The Mathematics of Secrets.)

Alice and Bob both have the secret key.

Can Eve the eavesdropper figure out the secret key? Let’s see what she has overheard. She has the encryptions of all of the puzzles, and the check number. She doesn’t know which puzzle Bob picked, but she does know that the ID number was “twenty”. And she doesn’t have Alice’s list of decrypted puzzles. It looks like she has to solve all of the puzzles before she can figure out which one Bob picked and get the secret key. This of course is possible, but will take her a lot longer than the procedure took Alice or Bob.

Eve can’t keep up.

Merkle’s puzzles were always a proof of concept — even Merkle knew that they wouldn’t work in practice. Alice and Bob’s advantage over Eve just isn’t large enough. Nevertheless, they had a direct impact on the development of public-key systems that are still very much in use on the Internet, such as the ones in Chapters 7 and 8 of The Mathematics of Secrets.

Actually, the version of Merkle’s puzzles that I’ve given here has a hole in it. The shift cipher has a weakness that lets Eve use Bob’s ID number to figure out which puzzle he solved without solving them herself. Can you use it to find the secret key which goes with ID number “ten”?

Solving last week’s L.A. Math challenge

LA MathWe’re back with the conclusion to last week’s LA Math challenge, The Case of the Vanishing Greenbacks, (taken from chapter 2 of the book). After the conclusion of the story, we’ll talk a little more with the author, Jim Stein. Don’t forget to check out the fantastic trailer for LA Math here.

Forty‑eight hours later I was bleary‑eyed from lack of sleep. I had made no discernible progress. As far as I could tell, both Stevens and Blaisdell were completely on the up‑and‑up.   Either I was losing my touch, or one (or both) of them were wasting their talents, doctoring books for penny‑ante amounts.   Then I remembered the envelope Pete had sealed. Maybe he’d actually seen something that I hadn’t.

I went over to the main house, to find Pete hunkered down happily watching a baseball game. I waited for a commercial break, and then managed to get his attention.

“I’m ready to take a look in the envelope, Pete.”

“Have you figured out who the guilty party is?”

“Frankly, no. To be honest, it’s got me stumped.” I moved to the mantel and unsealed the envelope. The writing was on the other side of the piece of paper. I turned it over. The name Pete had written on it was “Garrett Ryan and the City Council”!

I nearly dropped the piece of paper. Whatever I had been expecting, it certainly wasn’t this. “What in heaven’s name makes you think Ryan and the City Council embezzled the money, Pete?”

“I didn’t say I thought they did. I just think they’re responsible for the missing funds.”

I shook my head. “I don’t get it. How can they be responsible for the missing funds if they didn’t embezzle them?”

“They’re probably just guilty of innumeracy. It’s pretty common.”

“I give up. What’s innumeracy?”

“Innumeracy is the arithmetical equivalent of illiteracy. In this instance, it consists of failing to realize how percentages behave.” A pitching change was taking place, so Pete turned back to me. “An increase in 20% of the tax base will not compensate for a reduction of 20% in each individual’s taxes.   Percentages involve multiplication and division, not addition and subtraction. A gain of 20 dollars will compensate for a loss of 20 dollars, but that’s because you’re dealing with adding and subtracting. It’s not the same with percentages, because the base upon which you figure the percentages varies from calculation to calculation.”

“You may be right, Pete, but how can we tell?”

Pete grabbed a calculator. “Didn’t you say that each faction was out $198,000?”

I checked my figures. “Yeah, that’s the amount.”

Pete punched a few numbers into the calculator. “Call Ryan and see if there were 99,000 taxpayers in the last census. If there were, I’ll show you where the money went.”

I got on the phone to Ryan the next morning. He confirmed that the tax base in the previous census was indeed 99,000. I told Pete that it looked like he had been right, but I wanted to see the numbers to prove it.

Pete got out a piece of paper. “I think you can see where the money went if you simply do a little multiplication. The taxes collected in the previous census were $100 for each of 99,000 individuals, or $9,900,000. An increase of 20% in the population results in 118,800 individuals. If each pays $80 (that’s the 20% reduction from $100), the total taxes collected will be $9,504,000, or $396,000 less than was collected after the previous census. Half of $396,000 is $198,000.”

I was convinced. “There are going to be some awfully red faces down in Linda Vista. I’d like to see the press conference when they finally announce it.” I went back to the guesthouse, called Allen, and filled him in. He was delighted, and said that the check would be in the mail.   As I’ve said before, when Allen says it, he means it. Another advantage of having Allen make the arrangements is that I didn’t have to worry about collecting the fee, which is something I’ve never been very good at.

I wondered exactly how they were going to break the news to the citizens of Linda Vista that they had to pony up another $396,000, but as it was only about $3.34 per taxpayer I didn’t think they’d have too much trouble. Thanks to a combination of Ryan’s frugality and population increase, the tax assessment would still be lower than it was after the previous census, and how many government agencies do you know that actually reduce taxes? I quickly calculated that if they assessed everyone $3.42 they could not only cover the shortage, but Allen’s fee as well. I considered suggesting it to Ryan, but then I thought that Ryan probably wasn’t real interested in hearing from someone who had made him look like a bungler.

My conscience was bothering me, and I don’t like that. I thought about it, and finally came up with a compromise I found acceptable. I went back to the main house.

Pete was watching another baseball game. The Dodgers fouled up an attempted squeeze into an inning‑ending double play. Pete groaned. “It could be a long season,” he sighed.

“It’s early in the year.” I handed him a piece of paper. “Maybe this will console you.”

“What’s this?” He was examining my check for $1,750. “Your rent’s paid up.”

“It’s not for the rent, Pete. It’s your share of my fee.”

“Fee? What fee?”

“That embezzling case in Orange County. It was worth $3,500 to me to come up with the correct answer. I feel you’re entitled to half of it. You crunched the numbers, but I had the contacts and did the legwork.”

Pete looked at the check. “It seems like a lot of money for very little work. Tell you what. I’ll take $250, and credit the rest towards your rent.”

A landlord with a conscience! Maybe I should notify the Guinness Book of Records. “Seems more than fair to me.”

Pete tucked the check in the pocket of his shirt. “Tell me, Freddy, is it always this easy, doing investigations?”

I summoned up a wry laugh. “You’ve got to be kidding. So far, I’ve asked you two questions that just turned out to be right down your alley. I’ve sometimes spent months on a case, and come up dry. That can make the bottom line look pretty sick. What’s it like in your line of work?”

“I don’t really have a line of work. I have this house and some money in the bank. I can rent out the guesthouse and make enough to live on. People know I’m pretty good at certain problems, and sometimes they hire me. If it looks like it might be interesting, I’ll work on it.” He paused. “Of course, if they offer me a ridiculous amount of money, I’ll work on it even if it’s not interesting. Hey, we’re in a recession.”

“I’ll keep that in mind.”   I turned to leave the room. Pete’s voice stopped me.

“Haven’t you forgotten something?”

I turned around. “I give up. What?”

“We had a bet. You owe me five bucks.”

I fished a five out of my wallet and handed it over. He nodded with satisfaction as he stuffed it in the same pocket as the check, and then turned his attention back to the game.

What made you include this particular idea in the book?

JS: The story features one of the most common misunderstandings about percentages.  There are innumerable mistakes made because people assume that percentages work the same way as regular quantities.  But they don’t — if a store lowers the cost of an item by 30% and then by another 20%, the cost of the item hasn’t been lowered by 50% — although many people make the mistake of assuming that it has.  I’m hoping that the story is sufficiently memorable that if a reader is confronted by a 30% discount followed by a 20% discount, they’ll think “Wasn’t there something like that in The Case of the Vanishing Greenbacks?

There are 14 stories in the book, and each features a mathematical point, injected into the story in a similar fashion as the one above.  I think the stories are fun to read, and if someone reads the book and remembers just a few of the points, well, I’ve done a whole lot better than when I was teaching liberal arts math the way it is usually done.

James D. Stein is emeritus professor in the Department of Mathematics at California State University, Long Beach. His books include LA Math, Cosmic Numbers (Basic) and How Math Explains the World (Smithsonian).