The Code Book
Richard M. Todd
- Vice President, Community Development
Published June 1, 2001 | June 2001 issue
By Simon Singh
A version of the FedLine® software that financial institutions use to conduct business with the Federal Reserve banks is being upgraded this year to incorporate a new data security system known as public key infrastructure (PKI). Web-based services and vendors already use PKI to encrypt personal data and credit card information, and more complex and ambitious applications in electronic commerce and finance are developing. Nonetheless, given that computer technology is changing for all sorts of reasons all the time, is there any reason to pay special attention to the spread of PKI in traditional payments and banking businesses?
"Yes" is the answer in Simon Singh's The Code Book, which rates the development of PKI as the greatest achievement in data encryption since the days of Julius Caesar and his substitution cipher. I agree, and I encourage anyone with an interest in electronic commerce, data security, data privacy or civil liberties to learn more about PKI. In particular, bankers using the Fed's new PKI who understand the basic workings and significance of the technology will be better equipped to carry out the responsibilities it entails.
Reading The Code Book is an entertaining and effective way to get a basic understanding, not just of public keys but also of other past, current and future methods of data encryption. In his introduction, Singh declares that his two main objectives are "to chart the evolution of codes" and "to demonstrate how the subject [encryption] is more relevant today than ever before." He uses the theme of evolution, driven by competition between code makers and code breakers, to weave "stories of political intrigue and tales of life and death" into a coherent history of encryption from ancient times.
Although I wish the book included more coverage of some of the practical aspects of implementing data security, Singh achieves his two objectives because, as he proved in his earlier book on Fermat's last theorem, he knows how to use a good story to illustrate a difficult point. Singh opens by putting the fate of Mary Queen of Scots in the hands of Thomas Phelippes, Queen Elizabeth's code breaker. Before the ax falls, Singh has traced encryption back to the classical era, introduced the fundamental idea of the alphabetic substitution cipher (for example, A replaced by N, B by O, C by P) and followed statistical cipher breaking from Arab scholars to Renaissance courts. He goes on to discuss Louis XIV's mysterious Man in the Iron Mask, a still-unreadable 19th-century message that could lead you to $20 million of gold buried in Virginia, the deciphering of the Rosetta stone and several ancient scripts, the Zimmerman telegram and other German cryptographic blunders in World War I, and the familiar but still amazing story of determined Polish and English geniuses who broke formidable Nazi ciphers (and secretly developed and then secretly destroyed the first programmable computer while they were at it).
Along the way, Singh develops additional themesthe increasing complexity and automation of code making and breaking; the role of technologies like telegraphy and radio in spurring military, commercial and consumer interest in encryption; and the ability of secret government agencies to sometimes monopolize superior code making and breaking technologies. At the same time, he builds his main thesis of competitive evolution, of action and reaction, by skillfully overlapping the end of one story with the beginning of the next.
After an extended historical prelude, The Code Book turns to PKI. The "public" in PKI highlights its novel featurea public, or publicly available, encryption key. Following his story-telling motif, Singh introduces public key concepts by relating how public key encryption was invented twice, independently, in the 1970s. He then discusses one widely used PKI package to illustrate both the infrastructure needed to support public keys and some public policy issues related to encryption.
Thirty years ago the concept of a public encryption key was an oxymoron. Encryption had always required a shared secretthe sender and the intended recipient(s) share an encryption key, while keeping it a secret from others. The sender uses the shared private key to scramble the message into unreadable ciphertext, and the recipients reverse the process, using the same shared key to unscramble the ciphertext back into readable plaintext. Because the same key is used to encrypt and decrypt, this conventional encryption technology is also known as symmetric key encryption.
Secure encryption using a symmetric key requires a strong encryption algorithm and a safe but practical method for sharing the key. Although Singh provides numerous historical examples of encryption algorithms that were broken by determined cryptanalysts, computerized algorithms strong enough for commercial use are readily available today. However, the secure distribution of a symmetric key to all its intended users remains a serious practical problem. Its significance has grown with the expansion of technologies that facilitate worldwide communication, beginning with the telegraph in the 19th century and then telephones and radio. By World War II, for example, navies were hard pressed to get each new shared key to their far-flung ships fast enough to prevent their enemies from breaking the previously distributed key.
But it was the Internet that really pushed the symmetric key distribution problem beyond its practical limits. By the early 1970s, Whitfield Diffie, a maverick American cryptographer, was anticipating a worldwide computer network and wondering how individuals communicating only over that network could maintain privacy. It wouldn't work for one party to transmit a symmetric key to the other, because an eavesdropper might intercept that transmission and have the secret for decrypting all subsequent messages, too.
Many cryptographers saw little hope for a solution, but Diffie found allies in Martin Hellwig and Ralph Merkle at Stanford University and persevered. With a sympathy for the loneliness and exhilaration of abstract research that he also displayed in his Fermat's Enigma, Singh conveys the atmosphere of freedom, faith, imagination, energy and nagging doubt in which the team struggled. Finally they startled the cryptographic world with a clever sequence of messages by which two parties could agree on a symmetric key without ever transmitting it in the clear.
Then, in 1975, Diffie hit upon the idea of using not one shared key but a pair of keys for each person. One key in the pair would be the individual's private key, specific to that person and shared with no one. The individual's other key would be made public. The two keys are relatedwhat one of them encrypts, only the other one can decrypt. With this system of asymmetric keys, Alice can send Bob a message that she knows only Bob can read, even if she has never met or communicated with Bob before. To do so, she looks up Bob's public key in a directory and uses it to encrypt her message to Bob. She sends the encrypted text to Bob, the only person in the world with the matching private key needed to decrypt the message. Even if Alice sends the encrypted message to Bob over a public channel like the radio spectrum or newspaper classified ads, she knows that no one but Bob can decrypt it. If Bob wants to respond confidentially, he looks up Alice's public key to encrypt his reply. They can even use this method to secretly exchange a conventional symmetric key.
Asymmetric keys also open up some new possibilities. For example, if Alice wants to publish a manifesto that all the world will recognize as coming from her and not an imposter, she encrypts the text with her private key and publishes the result. Anyone who wants to read it looks up Alice's public key and tries to decrypt her ciphertext. If they succeed in recovering a readable document, they can be sure that only Alice's private key could have encrypted the ciphertext. And by cleverly sequencing the use of both her private and Bob's public key, Alice can securely encrypt a message to Bob with a digital signature that assures Bob it came from her.
Although his idea of asymmetric keys paved the way, Diffie didn't know how to create pairs of keys with the desired properties. That breakthrough required mathematical insight into so-called one-way functions. These are abstract analogs of a process like breaking eggseasy to do, and hard to undo. The insight required is to find a special one-way function that can be reversed if you have a secret hint, which becomes the private key. Singh relates how this breakthrough was achieved by the team of Ron Rivest, Adi Shamir and Leonard Adleman at MIT. Their patented RSA® algorithm is the current mainstay of public key encryption on the Internet.
With the help of material recently declassified by British intelligence, Singh then tells of the British spy agency mathematicians who invented the same public key technology in secret a few years ahead of the Stanford-MIT teams. Singh again does a fine job of describing the intellectually rich and free (albeit cloistered) research atmosphere that underlay the British achievements. And he uses this example to point out that the public, and even the academic research community, may at any time be completely unaware of the advanced cryptographic capabilities of secret government agencies.
As innovative as public key encryption is, it achieves practical significance only when embedded in a package of support structures and institutions that make up the infrastructure of PKI. Singh only touches on this important but perhaps rather mundane topic, mainly by describing the components of Phillip Zimmerman's Pretty Good Privacy(r) (PGP), the first complete PKI package available to the public. PGP software made PKI easy enough for unsophisticated users, by creating and securing their keys and automating the encryption and decryption process. This was an important achievement, and it could have been used to discuss the many practical issues that still surround widespread use of PKI.
Instead, Singh focuses on the public policy issues surrounding Zimmerman's indictment for exporting a strategic weapon, which ensued when Zimmerman posted his PGP software on a public Web site. This interesting and important story allows Singh to highlight the competing interests of law enforcement, which seeks to keep strong encryption technology out of the hands of criminals, and civil liberty, which is threatened by government control of strong encryption. Singh's sympathies clearly lie with Zimmerman.
Although PKI is only beginning to flower in practical applications, Singh looks ahead to future cryptographic technologies. Continuing his theme of competitive evolution, he foresees a race between quantum computing and quantum cryptography. Both, as their names suggest, involve the practical application of quantum mechanics, the strange physics governing the behavior of subatomic particles. The former attempts to use quantum mechanics to build exceedingly powerful computers that could break current PKI encryption algorithms. Singh assumes, probably realistically, that governments would at least initially have a near monopoly on powerful quantum computers and could use them to invade PKI-based privacy and deny civil liberties.
But Singh also thinks that applied quantum mechanics might bring the long-competitive evolution of cryptography to an end by providing final victory to personal privacy. That is the promise he sees in quantum cryptography, whose roots go back over 30 years to Stephen Weisner's long-neglected thesis work on how quantum mechanics could, in theory, be used to prevent the counterfeiting of money! Weisner's idea, as subsequently developed, exploits Heisenberg's famous uncertainty principle to solve the key distribution problem once and for all. Prototypes of this technology already work over distances of up to about 15 miles.
Singh concludes The Code Book by noting that quantum cryptography would be absolutely unbreakable, and if it "can be engineered to operate over long distances, the evolution of ciphers will stop. The quest for privacy will have come to an end. The technology will be available to guarantee secure communications for governments, the military, businesses and the public. The only question remaining would be whether or not the government would allow us to use the technology. How would governments regulate quantum cryptography, so as to enrich the Information Age, without protecting criminals?"
Although The Code Book is informative, thought-provoking, entertaining and generally very approachable, it is not intended to be a well-rounded introduction to PKI and other encryption technologies, and it sometimes gets into mathematical concepts (prime numbers, functions) that may put some readers off. As noted above, Singh is not particularly interested in the practical side of implementing technologies. Regarding PKI, for example, Singh only briefly addresses the question of how Alice can be sure she has found the public key that truly belongs to Bob, and not another key falsely published by someone pretending to be Bob. This question is very important in practical applications such as e-commerce, and the common solution is for individuals to be certified by a certificate authority (CA). A CA is a widely trusted entity that takes on the responsibility of verifying a person's identity and then publishing an electronic certificate that contains both the individual's public key and the CA's unique digital signature. If CAs can be trusted, then everyone can rely on the certificates they provide to locate a valid public key for any individual they wish to communicate with securely. Who will take on these CA responsibilities, how we decide which CAs we can trust and other practical issues that could compromise the ultimate success of the promising PKI technology are largely ignored by Singh.
Similarly, he more or less assumes that individuals can easily keep their private key safe and still remember it when they need it. In fact, private keys are very long numbers that are impractical to remember or type, so they essentially have to be stored in an electronic medium such as a computer disk or a smart chip. Once stored, they become vulnerable to digital or physical theft, and bankers and other new certificate owners need to understand those vulnerabilities and how to manage them. Such practical matters are simply not in the scope of The Code Book, and readers will have to look elsewhere to fill these gaps. Nonetheless, Singh's talent for making complicated topics interesting makes The Code Book a good introduction to encryption, PKI and many related policy and business issues.