The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography

by Simon Singh

  Glossary

  ASCII American Standard Code for Information Interchange, a standard for turning alphabetic and other characters into numbers.

  asymmetric key cryptography A form of cryptography in which the key required for encrypting is not the same as the key required for decrypting. Describes public key cryptography systems, such as RSA.

  Caesar-shift substitution cipher Originally a cipher in which each letter in the message is replaced with the letter three places further on in the alphabet. More generally, it is a cipher in which each letter in the message is replaced with the letter x places further on in the alphabet, where x is a number between 1 and 25.

  cipher Any general system for hiding the meaning of a message by replacing each letter in the original message with another letter. The system should have some built-in flexibility, known as the key.

  cipher alphabet The rearrangement of the ordinary (or plain) alphabet, which then determines how each letter in the original message is enciphered. The cipher alphabet can also consist of numbers or any other characters, but in all cases it dictates the replacements for letters in the original message.

  ciphertext The message (or plaintext) after encipherment.

  code A system for hiding the meaning of a message by replacing each word or phrase in the original message with another character or set of characters. The list of replacements is contained in a codebook. (An alternative definition of a code is any form of encryption which has no built-in flexibility, i.e., there is only one key, namely the codebook.)

  codebook A list of replacements for words or phrases in the original message.

  cryptanalysis The science of deducing the plaintext from a ciphertext, without knowledge of the key.

  cryptography The science of encrypting a message, or the science of concealing the meaning of a message. Sometimes the term is used more generally to mean the science of anything connected with ciphers, and is an alternative to the term cryptology.

  cryptology The science of secret writing in all its forms, covering both cryptography and cryptanalysis.

  decipher To turn an enciphered message back into the original message. Formally, the term refers only to the intended receiver who knows the key required to obtain the plaintext, but informally it also refers to the process of cryptanalysis, in which the decipherment is performed by an enemy interceptor.

  decode To turn an encoded message back into the original message.

  decrypt To decipher or to decode.

  DES Data Encryption Standard, developed by IBM and adopted in 1976.

  Diffie-Hellman-Merkle key exchange A process by which a sender and receiver can establish a secret key via public discussion. Once the key has been agreed, the sender can use a cipher such as DES to encrypt a message.

  digital signature A method for proving the authorship of an electronic document. Often this is generated by the author encrypting the document with his or her private key.

  encipher To turn the original message into the enciphered message.

  encode To turn the original message into the encoded message.

  encrypt To encipher or encode.

  encryption algorithm Any general encryption process which can be specified exactly by choosing a key.

  homophonic substitution cipher A cipher in which there are several potential substitutions for each plaintext letter. Crucially, if there are, say, six potential substitutions for the plaintext letter a, then these six characters can only represent the letter a. This is a type of monoalphabetic substitution cipher.

  key The element that turns the general encryption algorithm into a specific method for encryption. In general, the enemy may be aware of the encryption algorithm being used by the sender and receiver, but the enemy must not be allowed to know the key.

  key distribution The process of ensuring that both sender and receiver have access to the key required to encrypt and decrypt a message, while making sure that the key does not fall into enemy hands. Key distribution was a major problem in terms of logistics and security before the invention of public key cryptography.

  key escrow A scheme in which users lodge copies of their secret keys with a trusted third party, the escrow agent, who will pass on keys to law enforcers only under certain circumstances, for example if a court order is issued.

  key length Computer encryption involves keys which are numbers. The key length refers to the number of digits or bits in the key, and thus indicates the biggest number that can be used as a key, thereby defining the number of possible keys. The longer the key length (or the greater the number of possible keys), the longer it will take a cryptanalyst to test all the keys.

  monoalphabetic substitution cipher A substitution cipher in which the cipher alphabet is fixed throughout encryption.

  National Security Agency (NSA) A branch of the U.S. Department of Defense, responsible for ensuring the security of American communications and for breaking into the communications of other countries.

  onetime pad The only known form of encryption that is unbreakable. It relies on a random key that is the same length as the message. Each key can be used once and only once.

  plaintext The original message before encryption.

  polyalphabetic substitution cipher A substitution cipher in which the cipher alphabet changes during the encryption, for example the Vigenère cipher. The change is defined by a key.

  Pretty Good Privacy (PGP) A computer encryption algorithm developed by Phil Zimmermann, based on RSA.

  private key The key used by the receiver to decrypt messages in a system of public key cryptography. The private key must be kept secret.

  public key The key used by the sender to encrypt messages in a system of public key cryptography. The public key is available to the public.

  public key cryptography A system of cryptography which overcomes the problems of key distribution. Public key cryptography requires an asymmetric cipher, so that each user can create a public encryption key and a private decryption key.

  quantum computer An immensely powerful computer that exploits quantum theory, in particular the theory that an object can be in many states at once (superposition), or the theory that an object can be in many universes at once. If scientists could build a quantum computer on any reasonable scale, it would jeopardize the security of all current ciphers except the onetime pad cipher.

  quantum cryptography An unbreakable form of cryptography that exploits quantum theory, in particular the uncertainty principle-which states that it is impossible to measure all aspects of an object with absolute certainty. Quantum cryptography guarantees the secure exchange of a random series of bits, which is then used as the basis for a onetime pad cipher.

  RSA The first system that fitted the requirements of public key cryptography, invented by Ron Rivest, Adi Shamir and Leonard Adleman in 1977.

  steganography The science of hiding the existence of a message, as opposed to cryptography, which is the science of hiding the meaning of a message.

  substitution cipher A system of encryption in which each letter of a message is replaced with another character, but retains its position within the message.

  symmetric key cryptography A form of cryptography in which the key required for encrypting is the same as the key required for decrypting. The term describes all traditional forms of encryption, i.e. those in use before the 1970s.

  transposition cipher A system of encryption in which each letter of a message changes its position within the message, but retains its identity.

  Vigenère cipher A polyalphabetic cipher which was developed around 1500. The Vigenère square contains 26 separate cipher alphabets, each one a Caesar-shifted alphabet, and a keyword defines which cipher alphabet should be used to encrypt each letter of a message.

  Acknowledgments

  While writing this book I have had the privilege of meeting some of the world’s greatest living codemakers and codebreakers, ranging from those who worked at Bletchley Park to those who are devel
oping the ciphers that will enrich the Information Age. I would like to thank Whitfield Diffie and Martin Hellman, who took the time to describe their work to me while I was in sunny California. Similarly, Clifford Cocks, Malcolm Williamson and Richard Walton were enormously helpful during my visit to cloudy Cheltenham. In particular, I am grateful to the Information Security Group at Royal Holloway College, London, who allowed me to attend the M.Sc. course on information security. Professor Fred Piper, Simon Blackburn, Jonathan Tuliani, and Fauzan Mirza all taught me valuable lessons about codes and ciphers.

  While I was in Virginia, I was fortunate to be given a guided tour of the Beale treasure trail by Peter Viemeister, an expert on the mystery. Furthermore, the Bedford County Museum and Stephen Cowart of the Beale Cypher and Treasure Association helped me to research the subject. I am also grateful to David Deutsch and Michele Mosca of the Oxford Centre for Quantum Computation, Charles Bennett and his research group at IBM’s Thomas J. Watson Laboratories, Stephen Wiesner, Leonard Adleman, Ronald Rivest, Paul Rothemund, Jim Gillogly, Paul Leyland and Neil Barrett.

  Derek Taunt, Alan Stripp and Donald Davies kindly explained to me how Bletchley Park broke Enigma, and I was also helped by the Bletchley Park Trust, whose members regularly give enlightening lectures on a variety of topics. Dr. Mohammed Mrayati and Dr. Ibrahim Kadi have been involved in revealing some of the early breakthroughs in Arab cryptanalysis, and were kind enough to send me relevant documents. The periodical Cryptologia also carried articles about Arabian cryptanalysis, as well as many other cryptographic subjects, and I would like to thank Brian Winkel for sending me back issues of the magazines.

  I would encourage readers to visit the National Cryptologic Museum near Washington, D.C. and the Cabinet War Rooms in London, and I hope that you will be as fascinated as I was during my visits. Thank you to the curators and librarians of these museums for helping me with my research. When I was pressed for time, James Howard, Bindu Mathur, Pretty Sagoo, Anna Singh and Nick Shearing all helped me to uncover important and interesting articles, books and documents, and I am grateful to them for their efforts. Thanks also go to Antony Buonomo at www.vertigo.co.uk who helped me to establish my Web site.

  As well as interviewing experts, I have also depended on numerous books and articles. The list of further reading contains some of my sources, but it is neither a complete bibliography nor a definitive reference list. Instead, it merely includes material that may be of interest to the general reader. Of all the books I have come across during my research, I would like to single out one in particular: The Codebreakers by David Kahn. This book documents almost every cryptographic episode in history, and as such it is an invaluable resource.

  Various libraries, institutions and individuals have provided me with photographs. All the sources are listed in the picture credits, but particular thanks go to Sally McClain, for sending me photographs of the Navajo code talkers; Professor Eva Brann, for discovering the only known photo of Alice Kober; Joan Chadwick, for sending me a photo of John Chadwick; and Brenda Ellis, for allowing me to borrow photos of James Ellis. Thanks also go to Hugh Whitemore, who gave me permission to use a quote from his play Breaking the Code, based on Andrew Hodges’ book Alan Turing-The Enigma.

  On a personal note, I would like to thank friends and family who put up with me over the two years while I was writing this book. Neil Boynton, Dawn Dzedzy, Sonya Holbraad, Tim Johnson, Richard Singh and Andrew Thompson all helped me to keep sane while I was struggling with convoluted cryptographic concepts. In particular, Bernadette Alves supplied me with a rich mixture of moral support and perceptive criticism. Traveling back in time, thanks also go to all the people and institutions that have shaped my career, including Wellington School, Imperial College and the High Energy Physics Group at Cambridge University; Dana Purvis, at the BBC, who gave me my first break in television; and Roger Highfield, at the Daily Telegraph, who encouraged me to write my first article.

  Finally, I have had the enormous good fortune to work with some of the best people in publishing. Patrick Walsh is an agent with a love of science, a concern for his authors and a boundless enthusiasm. He has put me in touch with the kindest and most capable publishers, most notably Fourth Estate, whose staff endure my constant stream of queries with great spirit. Last, but certainly not least, my editors, Christopher Potter, Leo Hollis and Peternelle van Arsdale, have helped me to steer a clear path through a subject that twists and turns its way across three thousand years. For that I am tremendously grateful.

  Further Reading

  The following is a list of books aimed at the general reader. I have avoided giving more detailed technical references, but several of the texts listed contain a detailed bibliography. For example, if you would like to know more about the decipherment of Linear B (Chapter 5), then I would recommend The Decipherment of Linear B by John Chadwick. However, if this book is not detailed enough, then please refer to the references it contains.

  There is a great deal of interesting material on the Internet relating to codes and ciphers. In addition to the books, I have therefore listed a few of the Web sites that are worth visiting.

  General

  Kahn, David, The Codebreakers (New York: Scribner, 1996).

  A 1,200-page history of ciphers. The definitive story of cryptography up until the 1950s.

  Newton, David E., Encyclopedia of Cryptology (Santa Barbara, CA: ABC-Clio, 1997).

  A useful reference, with clear, concise explanations of most aspects of ancient and modern cryptology.

  Smith, Lawrence Dwight, Cryptography (New York: Dover, 1943).

  An excellent elementary introduction to cryptography, with more than 150 problems. Dover publishes many books on the subject of codes and ciphers.

  Beutelspacher, Albrecht, Cryptology (Washington, D.C.: Mathematical Association of America, 1994).

  An excellent overview of the subject, from the Caesar cipher to public key cryptography, concentrating on the mathematics rather than the history. It is also the cryptography book with the best subtitle: An Introduction to the Art and Science of Enciphering, Encrypting, Concealing, Hiding, and Safeguarding, Described Without any Arcane Skullduggery but not Without Cunning Waggery for the Delectation and Instruction of the General Public.

  Chapter 1

  Gaines, Helen Fouché, Cryptanalysis (New York: Dover, 1956).

  A study of ciphers and their solution. An excellent introduction to cryptanalysis, with many useful frequency tables in the appendix.

  Al-Kadi, Ibraham A., “The origins of cryptology: The Arab contributions,”

  Cryptologia, vol. 16, no. 2 (April 1992), pp. 97–126.

  A discussion of recently discovered Arab manuscripts, and the work of al-Kindī.

  Fraser, Lady Antonia, Mary Queen of Scots (London: Random House, 1989).

  A highly readable account of the life of Mary Queen of Scots.

  Smith, Alan Gordon, The Babington Plot (London: Macmillan, 1936).

  Written in two parts, this book examines the plot from the points of view of both Babington and Walsingham.

  Steuart, A. Francis (ed.), Trial of Mary Queen of Scots (London: William Hodge, 1951).

  Part of the Notable British Trials series.

  Chapter 2

  Standage, Tom, The Victorian Internet (London: Weidenfeld & Nicolson, 1998). The remarkable story of the development of the electric telegraph.

  Franksen, Ole Immanuel, Mr Babbage’s Secret (London: Prentice-Hall, 1985). Contains a discussion of Babbage’s work on breaking the Vigenère cipher.

  Franksen, Ole Immanuel, “Babbage and cryptography. Or, the mystery of Admiral Beaufort’s cipher,” Mathematics and Computer Simulation, vol. 35, 1993, pp. 327–67.

  A detailed paper on Babbage’s cryptological work, and his relationship with Rear Admiral Sir Francis Beaufort.

  Rosenheim, Shawn, The Cryptographic Imagination (Baltimore, MD: Johns Hopkins University Press, 1997).

  An academic assessment of the cryptographi
c writings of Edgar Allan Poe and their influence on literature and cryptography.

  Poe, Edgar Allan, The Complete Tales and Poems of Edgar Allan Poe (London: Penguin, 1982).

  Includes “The Gold Bug.”

  Viemeister, Peter, The Beale Treasure: History of a Mystery (Bedford, VA: Hamilton’s, 1997).

  An in-depth account of the Beale ciphers written by a respected local historian. It includes the entire text of the Beale pamphlet, and is most easily obtained directly from the publishers; Hamilton’s, P.O. Box 932, Bedford, VA, 24523, USA.

  Chapter 3

  Tuchman, Barbara W., The Zimmermann Telegram (New York: Ballantine, 1994). A highly readable account of the most influential decipherment in the First World War.

  Yardley, Herbert O., The American Black Chamber (Laguna Hills, CA: Aegean Park Press, 1931).

  A racy history of cryptography, which was a controversial best-seller when it was first published.

  Chapter 4

  Hinsley, F.H., British Intelligence in the Second World War: Its Influence on Strategy and Operations (London: HMSO, 1975).

  The authoritative record of intelligence in the Second World War, including the role of Ultra intelligence.

  Hodges, Andrew, Alan Turing: The Enigma (London: Vintage, 1992). The life and work of Alan Turing. One of the best scientific biographies ever written.

  Kahn, David, Seizing the Enigma (London: Arrow, 1996).