Public-key Encryption

09/07/05

A solution to the key distribution problem can be found in public key, or two-key, encryption. Public-key encryption is a form which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically.

In public key encryption, the private key is generally kept secret, while the public key may be widely distributed. In a sense, one key "locks" a lock; while the other is required to unlock it. It should not be possible to deduce the private key of a pair given the public key.

Typically, public-key techniques are much more computationally intensive than purely symmetric algorithms, but the judicious use of these techniques enables a wide variety of applications.

The fact that anyone can use a single "locking" key to encrypt a message which they are confident can still only be read by a single authorized user means that the number of keys required can be greatly reduced. For example, in the 1000 member system above the number of keys necessary could be reduced from 499,500 to 2000 (1000 public and 1000 private keys).

An individual, Adam, could distribute his public key to two other individuals, Brad and Charles. Brad could then send a message to Adam by encrypting it with the public key. When Adam receives the message he could then decrypt and read the message using his private key. Supposing Charles was a nosy individual then he might attempt to spy on the communications between Brad and Adam, however, because he only possesses the encrypting key, he can not decrypt the message.

There is a problem with this solution however. In this example, although Charles can not read or alter a message sent to Adam by Brad, he could easily fake a message because Charles has the same public key as Brad. Therefore, with a public key system the ability to authenticate messages has been given up in return for privacy. In many cases this will not be a problem, however there are times when it will be so.

There is an alternative to this method. Brad could send Adam and Charles his private (unlocking) key and keep the public key secret. Brad could then encrypt messages with his public key and send them to either Adam or Charles. This system has the advantage that the person receiving the message knows that it must have come from Brad; however, both Adam and Charles can now decrypt the message. In this example secrecy has been sacrificed in order to maintain an ability to authenticate the message.

This is a problem with the public key system which can only be solved by increasing the number of keys in the system. It can be solved however, by combining the two methods outlined above. If each user had two sets of public and private keys and distributed one key from each set then the capability to authenticate messages and to keep them secret would be maintained.

For example, another three individuals Paul, David and Wade are using this system. Each user holds, in addition to their normal private (unlocking) key and everyone else’s public keys, a public key which is paired with a private key which they then distribute. Paul could then encrypt a message with his own public key, thus authenticating it, and then encrypt it with the public key of whoever the message was intended for (thus ensuring secrecy).

Under this system each message is encrypted twice, once in a way which only the intended receiver can decrypt it, and once in which only the authentic sender could have encrypted it. Even though the number of keys required has been increased it still does not approach the number of keys which would be required for a single-key system of the same size.

This site was last updated 09/07/05