The Code Book The Secrets Behind Codebreaking (Simon Singh) (Z Library)

📄 File Format: PDF

💾 File Size: 1.8 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

,VMG;PORTIYPOERIUTE JLZXKDJFOERYTHFKDSJ RGK.EAJDHF,XCMBNGHL 82983YIJHSAGFMNDXBG 254HOIUYERHALKJHSAK JDF.GTHEXKJFHDSVNLO XLFKJCODEQSKJFH,MN, ;LDLKBOOKCLVNSEL;RI FLZKXDNFMLZXX.C,VNZ FP’SEOJRLGIZDS7ER50 =WPH[GFOKBOLHJZXGFY 1EDFUJ4GHEBGKAJSNC. PRTOYIEP5ROTKGH;SDL YRHIKSUHFIUEWYTOISE SRTIY458WT028YHTGLD R9TOY[PRTLKG;’OSEI[ TLKDJFG.DF,MGPFGSOU UWP4KJT,DF,KSEJHR’O This book has been optimized for viewing at a monitor setting of 1024 x 768 pixels.

📄 Page 3

Also by Simon Singh Fermat’s Enigma

📄 Page 4

HOW TO MAKE IT, BREAK IT, HACK IT, CRACK IT SIMON SINGH DELACORTE PRESS

📄 Page 5

Published by Delacorte Press an imprint of Random House Children’s Books a division of Random House, Inc. 1540 Broadway New York, New York 10036 Copyright © 2001 by Simon Singh All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without the written permission of the Publisher, except where permitted by law. The trademark Delacorte Press® is registered in the U.S. Patent and Trademark Office and in other countries. Visit us on the Web! www.randomhouse.com/teens Educators and librarians, for a variety of teaching tools, visit us at www.randomhouse.com/teachers Library of Congress Cataloging-in-Publication Data Singh, Simon. The code book : how to make it, break it, hack it, crack it / Simon Singh. p. cm. Includes bibliographical references and index. 1. Coding theory. 2. Cryptography. I. Title. TK5102.92.S56 2002 652'.8—dc21 2001042131 eISBN 0-375-89012-2 Book design by Ericka O’Rourke March 2002 v1.0

📄 Page 6

To the Teachers and Mortals who took the time to inspire me XICYIQKMHR, VOIR RFH LKRQT

📄 Page 7

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 fortu- nate 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 entertain- ment. 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

📄 Page 8

CONTENTS Introduction 1 1 The Cipher of Mary Queen of Scots 5 The birth of cryptography, the substitution cipher and the invention of codebreaking by frequency analysis 2 The Anonymous Codebreaker 51 The Vigenère cipher, why cryptographers seldom get credit for their breakthroughs and a tale of buried treasure 3 The Mechanization of Secrecy 95 The Zimmermann telegram, the Enigma machine and how cryptography changed the courses of World Wars I and II 4 The Language Barrier 152 The impenetrability of unknown languages, the Navajo code talkers of World War II and the decipherment of Egyptian hieroglyphs 5 Alice and Bob Go Public 180 Modern cryptography, the solution to the so-called key-distribution problem and the secret history of nonsecret encryption 6 Pretty Good Privacy 221 The politics of privacy, the future of cryptography and the quest for an uncrackable code The Codebreaker’s Challenge 243 Appendices 245 Acknowledgments 253 Further Reading 255 Picture Credits 260 Index 261

📄 Page 9

(This page has no text content)

📄 Page 10

1 INTRODUCTION For centuries, kings, queens and generals have relied on effi- cient 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 be- traying 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, which were responsible for ensuring the security of communications by inventing and implement- ing the best possible codes. At the same time, enemy code- breakers have attempted to break these codes and steal secrets. Codebreakers are linguistic alchemists, a mystical tribe at- tempting to conjure sensible words out of meaningless sym- bols. 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

📄 Page 11

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 similar 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. 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 in- trigue 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 ac- count is not definitive. If you would like to find out more about your favorite tale or your favorite codebreaker, then I would re- fer you to the list of further reading. 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 com- munications revolution changes society, so the process of en- coding 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 INTRODUCTION 2

📄 Page 12

to protect companies and their clients. Encryption is the only way to protect our privacy and guarantee the success of the dig- ital 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 se- curity. For decades, the police and the intelligence services have used wiretaps to gather evidence against terrorists and organized crime syndicates, but the recent development of ul- trastrong codes threatens to undermine the value of wiretaps. The forces of law and order are lobbying governments to re- strict the use of cryptography, while civil libertarians and busi- nesses are arguing for the widespread use of encryption to protect privacy. Who wins the argument depends on which we value more, our privacy or an effective police force. Or is there a compromise? Before concluding this introduction, I must mention a problem that faces any author who tackles the subject of cryp- tography: 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. This culture of secrecy continues today, and organizations such as the U.S. National Security Agency still conduct classified research into cryptog- raphy. It is clear that there is a great deal more going on of which neither I nor any other science writer is aware. INTRODUCTION 3

📄 Page 13

Figure 1 Mary Queen of Scots.

📄 Page 14

5 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 re- gal. 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 1 The birth of cryptography, the substitution cipher and the invention of codebreaking by frequency analysis

📄 Page 15

planned to prove that Mary was at the heart of the plot, and was therefore equally to blame and equally deserving of death. Walsingham knew that before he could have Mary executed, he would have to convince Queen Elizabeth of her guilt. Al- though Elizabeth despised Mary, she had several reasons for being reluctant to see her put to death. First, Mary was a Scot- tish queen, and many questioned whether an English court had the authority to execute a foreign head of state. Second, exe- cuting 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 Eliza- beth. Third, Elizabeth and Mary were cousins, and their blood tie made Elizabeth all the more squeamish about ordering the 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 re- placing 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 given her blessing to the conspiracy. In fact, Mary had authorized the plot. The challenge for Wal- singham was to demonstrate a clear 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 ac- cused was forbidden counsel and was not permitted to call wit- nesses. Mary was not even allowed secretaries to help her prepare her case. However, her plight was not hopeless, be- cause she had been careful to ensure that all her correspon- dence 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 THE CODE BOOK 6

📄 Page 16

letters, 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 de- pended on the assumption that her cipher had not been broken. Unfortunately for Mary, Walsingham was not merely prin- cipal secretary, but also England’s spymaster. He had inter- cepted 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 incriminat- ing 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 B.C., which he viewed as a confrontation between free- dom 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, 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 The Cipher of Mary Queen of Scots 7

📄 Page 17

all over the empire and neighboring states, with the notable ex- ceptions of Athens and Sparta. Determined to avenge this in- solence, Xerxes began mobilizing 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 be- yond 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 B.C., he was ready to launch a surprise attack. However, the Persian military buildup had been witnessed by Demaratus, a Greek who had been expelled from his home- land 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 in- tercepted 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, writ- ing 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 destina- tion, no one was able to guess the secret, until, as I understand, Cleomenes’ daughter Gorgo, who was the wife of Leonidas, di- vined 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 afterward passed on to the other Greeks. As a result of this warning, the hitherto defenseless 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 hun- dred warships. THE CODE BOOK 8

📄 Page 18

Xerxes had lost the vital element of surprise, and on Septem- ber 23, 480 B.C., 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 realized that within the confines of the bay they might outmaneuver the Persians. As the wind changed direction the Persians found themselves being blown into the bay, forced into an engage- ment 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 Per- sian ships collided and the Greeks launched a full-blooded on- slaught. 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 mes- sage on his scalp, and then waited for the hair to regrow. This was clearly not an urgent message. The messenger, apparently carrying nothing contentious, could travel without being ha- rassed. 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. The Cipher of Mary Queen of Scots 9

📄 Page 19

For example, the ancient Chinese wrote messages on fine silk, which was scrunched into a tiny ball and covered in wax. The messenger would then swallow the ball of wax. Steganography also includes the practice of writing in invisible ink. As far back as the first century A.D., Pliny the Elder explained how the “milk” of the tithymalus plant could be used as an invisible ink. Although the ink is transparent after drying, gentle heating chars it 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 some degree of security, but it suffers from a fundamen- tal 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, shaving people’s heads, and so on, and inevitably there will be occasions when a message is uncovered. Hence, along with the development of steganography, there was the evolution of cryptography (the word is derived from the Greek 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 in- tended recipient. Thus the recipient can reverse the scrambling protocol and make the message comprehensible. The advan- tage of cryptography is that if the enemy intercepts an en- crypted message, the message is unreadable. Without knowing THE CODE BOOK 10

📄 Page 20

the scrambling protocol, the enemy should find it difficult, if not impossible, to re-create the original message from the en- crypted text. 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 num- ber 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 pro- cess is known. For example, consider this short sentence. It contains just thirty-five letters, and yet there are more than 50,000,000,000,000,000,000,000,000,000,000 distinct ar- rangements of them. If one person could check one arrange- ment per second, and if all the people in the world worked night and day, it would still take more than a thousand times the life- time of the universe to check all the arrangements. A random transposition of letters seems to offer a very high level of security, because it would be impractical for an enemy interceptor to unscramble even a short sentence. But there is a drawback. Transposition effectively generates an incredibly dif- ficult anagram, and if the letters are randomly jumbled, with neither rhyme nor reason, then unscrambling the anagram is impossible for the intended recipient, as well as for an enemy interceptor. In order for transposition to be effective, the re- arrangement of letters needs to follow a straightforward system, one that has been previously agreed by sender and re- ceiver but kept secret from the enemy. For example, it is possi- ble to send messages using the “rail fence” transposition, in The Cipher of Mary Queen of Scots 11