Unlocking Cryptography: Private Key vs. Public Key

Private Key vs. Public Key

Private key cryptography

If you're a big business or spy agency that must make secure transactions with hundreds or millions of customers, it is too much trouble to agree on a new encryption system--a new private key--with every customer or spy. Some organizations get around this problem by using the same encryption system for everyone, but with a different permutation for each person's private key.

As a simple example, say the encryption system requires shifting each letter by a given distance in the alphabet. Each business you deal with would receive a different permutation of this system. For instance, Spy Company A would encode its messages by shifting every letter forward by three letters, turning every "A" into "D" and every "B" into "E." Spy Company B might be instructed to encode its messages by shifting a letter forward by 10 letters, turning "P" into "Z" and "R" into "B."

Clearly there are some basic flaws with this system; you can assign keys only up to 25 different spies and since Spy A knows the general system, it would be relatively easy for A to unlock Spy B's specific permutation of the system.

Real private key cryptographic systems are considerably more complex. The most widely used system in the world is called DES (Digital Encryption Standard), which was developed by IBM in response to a public solicitation by the National Bureau of Standards (NBS), which is now called the National Institute of Standards and Technology (NIST). DES is used by banks for electronic transfers of money and for encryption of passwords on computers.

Problems with private key systems

Although these private key systems have been quite effective, researchers are becoming increasingly successful in attacking DES. In response, NIST has issued a solicitation for a new system, called the Advanced Encryption Standards. NIST is now in the process of evaluating systems that have been submitted by cryptographers worldwide.

There is another issue with private key systems. As good as they are, these systems still require an advance exchange of a key, which is not always possible. For example, if you are buying something from an e-business and want to transmit your credit-card number to them, there is no way for the company to send you a private key to use (which might be time-consuming and expensive) without the possibility of someone intercepting this key. Anytime you send one part of a private key into the world, you run the risk of someone intercepting it and using it to decode all of your messages. And if someone does intercept the key, how do you know you're not receiving a message from a forger?

Public key cryptography

In 1976, Whitfield Diffie and Martin Hellman came up with an innovative idea. What if there were a cryptographic system whereby the key used to encrypt a message is different from the key used to decrypt it? In other words, the sender and the receiver of a message don't work from the same rulebook. The sender can distribute a key to the world that anyone can use to encrypt messages to send. This presents a limited danger to security, because none of these publicly distributed keys can decode the message. The key that can decode the messages is kept--and seen--only by the sender.

This system is now called public key cryptography, so called because anyone can see and use the encryption key, while the sender keeps the decryption key private. There is no need to exchange private keys in advance and to tightly control the distribution of these keys.

It was noticed almost immediately that this approach has an extra benefit. It allows the recipient of a message to know that the message really did come from the sender and not from a forger who has cracked the system.

This additional level of security against forgers is provided in two ways. First, the two companies exchanging messages must both have public key cryptography systems. Second, in a public key cryptographic system, a company can choose which key to distribute publicly and which to keep for its eyes only. A company can distribute a public key that decodes messages and maintain a private key that encodes messages. As long as the private key performs a different function from the public key, the underlying security of the system is safe.

Public key cryptography was immediately recognized as a brilliant concept. It was so brilliant that the National Security Agency initially tried to keep the idea classified and prevent the researchers who invented it from publicizing their findings. They were unsuccessful.

Yet, trying to implement this great theory was tricky. Mathematicians found it very difficult to create an unbreakable system in which the encryption key was different from the decryption key. Most of the time, the decryption key ended up being easily deduced from the encryption key, or the system was too slow to be practical.

Until three mathematicians--Ron Rivest, Adi Shamir and Leonard Adelman--turned the simple process of finding what numbers multiply into which, or factoring, in their favor. The three mathematicians proposed an algorithm named after them that soon gained wide acceptance: the Rivest, Shamir, Adelman (RSA) algorithm.

Making public encryption work: the RSA algorithm

The RSA algorithm provided the first successful implementation of public key cryptography. It relies, crucially, on the fact that, although we know how to multiply two really big numbers quickly, we do not know how to reverse the process quickly at all.

For example, if you take two 100-digit primes, multiply them together to get a 200-digit number, and give the 200-digit number to someone else, that person, using the current state of knowledge, would not be able to factor the number within our lifetime and, therefore, crack the code. Not even the most powerful computers available today provide enough computing power to get close. The upshot: only the person who created this large number from two primes would be able to decode the message.

So, pay attention, all future hackers: if you want to break the code, learn how to factor. The RSA algorithm for public key encryption is currently secure, because no one has been able to factor large numbers quickly or design a computer fast enough to do so. The best methods for factoring numbers are based on the same methods that you learned in grade school. The simplest approach, when faced with a number such as 105, is to start running through all the primes, starting with 2, 3 and 5, and see which number first divides equally into the number you are trying to factor.

Given the number 105, you find very quickly that 105 is divisible by three 35 times, yielding 3 x 35 = 105. By the same approach, you start then with 35, and see quickly that 5 divides into 35, yielding 5 x 7 = 35. You have quickly reached the prime factorization of 105: 3 x 5 x 7, as we saw in our first example.

The surprising fact is that the best-known methods for factoring, known as sieve methods, are basically sophisticated refinements of this approach. When faced with a number of 200 or more digits, these sieve methods take a very long time, even on today's fastest computers, since there are many primes with 100 digits or less. Therefore, until now the RSA algorithm has been secure from attack.

Rivest, Shamir and Adelman were able to develop a public key cryptography system in which the encryption method uses the tremendously large number, achieved by multiplying two tremendously large primes, but the decryption method requires knowing these two factors. A company, spy agency or e-business distributes the multiplied number (which has hundreds of digits) as part of its public key. When the company receives encrypted messages, it uses the factors of this number to decipher the messages.

The future of encryption

In practice, the RSA method is too slow for encrypting and decrypting entire messages. It is used, instead, merely to encrypt a key for a private key cryptographic system. Once that encrypted key is exchanged, the private key system can be used to exchange messages. This approach is now widely used and, in particular, is used for all secure Web-based communication. This includes the exchange of sensitive information such as credit-card numbers between customers and e-businesses.

Could some enterprising evil genius break this system? Certainly. We do not know for sure that factoring large numbers is necessarily so difficult and time-consuming. We only know that no one has yet found a fast way to factor large numbers or created a new system to do so. Based upon the current state of knowledge in computational theory, it is still possible that a very clever graduate student in either mathematics or computer science could suddenly devise a completely new approach to factoring, one much more effective and quick than the sieve method. Recently, using almost 400 computers working simultaneously, a group was able to factor a 155-digit number in 3.7 months.

Another interesting observation was made by Peter Shor of Bell Labs. He showed that a quantum computer (a computer that harnesses the micropower of quantum mechanics) can factor numbers much faster than digital computers and thereby defeat the RSA encryption method. The catch is that no one has been able to figure out how to build a quantum computer, although people are certainly thinking about how it might be feasible.

But quantum physics might also offer a different kind of light at the end of the cryptographic tunnel: the possibility of developing a system called quantum cryptography, which, although hypothetical, does theoretically promise that grail for code-makers--an unbreakable code.

If the RSA method is defeated, there would have to be a massive effort to replace it with an alternative public key system. There are public key systems that use much more sophisticated mathematical ideas than factoring numbers. Ironically, this makes them potentially less secure. If a system is based upon complicated ideas, it is easier for weaknesses in the system to be masked by its complexity. In other words, it is more difficult to prove that a complicated method is secure than to prove that a simple method is secure. This, in fact, is why the RSA method has gained acceptance over the others and is, until that evil hacker or quantum genius arrives on the scene, one of the best keys to privacy we've got.

Back to Top