- The Search for an Innovative Key Delivery Solution
- Developing an Innovative Secret Key Delivery Solution
- A New Solution: Diffie-Hellman-Merkle Key Agreement
- Separate Encryption and Decryption Keys
So far in our discussion, Alice and Bob share the same key, and both of them use the identical secret key to encrypt and decrypt. Systems that use shared secret keys are called symmetric cipher methods. Diffie, Hellman, and Merkle also envisioned systems, called asymmetric ciphers, that have separate encryption and decryption keys. One key encrypts, and the other one, a different key, decrypts. Diffie's 1976 paper about this system marked the first time in 3,000 years of cryptographic study that anyone outside government institutions knew that such an idea had been conceived.
Diffie's paper ended up in the hands of Ronald Rivest at MIT. Rivest persuaded Adi Shamir and Leonard Adleman, also at MIT, to help him search for the math that would make this idea a reality.
Public Key: A Top Secret Discovery
In 1969, the British military asked British Intelligence at Government Communications Headquarters (GCHQ) to look into a problem with secure military communications. The military could see that miniaturization of radio equipment was going to allow every soldier to be in continual radio contact. But ensuring that such military communications were secure required the distribution of secret keys to all those soldiers, a daunting problem. GCHQ went to work trying to solve the dilemma.
The problem was given to James Ellis, one of Britain's prominent government cryptographers, known by the GCHQ as somewhat eccentric.
But Ellis was also known for his brilliance, which led him to read and collect a broad range of scientific materials. In those materials he found the seed of the idea that was proposed by the Stanford trio: an asymmetric cipher, in which one key encrypted and the other key decrypted. Ellis's brainstorm came after he read a Bell Telephone report written during WWII. To ensure the security of telephone speech, the report's unknown author proposed that the recipient mask the sender's message by adding noise to the line. Because the recipient had added the noise, theoretically the recipient should be able to remove it. It didn't work that way in reality because of the difficulty of removing noise from speech communications. But Ellis applied the noise principle to enciphering text. He suggested that it could be a way of achieving security without exchanging any secrets. Unfortunately, Ellis was not a mathematician. Although he knew he needed a special one-way function that only the receiver could reverse, he didn't have the mathematics background to implement his idea.
Ellis made his idea known to the higher-ups, and for several years GCHQ's brightest minds worked on a practical solution to the problem. The solution came to a novice cryptographer, Clifford Cocks, just six weeks after he joined GCHQ in 1973. Although Cocks knew very little about cryptography, he'd specialized in number theory at Cambridge University before joining British Intelligence.
According to cryptographic historian Simon Singh in The Code Book, Cocks claimed that it took him half an hour to solve the mathematical puzzle with prime numbers and factoring, the same solution that has become known as RSA (after Rivest, Shamir, and Adleman). At the time Cocks solved the problem, he had no idea that GCHQ had been working on its solution for years or that he'd discovered one of the most important cryptographic methods ever conceived. At that time, GCHQ couldn't put Cock's discovery into effect because there wasn't yet enough computing power available to make it practical.
In 1974 Malcolm Williamson, a mathematician and long-time friend of Cocks, joined GCHQ. When Williamson heard about Cocks's discovery, he set out to disprove it. Instead, he discovered what the world would soon know as Diffie-Hellman key exchange at about the same time it was being developed across the Atlantic.
By 1975, the British had discovered all the essential components of public key cryptography, but no one was talking. It was top secret. The credit went to the Americans, who commercialized and patented these ideas, which are key to the advancement of the digital revolution.
|RSA claimed it had public key technology before Diffie-Hellman.|
The RSA method solved the authentication and key exchange problems and thus enabled the assurances needed in our burgeoning digital age.
This powerful system can seem complex if you look at all its capabilities at once. Chapter 10 shows how public/private key pairs provide easy key exchange and confidentiality. Chapter 11 briefly examines the major math trick behind public key cryptography. After that, we look at how public key cryptography (and RSA in particular) goes beyond confidentiality to give us digital signatures needed for e-commerce.