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

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:

VGPVY QUGXG PVYGP VAQPG UKZVG GPUGX GPVGG PBTPU XSNHT JZFEB
GJBAV ARSVI RFRIR AGRRA GJRYI RFRIR AGRRA VTDHC BMABD QMPUP
AFSPO JOFUF FOUFO TFWFO UXFOU ZGJWF TFWFO UFFOI RCXJQ EHHZF
JIZJI ZNDSO RZIOT ADAOZ ZINZQ ZIOZZ IWOPL KDWJH SEXRJ IKAVV
YBJSY DSNSJ YJJSY BJSYD KNAJX JAJSK TZWXJ AJSYJ JSFNY UZAKM
QCTCL RFPCC RUCLR WDMSP RCCLD GDRCC LQCTC LRCCL JLXUW HAYDT
ADLUA FMVBY ALUVU LVULZ LCLUZ LCLUA LLUGE AMPWB PSEQG IKDSV
JXHUU VYLUJ XHUUJ UDDYD UIULU DJUUD AUTRC SGBOD ALQUS ERDWN
RDUDM SDDMS VDMSX RDUDM SDDMM HMDSD DMRHW SDDMR DUDMS DDMAW
BEMTD MBEMV BGBPZ MMMQO PBMMV AMDMV NQDMA MDMVB MMVUR YCEZC

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:

YBJSY DSNSJ YJJSY BJSYD KNAJX JAJSK TZWXJ AJSYJ JSFNY UZAKM
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”?