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

by Simon Singh

  On December 18, 1997, Cocks delivered his talk. After almost three decades of secrecy, Ellis, Cocks and Williamson received the acknowledgment they deserved. Sadly, James Ellis had died just one month earlier on November 25, 1997, at the age of seventy-three. Ellis joined the list of British cipher experts whose contributions would never be recognized during their lifetimes. Charles Babbage’s breaking of the Vigenère cipher was never revealed during his lifetime, because his work was invaluable to British forces in the Crimea. Instead, credit for the work went to Friedrich Kasiski. Similarly, Alan Turing’s contribution to the war effort was unparalleled, and yet government secrecy demanded that his work on Enigma could not be revealed.

  In 1987, Ellis wrote a classified document that recorded his contribution to public key cryptography, which included his thoughts on the secrecy that so often surrounds cryptographic work:

  Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realizes its value. In contrast, the fullest value of cryptography is realized by minimizing the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated that no further benefit can be obtained from continued secrecy.

  7 Pretty Good Privacy

  Just as Whit Diffie predicted in the early 1970s, we are now entering the Information Age, a postindustrial era in which information is the most valuable commodity. The exchange of digital information has become an integral part of our society. Already, tens of millions of e-mails are sent each day, and electronic mail will soon become more popular than conventional mail. The Internet, still in its infancy, has provided the infrastructure for the digital marketplace, and e-commerce is thriving. Money is flowing through cyberspace, and it is estimated that every day half the world’s Gross Domestic Product travels through the Society for Worldwide Interbank Financial Telecommunications network. In the future, democracies that favor referenda will begin to have on-line voting, and governments will use the Internet to help administer their countries, offering facilities such as on-line tax declarations.

  However, the success of the Information Age depends on the ability to protect information as it flows around the world, and this relies on the power of cryptography. Encryption can be seen as providing the locks and keys of the Information Age. For two thousand years encryption has been of importance only to governments and the military, but today it also has a role to play in facilitating business, and tomorrow ordinary people will rely on cryptography in order to protect their privacy. Fortunately, just as the Information Age is taking off, we have access to extraordinarily strong encryption. The development of public key cryptography, particularly the RSA cipher, has given today’s cryptographers a clear advantage in their continual power struggle against cryptanalysts. If the value of N is large enough, then finding p and q takes Eve an unreasonable amount of time, and RSA encryption is therefore effectively unbreakable. Most important of all, public key cryptography is not weakened by any key distribution problems. In short, RSA guarantees almost unbreakable locks for our most precious pieces of information.

  Figure 70 Phil Zimmermann. (photo credit 7.1)

  However, as with every technology, there is a dark side to encryption. As well as protecting the communications of law-abiding citizens, encryption also protects the communications of criminals and terrorists. Currently, the police use wiretapping as a way of gathering evidence in serious cases, such as organized crime and terrorism, but this would be impossible if criminals used unbreakable ciphers. As we enter the twenty-first century, the fundamental dilemma for cryptography is to find a way of allowing the public and business to use encryption in order to exploit the benefits of the Information Age without allowing criminals to abuse encryption and evade arrest. There is currently an active and vigorous debate about the best way forward, and much of the discussion has been inspired by the story of Phil Zimmermann, a man whose attempts to encourage the widespread use of strong encryption have panicked America’s security experts, threatened the effectiveness of the billion-dollar National Security Agency, and made him the subject of an FBI inquiry and a grand jury investigation.

  Phil Zimmermann spent the mid-1970s at Florida Atlantic University, where he studied physics and then computer science. On graduation he seemed set for a steady career in the rapidly growing computer industry, but the political events of the early 1980s transformed his life, and he became less interested in the technology of silicon chips and more worried about the threat of nuclear war. He was alarmed by the Soviet invasion of Afghanistan, the election of Ronald Reagan, the instability caused by an aging Brezhnev and the increasingly tense nature of the Cold War. He even considered taking himself and his family to New Zealand, believing that this would be one of the few places on Earth that would be habitable after a nuclear conflict. But just as he had obtained passports and the necessary immigration papers, he and his wife attended a meeting held by the Nuclear Weapons Freeze Campaign. Rather than flee, the Zimmermanns decided to stay and fight the battle at home, becoming front-line antinuclear activists-they educated political candidates on issues of military policy, and were arrested at the Nevada nuclear testing grounds, alongside Carl Sagan and four hundred other protesters.

  A few years later, in 1988, Mikhail Gorbachev became head of state of the Soviet Union, heralding perestroika, glasnost and a reduction in tension between East and West. Zimmermann’s fears began to subside, but he did not lose his passion for political activism, he merely channeled it in a different direction. He began to focus his attentions on the digital revolution and the necessity for encryption:

  Cryptography used to be an obscure science, of little relevance to everyday life. Historically, it always had a special role in military and diplomatic communications. But in the Information Age, cryptography is about political power, and in particular, about the power relationship between a government and its people. It is about the right to privacy, freedom of speech, freedom of political association, freedom of the press, freedom from unreasonable search and seizure, freedom to be left alone.

  These views might seem paranoid, but according to Zimmermann there is a fundamental difference between traditional and digital communication which has important implications for security:

  In the past, if the government wanted to violate the privacy of ordinary citizens, it had to expend a certain amount of effort to intercept and steam open and read paper mail, or listen to and possibly transcribe spoken telephone conversations. This is analogous to catching fish with a hook and a line, one fish at a time. Fortunately for freedom and democracy, this kind of labor-intensive monitoring is not practical on a large scale. Today, electronic mail is gradually replacing conventional paper mail, and is soon to be the norm for everyone, not the novelty it is today. Unlike paper mail, e-mail messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. This is analogous to driftnet fishing-making a quantitative and qualitative Orwellian difference to the health of democracy.

  The difference between ordinary and digital mail can be illustrated by imagining that Alice wants to send out invitations to her birthday party, and that Eve, who has not been invited, wants to know the time and place of the party. If Alice uses the traditional method of posting letters, then it is very difficult for Eve to intercept one of the invitations. To start with, Eve does not know where Alice’s invitations entered the postal system, because Alice could use any postbox in the city. Her only hope for intercepting one of the invitations is to somehow identify the address of one of Alice’s friends, and infiltrate the local sorting office. She then has to check each and every letter manually. If sh
e does manage to find a letter from Alice, she will have to steam it open in order to get the information she wants, and then return it to its original condition to avoid any suspicion of tampering.

  In comparison, Eve’s task is made considerably easier if Alice sends her invitations by e-mail. As the messages leave Alice’s computer, they will go to a local server, a main entry point for the Internet; if Eve is clever enough, she can hack into that local server without leaving her home. The invitations will carry Alice’s e-mail address, and it would be a trivial matter to set up an electronic sieve that looks for e-mails containing Alice’s address. Once an invitation has been found, there is no envelope to open, and so no problem in reading it. Furthermore, the invitation can be sent on its way without it showing any sign of having been intercepted. Alice would be oblivious to what was going on. However, there is a way to prevent Eve from reading Alice’s e-mails, namely encryption.

  More than a hundred million e-mails are sent around the world each day, and they are all vulnerable to interception. Digital technology has aided communication, but it has also given rise to the possibility of those communications being monitored. According to Zimmermann, cryptographers have a duty to encourage the use of encryption and thereby protect the privacy of the individual:

  A future government could inherit a technology infrastructure that’s optimized for surveillance, where they can watch the movements of their political opposition, every financial transaction, every communication, every bit of e-mail, every phone call. Everything could be filtered and scanned and automatically recognized by voice recognition technology and transcribed. It’s time for cryptography to step out of the shadows of spies and the military, and step into the sunshine and be embraced by the rest of us.

  In theory, when RSA was invented in 1977 it offered an antidote to the Big Brother scenario because individuals were able to create their own public and private keys, and thereafter send and receive perfectly secure messages. However, in practice there was a major problem because the actual process of RSA encryption required a substantial amount of computing power in comparison with symmetric forms of encryption, such as DES. Consequently, in the 1980s it was only government, the military and large businesses that owned computers powerful enough to run RSA. Not surprisingly, RSA Data Security, Inc., the company set up to commercialize RSA, developed their encryption products with only these markets in mind.

  In contrast, Zimmermann believed that everybody deserved the right to the privacy that was offered by RSA encryption, and he directed his political zeal toward developing an RSA encryption product for the masses. He intended to draw upon his background in computer science to design a product with economy and efficiency in mind, thus not overloading the capacity of an ordinary personal computer. He also wanted his version of RSA to have a particularly friendly interface, so that the user did not have to be an expert in cryptography to operate it. He called his project Pretty Good Privacy, or PGP for short. The name was inspired by Ralph’s Pretty Good Groceries, a sponsor of Garrison Keillor’s Prairie Home Companion, one of Zimmermann’s favorite radio shows.

  During the late 1980s, working from his home in Boulder, Colorado, Zimmermann gradually pieced together his scrambling software package. His main goal was to speed up RSA encryption. Ordinarily, if Alice wants to use RSA to encrypt a message to Bob, she looks up his public key and then applies RSA’s one-way function to the message. Conversely, Bob decrypts the ciphertext by using his private key to reverse RSA’s one-way function. Both processes require considerable mathematical manipulation, so encryption and decryption can, if the message is long, take several minutes on a personal computer. If Alice is sending a hundred messages a day, she cannot afford to spend several minutes encrypting each one. To speed up encryption and decryption, Zimmermann employed a neat trick that used asymmetric RSA encryption in tandem with old-fashioned symmetric encryption. Traditional symmetric encryption can be just as secure as asymmetric encryption, and it is much quicker to perform, but symmetric encryption suffers from the problem of having to distribute the key, which has to be securely transported from the sender to the receiver. This is where RSA comes to the rescue, because RSA can be used to encrypt the symmetric key.

  Zimmermann pictured the following scenario. If Alice wants to send an encrypted message to Bob, she begins by encrypting it with a symmetric cipher. Zimmermann suggested using a cipher known as IDEA, which is similar to DES. To encrypt with IDEA, Alice needs to choose a key, but for Bob to decrypt the message Alice somehow has to get the key to Bob. Alice overcomes this problem by looking up Bob’s RSA public key, and then uses it to encrypt the IDEA key. So, Alice ends up sending two things to Bob: the message encrypted with the symmetric IDEA cipher and the IDEA key encrypted with the asymmetric RSA cipher. At the other end, Bob uses his RSA private key to decrypt the IDEA key, and then uses the IDEA key to decrypt the message. This might seem convoluted, but the advantage is that the message, which might contain a large amount of information, is being encrypted with a quick symmetric cipher, and only the symmetric IDEA key, which consists of a relatively small amount of information, is being encrypted with a slow asymmetric cipher. Zimmermann planned to have this combination of RSA and IDEA within the PGP product, but the user-friendly interface would mean that the user would not have to get involved in the nuts and bolts of what was going on.

  Having largely solved the speed problem, Zimmermann also incorporated a series of handy features into PGP. For example, before using the RSA component of PGP, Alice needs to generate her own private key and public key. Key generation is not trivial, because it requires finding a pair of giant primes. However, Alice only has to wiggle her mouse in an erratic manner, and the PGP program will go ahead and create her private key and public key-the mouse movements introduce a random factor which PGP utilizes to ensure that every user has their own distinct pair of primes, and therefore their own unique private key and public key. Thereafter Alice merely has to publicize her public key.

  Another helpful aspect of PGP is its facility for digitally signing an email. Ordinarily e-mail does not carry a signature, which means that it is impossible to verify the true author of an electronic message. For example, if Alice uses e-mail to send a love letter to Bob, she normally encrypts it with his public key, and when he receives it he decrypts it with his private key. Bob is initially flattered, but how can he be sure that the love letter is really from Alice? Perhaps the malevolent Eve wrote the e-mail and typed Alice’s name at the bottom. Without the reassurance of a handwritten ink signature, there is no obvious way to verify the authorship. Alternatively, imagine that a bank receives an e-mail from a client, which instructs that all the client’s funds should be transferred to a private numbered bank account in the Cayman Islands. Once again, without a handwritten signature, how does the bank know that the e-mail is really from the client? The e-mail could have been written by a criminal attempting to divert the money to his own Cayman Islands bank account. In order to develop trust on the Internet, it is essential that there is some form of reliable digital signature.

  The PGP digital signature is based on a principle that was first developed by Whitfield Diffie and Martin Hellman. When they proposed the idea of separate public keys and private keys, they realized that, in addition to solving the key distribution problem, their invention would also provide a natural mechanism for generating e-mail signatures. In Chapter 6 we saw that the public key is for encrypting and the private key for decrypting. In fact the process can be swapped around, so that the private key is used for encrypting and the public key is used for decrypting. This mode of encryption is usually ignored because it offers no security. If Alice uses her private key to encrypt a message to Bob, then everybody can decrypt it because everybody has Alice’s public key. However, this mode of operation does verify authorship, because if Bob can decrypt a message using Alice’s public key, then it must have been encrypted using her private key-only Alice has access to her private key, so the messag
e must have been sent by Alice.

  In effect, if Alice wants to send a love letter to Bob, she has two options. Either she encrypts the message with Bob’s public key to guarantee privacy, or she encrypts it with her own private key to guarantee authorship. However, if she combines both options she can guarantee privacy and authorship. There are quicker ways to achieve this, but here is one way in which Alice might send her love letter. She starts by encrypting the message using her private key, then she encrypts the resulting ciphertext using Bob’s public key. We can picture the message surrounded by a fragile inner shell, which represents encryption by Alice’s private key, and a strong outer shell, which represents encryption by Bob’s public key. The resulting ciphertext can only be deciphered by Bob, because only he has access to the private key necessary to crack the strong outer shell. Having deciphered the outer shell, Bob can then easily decipher the inner shell using Alice’s public key-the inner shell is not meant to protect the message, but it does prove that the message came from Alice, and not an impostor.