by Simon Singh
PRAISE FOR SIMON SINGH AND The Code Book
“Singh spins tales of cryptic intrigue in every chapter.”
—The Wall Street Journal
“Brings together … the geniuses who have secured communications, saved lives, and influenced the fate of nations. A pleasure to read.”
—Chicago Tribune
“Singh pursues the fascinating story [of codes] through the centuries, always providing plenty of detailed examples of ciphers for those who appreciate the intricacies of the medium.”
—Los Angeles Times
“Especially effective at putting the reader in the codebreaker’s shoes, facing each new, apparently unbreakable code.… Singh does a fine job.”
—The New York Times Book Review
“Entertaining.… Singh has a flair for narrative.”
—San Francisco Chronicle
“Singh is an interesting mix of scientist and storyteller, and this subject is the perfect mix of true fact and tall tales.”
—The San Diego Union-Tribune
“Where would we Information Age ignoramuses be without smart guys like Stephen Jay Gould, the late Carl Sagan, or Simon Singh? They are the troubadours of our time, making complicated subjects understandable and entertaining.”
—The Plain Dealer
“In this entertaining survey, the evolution of cryptography is driven by the ongoing struggle between code-makers and codebreakers.”
—The New Yorker
“[Singh] is well-equipped to describe all the arcane mathematics in layman’s language.”
—Forbes
“Wonderful stories.… Close reading is rewarded with the flash of logical insight that the codebreakers must enjoy.”
—Hartford Advocate
“An illuminating and entertaining account.… From the first page, Singh shows his knack both for explaining complex areas of science and telling rip-roaring stories.”
—New York Law Journal
“My only regret is that this great book has come far too late. If only someone had given it to me when I was 10, my secret plans for world playground domination might never have been foiled.”
—James Flint, The Observer (London)
“Full of fascinating case histories covering the development and practical use of cryptography.”
—Mail on Sunday (London)
“Singh has created an authoritative and engrossing read which both explains and humanizes the subject.… This intelligent, exciting book takes its drive from a simple premise-that nothing is as exciting as a secret.”
—Scotland on Sunday
SIMON SINGH
The Code Book
Simon Singh received his Ph.D. in physics from Cambridge University. A former BBC producer, he directed an award-winning documentary film on Fermat’s Last Theorem that aired on PBS’s Nova series and wrote the bestselling book, Fermat’s Enigma. He lives in London, England.
Also by Simon Singh
Fermat’s Enigma
FIRST ANCHOR BOOKS EDITION, SEPTEMBER 2000
Copyright © 1999 by Simon Singh
All rights reserved under International and Pan-American Copyright Conventions. Published in the United States by Anchor Books, a division of Random House, Inc., New York, and simultaneously in Canada by Random House of Canada Limited, Toronto. Originally published in hardcover in the United States by Doubleday, a division of Random House, Inc., New York, and in the United Kingdom by the Fourth Estate, London, in 1999.
Anchor Books and colophon are registered trademarks of Random House, Inc.
The Library of Congress has cataloged the Doubleday edition as follows:
Singh, Simon.
The code book : the evolution of secrecy from Mary Queen of Scots to quantum cryptography / Simon Singh. –1st ed.
p. cm.
1. Cryptography–History. 2. Data encryption (Computer science)–History. I. Title.
Z103.S56 1999
652′.8′09–dc21 99-35261
eISBN: 978-0-307-78784-2
Author photo © Nigel Spalding
www.anchorbooks.com
v3.1_r2
For my mother and father,
Sawaran Kaur and Mehnga Singh
The urge to discover secrets is deeply ingrained in human nature; even the least curious mind is roused by the promise of sharing knowledge withheld from others. Some are fortunate enough to find a job which consists in the solution of mysteries, but most of us are driven to sublimate this urge by the solving of artificial puzzles devised for our entertainment. Detective stories or crossword puzzles cater for the majority; the solution of secret codes may be the pursuit of a few.
John Chadwick
The Decipherment of Linear B
Contents
Cover
About the Author
Other Books by This Author
Title Page
Copyright
Dedication
Epigraph
Introduction
1 The Cipher of Mary Queen of Scots
2 Le Chiffre Indéchiffrable
3 The Mechanization of Secrecy
4 Cracking the Enigma
5 The Language Barrier
6 Alice and Bob Go Public
7 Pretty Good Privacy
8 A Quantum Leap into the Future
The Cipher Challenge
Appendices
Glossary
Acknowledgments
Further Reading
Picture Credits
Introduction
For thousands of years, kings, queens and generals have relied on efficient communication in order to govern their countries and command their armies. At the same time, they have all been aware of the consequences of their messages falling into the wrong hands, revealing precious secrets to rival nations and betraying vital information to opposing forces. It was the threat of enemy interception that motivated the development of codes and ciphers: techniques for disguising a message so that only the intended recipient can read it.
The desire for secrecy has meant that nations have operated codemaking departments, responsible for ensuring the security of communications by inventing and implementing the best possible codes. At the same time, enemy codebreakers have attempted to break these codes, and steal secrets. Codebreakers are linguistic alchemists, a mystical tribe attempting to conjure sensible words out of meaningless symbols. The history of codes and ciphers is the story of the centuries-old battle between codemakers and codebreakers, an intellectual arms race that has had a dramatic impact on the course of history.
In writing The Code Book, I have had two main objectives. The first is to chart the evolution of codes. Evolution is a wholly appropriate term, because the development of codes can be viewed as an evolutionary struggle. A code is constantly under attack from codebreakers. When the codebreakers have developed a new weapon that reveals a code’s weakness, then the code is no longer useful. It either becomes extinct or it evolves into a new, stronger code. In turn, this new code thrives only until the codebreakers identify its weakness, and so on. This is analogous to the situation facing, for example, a strain of infectious bacteria. The bacteria live, thrive and survive until doctors discover an antibiotic that exposes a weakness in the bacteria and kills them. The bacteria are forced to evolve and outwit the antibiotic, and, if successful, they will thrive once again and reestablish themselves. The bacteria are continually forced to evolve in order to survive the onslaught of new antibiotics.
The ongoing battle between codem
akers and codebreakers has inspired a whole series of remarkable scientific breakthroughs. The codemakers have continually striven to construct ever-stronger codes for defending communications, while codebreakers have continually invented more powerful methods for attacking them. In their efforts to destroy and preserve secrecy, both sides have drawn upon a diverse range of disciplines and technologies, from mathematics to linguistics, from information theory to quantum theory. In return, codemakers and codebreakers have enriched these subjects, and their work has accelerated technological development, most notably in the case of the modern computer.
History is punctuated with codes. They have decided the outcomes of battles and led to the deaths of kings and queens. I have therefore been able to call upon stories of political intrigue and tales of life and death to illustrate the key turning points in the evolutionary development of codes. The history of codes is so inordinately rich that I have been forced to leave out many fascinating stories, which in turn means that my account is not definitive. If you would like to find out more about your favorite tale or your favorite codebreaker then I would refer you to the list of further reading, which should help those readers who would like to study the subject in more detail.
Having discussed the evolution of codes and their impact on history, the book’s second objective is to demonstrate how the subject is more relevant today than ever before. As information becomes an increasingly valuable commodity, and as the communications revolution changes society, so the process of encoding messages, known as encryption, will play an increasing role in everyday life. Nowadays our phone calls bounce off satellites and our e-mails pass through various computers, and both forms of communication can be intercepted with ease, so jeopardizing our privacy. Similarly, as more and more business is conducted over the Internet, safeguards must be put in place to protect companies and their clients. Encryption is the only way to protect our privacy and guarantee the success of the digital marketplace. The art of secret communication, otherwise known as cryptography, will provide the locks and keys of the Information Age.
However, the public’s growing demand for cryptography conflicts with the needs of law enforcement and national security. For decades, the police and the intelligence services have used wire-taps to gather evidence against terrorists and organized crime syndicates, but the recent development of ultra-strong codes threatens to undermine the value of wire-taps. As we enter the twenty-first century, civil libertarians are pressing for the widespread use of cryptography in order to protect the privacy of the individual. Arguing alongside them are businesses, who require strong cryptography in order to guarantee the security of transactions within the fast-growing world of Internet commerce. At the same time, the forces of law and order are lobbying governments to restrict the use of cryptography. The question is, which do we value more—our privacy or an effective police force? Or is there a compromise?
Although cryptography is now having a major impact on civilian activities, it should be noted that military cryptography remains an important subject. It has been said that the First World War was the chemists’ war, because mustard gas and chlorine were employed for the first time, and that the Second World War was the physicists’ war, because the atom bomb was detonated. Similarly, it has been argued that the Third World War would be the mathematicians’ war, because mathematicians will have control over the next great weapon of war—information. Mathematicians have been responsible for developing the codes that are currently used to protect military information. Not surprisingly, mathematicians are also at the forefront of the battle to break these codes.
While describing the evolution of codes and their impact on history, I have allowed myself a minor detour. Chapter 5 describes the decipherment of various ancient scripts, including Linear B and Egyptian hieroglyphics. Technically, cryptography concerns communications that are deliberately designed to keep secrets from an enemy, whereas the writings of ancient civilizations were not intended to be indecipherable: it is merely that we have lost the ability to interpret them. However, the skills required to uncover the meaning of archaeological texts are closely related to the art of codebreaking. Ever since reading The Decipherment of Linear B, John Chadwick’s description of how an ancient Mediterranean text was unraveled, I have been struck by the astounding intellectual achievements of those men and women who have been able to decipher the scripts of our ancestors, thereby allowing us to read about their civilizations, religions and everyday lives.
Turning to the purists, I should apologize for the title of this book. The Code Book is about more than just codes. The word “code” refers to a very particular type of secret communication, one that has declined in use over the centuries. In a code, a word or phrase is replaced with a word, number or symbol. For example, secret agents have codenames, words that are used instead of their real names in order to mask their identities. Similarly, the phrase Attack at dawn could be replaced by the codeword Jupiter, and this word could be sent to a commander in the battlefield as a way of baffling the enemy. If headquarters and the commander have previously agreed on the code, then the meaning of Jupiter will be clear to the intended recipient, but it will mean nothing to an enemy who intercepts it. The alternative to a code is a cipher, a technique that acts at a more fundamental level, by replacing letters rather than whole words. For example, each letter in a phrase could be replaced by the next letter in the alphabet, so that A is replaced by B, B by C, and so on. Attack at dawn thus becomes Buubdl bu ebxo. Ciphers play an integral role in cryptography, and so this book should really have been called The Code and Cipher Book. I have, however, forsaken accuracy for snappiness.
As the need arises, I have defined the various technical terms used within cryptography. Although I have generally adhered to these definitions, there will be occasions when I use a term that is perhaps not technically accurate, but which I feel is more familiar to the non-specialist. For example, when describing a person attempting to break a cipher, I have often used codebreaker rather than the more accurate cipherbreaker. I have done this only when the meaning of the word is obvious from the context. There is a glossary of terms at the end of the book. More often than not, though, crypto-jargon is quite transparent: for example, plaintext is the message before encryption, and ciphertext is the message after encryption.
Before concluding this introduction, I must mention a problem that faces any author who tackles the subject of cryptography: the science of secrecy is largely a secret science. Many of the heroes in this book never gained recognition for their work during their lifetimes because their contribution could not be publicly acknowledged while their invention was still of diplomatic or military value. While researching this book, I was able to talk to experts at Britain’s Government Communications Headquarters (GCHQ), who revealed details of extraordinary research done in the 1970s which has only just been declassified. As a result of this declassification, three of the world’s greatest cryptographers can now receive the credit they deserve. However, this recent revelation has merely served to remind me that there is a great deal more going on, of which neither I nor any other science writer is aware. Organizations such as GCHQ and America’s National Security Agency continue to conduct classified research into cryptography, which means that their breakthroughs remain secret and the individuals who make them remain anonymous.
Despite the problems of government secrecy and classified research, I have spent the final chapter of this book speculating about the future of codes and ciphers. Ultimately, this chapter is an attempt to see if we can predict who will win the evolutionary struggle between codemaker and codebreaker. Will codemakers ever design a truly unbreakable code and succeed in their quest for absolute secrecy? Or will codebreakers build a machine that can decipher any message? Bearing in mind that some of the greatest minds work in classified laboratories, and that they receive the bulk of research funds, it is clear that some of the statements in my final chapter may be inaccurate. For example, I state that qu
antum computers—machines potentially capable of breaking all today’s ciphers—are at a very primitive stage, but it is possible that somebody has already built one. The only people who are in a position to point out my errors are also those who are not at liberty to reveal them.
1 The Cipher of Mary Queen of Scots
On the morning of Saturday, October 15, 1586, Queen Mary entered the crowded courtroom at Fotheringhay Castle. Years of imprisonment and the onset of rheumatism had taken their toll, yet she remained dignified, composed and indisputably regal. Assisted by her physician, she made her way past the judges, officials and spectators, and approached the throne that stood halfway along the long, narrow chamber. Mary had assumed that the throne was a gesture of respect toward her, but she was mistaken. The throne symbolized the absent Queen Elizabeth, Mary’s enemy and prosecutor. Mary was gently guided away from the throne and toward the opposite side of the room, to the defendant’s seat, a crimson velvet chair.
Mary Queen of Scots was on trial for treason. She had been accused of plotting to assassinate Queen Elizabeth in order to take the English crown for herself. Sir Francis Walsingham, Elizabeth’s Principal Secretary, had already arrested the other conspirators, extracted confessions, and executed them. Now he planned to prove that Mary was at the heart of the plot, and was therefore equally culpable and equally deserving of death.
Walsingham knew that before he could have Mary executed, he would have to convince Queen Elizabeth of her guilt. Although Elizabeth despised Mary, she had several reasons for being reluctant to see her put to death. First, Mary was a Scottish queen, and many questioned whether an English court had the authority to execute a foreign head of state. Second, executing Mary might establish an awkward precedent—if the state is allowed to kill one queen, then perhaps rebels might have fewer reservations about killing another, namely Elizabeth. Third, Elizabeth and Mary were cousins, and their blood tie made Elizabeth all the more squeamish about ordering her execution. In short, Elizabeth would sanction Mary’s execution only if Walsingham could prove beyond any hint of doubt that she had been part of the assassination plot.
