Who invented public key cryptography

Mulling it over while in his pajamas one night, he has a startling insight, but he's not sure his math skills are strong enough to unravel its implications. Enter two Cambridge University math grads who have quit advanced-degree programs and come to work in the world of spooks because - well, because they need a job. Friendly rivals since they were schoolboys, they're fellow lodgers who, ruminating in their off hours, separately happen upon algorithms that would make the engineer's idea fly the same algorithms published to astonishment and acclaim by the Americans a few years later.

Then, after their agency tries and fails to knock down their work, it decides to sit on the findings and stay on the sidelines - even when the American discovery of public key touches off a cryptographic and commercial revolution. During the late '60s, intelligence agencies were giving much thought to the fast-breaking developments in computers and wireless technologies, and to ways to protect government data that traveled over these channels.

While encryption hardware was evolving, one crucial part of the process hadn't changed since World War I: the need to distribute and use digital keys to scramble and unscramble messages.

The process was a bottleneck. To ensure security, a unique key had to be generated for every pair of people who needed to conduct secret conversations; then those keys had to be delivered securely. Thousands of people were in the classified loop, and that meant generating millions of keys that needed to be protected.

Managing the system was, to put it in a very un-British way, a bitch. Ellis, an orphan who had been raised by his grandparents in London's East End, had joined the GCHQ in the '50s, then left for a time to work presumably on security issues at the post office.

By , in his 40s, Ellis was back at the GCHQ and, as part of its Communications-Electronics Security Group, was hunting for a way past the seemingly intractable conundrum of key management. It is difficult to peer into the office politics of his world, and doubly so at a distance of 30 years.

Still, it's clear that this assignment placed him neither at the white-hot center of international intrigue nor at the forefront of research. Ellis had his doubts about finding a solution to the problem. After all, if they were in identical situations, how could one possibly be able to receive what the other could not? Thus there was no incentive to look for something so clearly impossible. The scheme, labeled Project C43, was an ingenious method of analog voice scrambling that worked by the use of distortion.

To conceptualize it, imagine you want to send a message over the phone line and you suspect someone is listening. How can you keep the message secure? The Bell scientist suggested that the person receiving the message simply add noise to the line.

When the message arrives, message and noise are intermingled and eavesdroppers will hear only garbage. The recipient, knowing precisely how the noise was added, can subtract it from the transmission and wind up with the original, unscrambled message.

For modern cryptography, Project C43 was useless. For one thing, it was an analog model, and by the late '60s the world was going digital. But Ellis found it exciting nevertheless: The sender of a message didn't have to worry about an enemy listening in, even if the foe knew how the system worked. What made this possible was that, in contrast to conventional cryptography, the recipient is a collaborator in the encryption. That raised a tantalizing question for Ellis: Could a secure, digitally encrypted message be sent without keys being exchanged in advance?

This heretical idea popped into his head one night after he had gone to bed. Sitting in the dark in his Cheltenham bedroom, he decided it could, and he came up with an existence proof for the question.

His name for it would embody the contradiction: nonsecret encryption. It worked by taking the digitized, nonsecret exchange between two parties - call them Alice and Bob - and submitting it to a series of three mathematical alterations. Let's say, for instance, that Bob wants to send a message to Alice. The problem is Eve, an unwelcome snoop who is familiar with the way this particular scrambling system works, down to the mathematical formulas themselves - since these rules are, in this scenario, public knowledge.

Alice gets the ball rolling by generating a large number chosen at random. This, in effect, is a secret key that only she holds. Now comes a crucial act suggested to Ellis by Project C Alice, who is the intended recipient, actually initiates the scrambling process by executing a mathematical operation to transform the key to a new number.

She sends the new number to Bob. The new number is analogous to what we know as a public key. Since an important property of the mathematical operation Alice uses is that it cannot be calculated in reverse, even by an outside observer who has this second, nonsecret number, and also knows what function produced it, cannot do an inverse calculation to retrieve the first, secret number.

This is something that will remain known only to the recipient, Alice. Now that Bob has this nonsecret number, he uses a second operation to scramble the private message he has for Alice, which he then sends.

With a third mathematical function, Alice uses her original, secret key to essentially strip the encryption from the message. She can now read the plain text, and Eve can do nothing but gnash her teeth as she watches a very public exchange of what, to her, will remain gibberish. The nonsecret key acts like the line noise in Project C Since such keys wouldn't have to be protected, it would be possible to have secure communications without all the prior arrangements necessary in conventional crypto, opening the way for protected communications on a vast scale.

Ellis hadn't been assigned to unleash a revolution in cryptography, but the possibility that he had done so had to be dealt with. The very basis of the idea - its "nonsecret" element - seemed so heretical that, to some at the GCHQ, disproving his thesis would be striking a blow for the natural order of things. Just before Christmas, he delivered his judgment: "Unfortunately, I can't see anything wrong with this.

However, the mathematician noted, Ellis had presented only a proof that such a system could exist. The unknown remained: Was there really a way of generating a nonsecret key from the original private key? To make it work, you needed to be certain that the Eves of the world could not reverse the first mathematical process and get their hands on the key.

Ellis had conjectured a set of lookup tables that would perform the various scrambling and descrambling calculations but had not developed the specific functions. Until they were formulated, nonsecret encryption would be nothing more than a theoretical curiosity. Ellis did not hide this state of affairs when he formally wrote up his idea in a January internal paper called "The Possibility of Secure Non-Secret Digital Encryption.

The remaining step in the creation of a secure, nonsecret key was not trivial. Even as he set about the search for the nonreversible functions that would make his scheme work, Ellis, an engineer by training, was concerned that his mathematics skills were not up to the task. And despite the possible importance of a nonsecret system, the GCHQ did not assign much brainpower to aid him in the quest.

At times over the next few years, some Communications-Electronics Security Group cryptographers would read Ellis's paper and work for a while on potential solutions, and in a new chief scientist took an interest and assigned some people to the problem.

But while those looking for the mystery functions developed ideas about what the characteristics of such things might be, they had no luck in actually finding one that worked. In , Cocks was a recent arrival in the electronics-security group. He had come to intelligence work from Kings College, Cambridge, where he earned an undergraduate degree in math, and Oxford, where he did graduate work in number theory before deciding to move on.

Although Cocks didn't know much about the GCHQ and really hadn't thought about cryptography as a focus of his work, he knew the agency needed mathematicians. The encryption and decryption operation, T, should be computationally easy to carry out. At least one of the keys must be computationally infeasible for the cryptanalyst to recover even when he knows T, the other key, and arbitrarily many matching plaintext and ciphertext pairs.

Given such a system, Diffie and Hellman proposed that each user keep his decryption key secret and publish his encryption key in a public directory. The total number of keys involved is just twice the number of users, with each user having a key in the public directory and his own secret key, which he must protect in his own self-interest.

Since they were focused on the key distribution problem, Diffie and Hellman called their discovery public-key cryptography. This was the first discussion of two-key cryptography in the open literature. However, Admiral Bobby Inman, while director of the U. In this system, ciphers created with a secret key can be decrypted by anyone using the corresponding public key—thereby providing a means to identify the originator at the expense of completely giving up secrecy.

Ciphers generated using the public key can only be decrypted by users holding the secret key, not by others holding the public key—however, the secret-key holder receives no information concerning the sender. In other words, the system provides secrecy at the expense of completely giving up any capability of authentication. What Diffie and Hellman had done was to separate the secrecy channel from the authentication channel—a striking example of the sum of the parts being greater than the whole.

Single-key cryptography is called symmetric for obvious reasons. A cryptosystem satisfying conditions 1—4 above is called asymmetric for equally obvious reasons. There are symmetric cryptosystems in which the encryption and decryption keys are not the same—for example, matrix transforms of the text in which one key is a nonsingular invertible matrix and the other its inverse.

Even though this is a two-key cryptosystem, since it is easy to calculate the inverse to a non-singular matrix, it does not satisfy condition 3 and is not considered to be asymmetric. Since in an asymmetric cryptosystem each user has a secrecy channel from every other user to him using his public key and an authentication channel from him to all other users using his secret key , it is possible to achieve both secrecy and authentication using superencryption.

Say A wishes to communicate a message in secret to B, but B wants to be sure the message was sent by A. The resulting outer cipher can only be decrypted by B, thus guaranteeing to A that only B can recover the inner cipher. Simple as it is, this protocol is a paradigm for many contemporary applications. Schemmatic approach.

If this can be done, the cryptosecurity of the scheme will be at least as good as the underlying mathematical problem is hard to solve. This has not been proven for any of the candidate schemes thus far, although it is believed to hold in each instance. However, a simple and secure proof of identity is possible based on such computational asymmetry.

A user first secretly selects two large primes and then openly publishes their product. Although it is easy to compute a modular square root a number whose square leaves a designated remainder when divided by the product if the prime factors are known, it is just as hard as factoring in fact equivalent to factoring the product if the primes are unknown. A user can therefore prove his identity, i. The user can be confident that no one can impersonate him since to do so they would have to be able to factor his product.

There are some subtleties to the protocol that must be observed, but this illustrates how modern computational cryptography depends on hard problems. Click Here to Know about a Legend Dr. Abdul Kalam. Toggle navigation Menu. Social Discuss Sign Up Login. Public-key cryptography Famous Inventors. Home inventions Public-key cryptography. Public-key cryptography - Invented by James Henry Ellis. Invented Year. Invention Field.

When Alice sends a new key to Bob, she must ensure that Eve doesn't read the message and thus learn the new key. The obvious way to prevent eavesdropping is to use the old key the key that Alice wants to replace to encrypt the message containing the new key the key that Alice wants Bob to employ in the future.

But Alice can't do this if there is a chance that Eve knows the old key. Alice could rely on a special backup key that she uses only to encrypt new keys, but presumably this key, too, would need to be changed. Problems multiply when Alice wants to send messages to other people. Obviously, Alice shouldn't use the key she uses to encrypt messages to Bob to communicate with other people—she doesn't want one compromised key to reveal everything.

But managing the keys for a large group is an administrative horror; a hundred-user network needs 4, separate keys, all of which need regular changing. In the s, Schneier says, U. Navy ships had to store so many keys to communicate with other vessels that the paper records were loaded aboard with forklifts. Public-key encryption makes key-management much easier. Their discovery can be phrased simply: enciphering schemes should be asymmetric.

For thousands of years all ciphers were symmetric—the key for encrypting a message was identical to the key for decrypting it, but used, so to speak, in reverse.

To change "5 5 15 55" or "6 6 18 66" back into "attack," for instance, one simply reverses the encryption by dividing the numbers with the key, instead of multiplying them, and then replaces the numbers with their equivalent letters.

Thus sender and receiver must both have the key, and must both keep it secret. The symmetry, Diffie and Hellman realized, is the origin of the key-management problem. The solution is to have an encrypting key that is different from the decrypting key—one key to encipher a message, and another, different key to decipher it.

With an asymmetric cipher, Alice could send encrypted messages to Bob without providing him with a secret key. In fact, Alice could send him a secret message even if she had never before communicated with him in any way. If you were to survey the world's cryptographers in , they would all have told you it was impossible. Later the British Secret Service revealed that it had invented these techniques before Diffie and Hellman, but kept them secret—and apparently did nothing with them.

To be precise, Diffie and Hellman demonstrated only that public-key encryption was possible in theory. Rivest, Adi Shamir, and Leonard M.

Adleman—figured out a way to do it in the real world. Factoring a number means identifying the prime numbers which, when multiplied together, produce that number. Thus , can be factored into 2 x 2 x 31 x 1,, where 2, 31, and 1, are all prime. A given number has only one set of prime factors. Surprisingly, mathematicians regard factoring numbers—part of the elementary-school curriculum—as a fantastically difficult task.

Despite the efforts of such luminaries as Fermat, Gauss, and Fibonacci, nobody has ever discovered a consistent, usable method for factoring large numbers.

Instead, mathematicians try potential factors by invoking complex rules of thumb, looking for numbers that divide evenly. For big numbers the process is horribly time-consuming, even with fast computers. The largest number yet factored is digits long. It took computers, most of them fast workstations, more than seven months.