Toward the end of August, an international team of computer scientists succeeded in breaking a 155-digit number into its two prime factors. The feat was significant because public-key cryptography -- the system of encryption that ostensibly guards the privacy of most Internet traffic today -- depends on the difficulty of factoring a very large number. True, it took 292 computers seven months to factor that number. But the mere fact that the problem was solvable in a finite period -- as opposed to, say, 43 times the age of the universe -- was enough to show that the current level of security can, and ultimately will, be penetrated.
This latest blow in the struggle between code makers and code breakers comes as a timely epilogue to The Code Book, Simon Singh's fascinating and remarkably accessible history of cryptography. Tracing the development of secret writing from the fifth century B.C. to the present and beyond, Singh recounts a series of theoretical and practical breakthroughs, each followed by a matching counterstroke in an ongoing intellectual tennis match. The "evolution" of his subtitle, in fact, is analogous to the biological arms race that develops over time between predators and their prey, or pathogens and their hosts. Each time a technological advance makes a new level of secrecy in encrypted writing possible, the code makers have the upper hand; but eventually the code breakers locate a flaw in the new system, making secure communications an iffy proposition again.
Singh begins his story with the simple alphabetic cipher, a letter-by-letter encoding that lives on today in the humble cryptogram. (It's amazing to consider that what is now an amusement in the daily newspaper was used as recently as the Renaissance to conceal top-level diplomatic correspondence.) Cryptograms, of course, can be easily broken by "frequency analysis" -- assuming, for instance, that the most common letter in a long English message stands for E. Singh goes on to the Vigenere cipher, hailed in the 19th century as "the indecipherable cipher," which improved on that system by using several different cipher alphabets in rotation, but it, too, ultimately proved fallible. He then proceeds to describe the penetration of the Germans' Enigma code during World War II and, ultimately, with the rise of the computer and electronic communications, the 1970s development of public-key cryptography. He also includes a compelling detour into the great achievements in historical code breaking: the decipherings of the Rosetta Stone and the Linear B inscriptions of the Minoan civilization.
Singh, the British science journalist who wrote the popular Fermat's Enigma, has a gift for explaining the nuts and bolts of even the most intricate cryptographic systems; it is nothing short of astonishing to watch the Enigma cipher crumble before your eyes through a series of logical deductions that a lay reader can easily follow. At the end of the book, in a sort of promotional-gimmick-cum-final-exam, Singh offers a $15,000 prize to the first reader who can crack a series of coded messages -- one in each of the increasingly sophisticated encryption schemes he details in the book. (It's a measure of just how clear his explanations are that the challenge seems well within the realm of possibility.)
Singh goes beyond the technical details of cryptography to profile the people behind the codes; his book is full of enlivening biographical details and deft portraits of some of the quirkier figures in the history of mathematics, computer science, archaeology and diplomacy. He is scrupulous, too, about giving credit not just to the marquee names but to the lesser-known figures in the story of cryptography as well: His account of the Enigma decoding, for instance, recognizes the work of the British intelligence service and the brilliant mathematician Alan Turing, but also explicates the essential foundations laid by an obscure Polish statistician named Marian Rejewski.
The book's lone false note comes at the end, when Singh contemplates the cryptographic advances based on quantum physics that may appear in the 21st century. He seems to take seriously the likelihood that a truly unbreakable cipher is on the horizon -- this after 300 pages detailing the history of just such a fantasy. It's possible, of course, that complete privacy may yet be achievable. But nothing in The Code Book supports the idea.
Publishers Weekly - Publisher's Weekly
In an enthralling tour de force of popular explication, Singh, author of the bestselling Fermat's Enigma, explores the impact of cryptography--the creation and cracking of coded messages--on history and society. Some of his examples are familiar, notably the Allies' decryption of the Nazis' Enigma machine during WWII; less well-known is the crucial role of Queen Elizabeth's code breakers in deciphering Mary, Queen of Scots' incriminating missives to her fellow conspirators plotting to assassinate Elizabeth, which led to Mary's beheading in 1587. Singh celebrates a group of unsung heroes of WWII, the Navajo "code talkers," Native American Marine radio operators who, using a coded version of their native language, played a vital role in defeating the Japanese in the Pacific. He also elucidates the intimate links between codes or ciphers and the development of the telegraph, radio, computers and the Internet. As he ranges from Julius Caesar's secret military writing to coded diplomatic messages in feuding Renaissance Italy city-states, from the decipherment of the Rosetta Stone to the ingenuity of modern security experts battling cyber-criminals and cyber-terrorists, Singh clarifies the techniques and tricks of code makers and code breakers alike. He lightens the sometimes technical load with photos, political cartoons, charts, code grids and reproductions of historic documents. He closes with a fascinating look at cryptanalysts' planned and futuristic tools, including the "one-time pad," a seemingly unbreakable form of encryption. In Singh's expert hands, cryptography decodes as an awe-inspiring and mind-expanding story of scientific breakthrough and high drama. Agent, Patrick Walsh. (Oct.) FYI: The book includes a "Cipher Challenge," offering a $15,000 reward to the first person to crack that code. Copyright 1999 Cahners Business Information.
Library Journal - Library Journal
Singh, Cambridge-educated physicist, has written a provocative study of code, the way in which humans hide the inherent meanings of messages by substituting words and or characters in a text. Author of the popular Fermat's Enigma, he broadly portrays the evolution of cryptography throughout the centuries. In essence, efforts of those wishing for secrecy and others who attempt to break it is a story of intrigue of the highest form. Employing a smooth narrative style, Singh tells of secrecy, fascinating events, and people, starting with Mary Queen of Scots and ending with recent attempts by quantum theorists to construct an unbreakable code. This is the history of technology at its best and serves as an excellent addition to David Kahn's mammoth work on cryptography, The Codebreakers (Scribner, 1996). Highly recommended for all public and academic libraries. [Previewed in Prepub Alert, LJ 5/1/99.]--Dayne Sherman, Southeastern Louisiana Univ., Hammond Copyright 1999 Cahners Business Information.
During the late 19th century, private citizens and businesses began to rely less on the dependable but slow postal system, and more on a new method of transmitting and receiving messages, news and financial data. The breakthrough technology was the telegraph, and almost as soon as people started using it, they began to think of ways to safeguard private communications from prying eyes.
One writer in England's Quarterly Review described the problem in 1853: "The clerks of the English Telegraph Company are sworn to secrecy, but we often write things that would be intolerable to see strangers read before our eyes. This is a grievous fault in the telegraph, and it must be remedied by some means or other."
A simple solution to snooping telegraph operators was to encrypt messages before handing them over to transmit, a practice that became common for individuals and companies alike. A hundred years later, we are in the midst of another telecommunications transformation, and concern over privacy is more intense than ever. As our private e-mail messages and credit card numbers ricochet around the world at dizzying speed, encryption remains the cornerstone of our security.
Of course, as author Simon Singh explains in The Code Book, our methods of encryption have evolved along with our communications technologies. In a sweeping overview, Singh traces the evolution of secret writing from the time of Herodotus to the present day. Along the way, he tells tales of the treasonous, though simply coded communications of Mary, Queen of Scots; Louis XIV's Great Cipher, which went unsolved for two centuries; and Charles Babbage's 1850s deciphering of the supposedly uncrackable polyalphabetic Vigenere Cipher. He also details the World War II-era work of Navajo code-talkers and the cracking of the German Enigma machine, as well as the United States' and England's nearly simultaneous discovery of public-key cryptography in the 1970s.
Author of the 1997 bestseller Fermat's Enigma, Singh casts the relationship between codemaking and codebreaking in evolutionary terms: Like strains of infectious bacteria, ciphers grow stronger because, as the weak are deciphered, necessity demands that more difficult-to-crack codes take their place.
Although Singh fashions a compelling history, as well as a skillful explanation of the analytical underpinnings of cryptographs, the most dramatic moments in the book come in the last three chapters. As the book draws to a close, the author walks readers through such events of the past 20 years as the invention of public-key cryptography and recent experiments to employ quantum mechanics in the quest for the unbreakable code.
The public-key method - the first cryptographic system in history that doesn't require both parties in a transaction to share a secret key - is considered the most important advance in codemaking within the past 2,000 years. Public-key encryption makes possible familiar computer transactions like secure e-mail and e-commerce, without which using a credit card on the Web would be no more secure than leaving a wallet on the bus.
Public-key cryptography also helped revive a debate over encryption that pits citizen privacy against government security. As Singh commented at a recent book reading in San Francisco, "I could send you a message encrypted through free software on the Net, and the combined forces of the GCHQ, the NSA, the CIA and the FBI wouldn't be able to crack that code. And if they did manage to," he added, "I could just re-encrypt with Version 2.0."
Singh understands an essential truth about secrets: You can crack a code if you ask the right questions, but sometimes the answers evolve themselves out of existence. -- Maria De La O
[A] very readable and skillfully told history of crypthography.
London Review of Books
Read an Excerpt
On the morning of Wednesday, 15 October 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 towards her, but she was mistaken. The throne symbolised the absent Queen Elizabeth, Mary's enemy and prosecutor. Mary was gently guided away from the throne and towards 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.
The conspirators were a group of young English Catholic noblemen intent on removing Elizabeth, a Protestant, and replacing her with Mary, a fellow Catholic. It was apparent to the court that Mary was a figurehead for the conspirators, but it was not clear that she had actually given her blessing to the conspiracy. In fact, Mary had authorised the plot. The challenge for Walsingham was to demonstrate a palpable link between Mary and the plotters.
On the morning of her trial, Mary sat alone in the dock, dressed in sorrowful black velvet. In cases of treason, the accused was forbidden counsel and was not permitted to call witnesses. Mary was not even allowed secretaries to help her prepare her case. However, her plight was not hopeless because she had been careful to ensure that all her correspondence with the conspirators had been written in cipher. The cipher turned her words into a meaningless series of symbols, and Mary believed that even if Walsingham had captured the letters, then he could have no idea of the meaning of the words within them. If their contents were a mystery, then the letters could not be used as evidence against her. However, this all depended on the assumption that her cipher had not been broken.
Unfortunately for Mary, Walsingham was not merely Principal Secretary, he was also England's spymaster. He had intercepted Mary's letters to the plotters, and he knew exactly who might be capable of deciphering them. Thomas Phelippes was the nation's foremost expert on breaking codes, and for years he had been deciphering the messages of those who plotted against Queen Elizabeth, thereby providing the evidence needed to condemn them. If he could decipher the incriminating letters between Mary and the conspirators, then her death would be inevitable. On the other hand, if Mary's cipher was strong enough to conceal her secrets, then there was a chance that she might survive. Not for the first time, a life hung on the strength of a cipher.
The Evolution of Secret Writing
Some of the earliest accounts of secret writing date back to Herodotus, 'the father of history' according to the Roman philosopher and statesman Cicero. In The Histories, Herodotus chronicled the conflicts between Greece and Persia in the fifth century bc, which he viewed as a confrontation between freedom and slavery, between the independent Greek states and the oppressive Persians. According to Herodotus, it was the art of secret writing that saved Greece from being conquered by Xerxes, King of Kings, the despotic leader of the Persians.
The long-running feud between Greece and Persia reached a crisis soon after Xerxes began constructing a city at Persepolis, the new capital for his kingdom. Tributes and gifts arrived from all over the empire and neighbouring states, with the notable exceptions of Athens and Sparta. Determined to avenge this insolence, Xerxes began mobilising a force, declaring that 'we shall extend the empire of Persia such that its boundaries will be God's own sky, so the sun will not look down upon any land beyond the boundaries of what is our own'. He spent the next five years secretly assembling the greatest fighting force in history, and then, in 480 bc, he was ready to launch a surprise attack.
However, the Persian military build-up had been witnessed by Demaratus, a Greek who had been expelled from his homeland and who lived in the Persian city of Susa. Despite being exiled he still felt some loyalty to Greece, so he decided to send a message to warn the Spartans of Xerxes' invasion plan. The challenge was how to dispatch the message without it being intercepted by the Persian guards. Herodotus wrote:
As the danger of discovery was great, there was only one way in which he could contrive to get the message through: this was by scraping the wax off a pair of wooden folding tablets, writing on the wood underneath what Xerxes intended to do, and then covering the message over with wax again. In this way the tablets, being apparently blank, would cause no trouble with the guards along the road. When the message reached its destination, no one was able to guess the secret, until, as I understand, Cleomenes' daughter Gorgo, who was the wife of Leonides, divined and told the others that if they scraped the wax off, they would find something written on the wood underneath. This was done; the message was revealed and read, and afterwards passed on to the other Greeks.
As a result of this warning, the hitherto defenceless Greeks began to arm themselves. Profits from the state-owned silver mines, which were usually shared among the citizens, were instead diverted to the navy for the construction of two hundred warships.
Xerxes had lost the vital element of surprise and, on 23 September 480 bc, when the Persian fleet approached the Bay of Salamis near Athens, the Greeks were prepared. Although Xerxes believed he had trapped the Greek navy, the Greeks were deliberately enticing the Persian ships to enter the bay. The Greeks knew that their ships, smaller and fewer in number, would have been destroyed in the open sea, but they realised that within the confines of the bay they might outmanoeuvre the Persians. As the wind changed direction the Persians found themselves being blown into the bay, forced into an engagement on Greek terms. The Persian princess Artemisia became surrounded on three sides and attempted to head back out to sea, only to ram one of her own ships. Panic ensued, more Persian ships collided and the Greeks launched a full-blooded onslaught. Within a day, the formidable forces of Persia had been humbled.
Demaratus' strategy for secret communication relied on simply hiding the message. Herodotus also recounted another incident in which concealment was sufficient to secure the safe passage of a message. He chronicled the story of Histaiaeus, who wanted to encourage Aristagoras of Miletus to revolt against the Persian king. To convey his instructions securely, Histaiaeus shaved the head of his messenger, wrote the message on his scalp, and then waited for the hair to regrow. This was clearly a period of history that tolerated a certain lack of urgency. The messenger, apparently carrying nothing contentious, could travel without being harassed. Upon arriving at his destination he then shaved his head and pointed it at the intended recipient.
Secret communication achieved by hiding the existence of a message is known as steganography, derived from the Greek words steganos, meaning 'covered', and graphein, meaning 'to write'. In the two thousand years since Herodotus, various forms of steganography have been used throughout the world. For example, the ancient Chinese wrote messages on fine silk, which was then scrunched into a tiny ball and covered in wax. The messenger would then swallow the ball of wax. In the fifteenth century, the Italian scientist Giovanni Porta described how to conceal a message within a hard-boiled egg by making an ink from a mixture of one ounce of alum and a pint of vinegar, and then using it to write on the shell. The solution penetrates the porous shell, and leaves a message on the surface of the hardened egg albumen, which can be read only when the shell is removed. Steganography also includes the practice of writing in invisible ink. As far back as the first century ad, Pliny the Elder explained how the 'milk' of the thithymallus plant could be used as an invisible ink. Although transparent after drying, gentle heating chars the ink and turns it brown. Many organic fluids behave in a similar way, because they are rich in carbon and therefore char easily. Indeed, it is not unknown for modern spies who have run out of standard-issue invisible ink to improvise by using their own urine.
The longevity of steganography illustrates that it certainly offers a modicum of security, but it suffers from a fundamental weakness. If the messenger is searched and the message is discovered, then the contents of the secret communication are revealed at once. Interception of the message immediately compromises all security. A thorough guard might routinely search any person crossing a border, scraping any wax tablets, heating blank sheets of paper, shelling boiled eggs, shaving people's heads, and so on, and inevitably there will be occasions when the message is uncovered.
Hence, in parallel with the development of steganography, there was the evolution of cryptography, derived from the Greek word kryptos, meaning 'hidden'. The aim of cryptography is not to hide the existence of a message, but rather to hide its meaning, a process known as encryption. To render a message unintelligible, it is scrambled according to a particular protocol which is agreed beforehand between the sender and the intended recipient. Thus the recipient can reverse the scrambling protocol and make the message comprehensible. The advantage of cryptography is that if the enemy intercepts an encrypted message, then the message is unreadable. Without knowing the scrambling protocol, the enemy should find it difficult, if not impossible, to recreate the original message from the encrypted text.
Although cryptography and steganography are independent, it is possible to both scramble and hide a message to maximise security. For example, the microdot is a form of steganography that became popular during the Second World War. German agents in Latin America would photographically shrink a page of text down to a dot less than 1 millimetre in diameter, and then hide this microdot on top of a full stop in an apparently innocuous letter. The first microdot to be spotted by the FBI was in 1941, following a tip-off that the Americans should look for a tiny gleam from the surface of a letter, indicative of smooth film. Thereafter, the Americans could read the contents of most intercepted microdots, except when the German agents had taken the extra precaution of scrambling their message before reducing it. In such cases of cryptography combined with steganography, the Americans were sometimes able to intercept and block communications, but they were prevented from gaining any new information about German spying activity. Of the two branches of secret communication, cryptography is the more powerful because of this ability to prevent information from falling into enemy hands.
In turn, cryptography itself can be divided into two branches, known as transposition and substitution. In transposition, the letters of the message are simply rearranged, effectively generating an anagram. For very short messages, such as a single word, this method is relatively insecure because there are only a limited number of ways of rearranging a handful of letters. For example, three letters can be arranged in only six different ways, e.g. cow, cwo, ocw, owc, wco, woc. However, as the number of letters gradually increases, the number of possible arrangements rapidly explodes, making it impossible to get back to the original message unless the exact scrambling process is known. For example, consider this short sentence. It contains just 35 letters, and yet there are more than 50,000,000,000,000,000,000,000,000,000,000 distinct arrangements of them. If one person could check one arrangement per second, and if all the people in the world worked night and day, it would still take more than a thousand times the lifetime of the universe to check all the arrangements.