Data can be protected by "coding" or encrypting it. When it has been well encrypted, only the encryptor/encoder (the person sending the message) and the decryptor/decoder (the person receiving the message) can understand it.

Let us examine an example of encryption:

    HAL: vgzs hr sgd bncd

One simple encryption algorithm is to change each of the letters in the message to the letter before it. So all Bs become As, Cs become Bs, Zs become Ys and As become Zs, and so on. Using this technique, the above line is the encrypted form of:

    IBM: what is the code

(You may remember that the computer in the move 2001: A Space Odyssey is named HAL.)

The encoder encodes the message by taking the original and applying the above algorithm.. The decoder, however, has to apply the reverse algorithm to decode the message.

This algorithm is clearly not a very impressive encryption mechanism, and message can easily be decrypted. Even worse, the longer the message the easier it is to decode, since the message will have a greater frequency of examples which can be analysed. A better encryption mechanism is obviously needed.

Most popular encryption algorithms use a key. The message plus the key yields the encoded message. On decryption, either the original or a related key is needed to decode the message. An example might be an 8-bit binary key and the following algorithm.

Segment the message into 8 bit sections, if the
matching bit in the key is 1, flip the bit.

For example: if the key were 11001010, and the input was the message "Hi", the algorithm would

Decryption is the reverse of this process. Of course a different key would yield a different encoding.

This is called private, or symmetric, key encoding. Symmetric key methods can be very effective, but require both the encoder and the decoder to share a key.

This requirement to share a key can, however, be a problem. Consider a customer making a secure purchase over the Internet: how do the customer and online store share a key? If the key is transmitted between the customer and store unencrypted, someone can intercept the key and, hence, decrypt any of the subsequent communications between the customer and store.

Transmitting keys between the encoder and decoder is a crucial problem that has to be overcome. One solution is to use two keys: one key for encryption, and another for decryption. Since the two keys are separate, the encryption key can be made publicly available (and is known as the public key). As long as the decryption key is kept private (it is called the private key), anyone can encrypt information that only the person who holds the private key can decrypt.

This is a common solution to key sharing, and such encryption techniques are known as public key systems.

A well known algorithm of this type is PGP (Pretty Good Privacy). This public key encryption system was originally written by Phil Zimmermann in 1991. PGP is the de facto standard for email encryption today with millions of users world-wide.

A public key algorithm works as follows: The person wanting to receive encrypted messages generates two keys, a public key and a private key. They do not share the private key with anyone, while at the same time they distribute the public key to whomever wants a copy (there are various ways to distribute public keys, including websites specifically meant for their distribution).

When someone wishes to send an encrypted message, they encrypt it using the public key. The receiver can then decrypt the message with their private key.

Note that there are two separate keys. The public key can encrypt a message but cannot decrypt it.

This takes advantage of uninvertible functions.

Addition is an invertible function. For example, if the number three has been added to an arbitrary number, the addition operation can be inverted by subtracting three.

Modulus (the remainder after whole number division) is an example of an uninvertible function. For instance, 403 modulus 2 gives the value 1 (i.e., 403 / 2 = 201 remainder 1). However, no proper inverse of the modulus operator exists — given the values 403 and 1, there is no way to determine that 2 was used in the modulus. To see this, consider that 403 modulus 3 and 403 modulus 6 all give the same value as 403 modulus 2. In other words, given the knowledge that 403 and 1 were obtained by using modulus, there is no way to know which third number was used in the operation.

A public key encryption algorithm takes advantage of uninvertible functions to ensure that the public key cannot be used to discover the initial message.

Encryption algorithms are a complex field of study, and algorithms need to be shown to be very difficult to break. PGP has been shown to be very difficult to break. For all practical purposes, without the appropriate private key, you will not be able to decrypt a message.

The best mechanism is to work through all the possible private keys in an attempt to find the one key that can decrypt the message. If the length of the private key is 20 bits, then there are 2²⁰ (close to one million) possible keys that need to be tested. Using 30 bits there are roughly a billion keys, 40 bits gives a trillion, 50 bits a quadrillion, and on. Clearly, it takes significant resources, both in terms of time and computational power, to try all possible keys. Even the CIA (Criminal Investigation Agency) in the USA has difficulty breaking messages like this.

Thus, public key encryption makes communication over the Internet quite secure.

Imagine a commercial Webeb site that wants to obtain a customer's credit card details. While the customer is willing to share the information, neither the website or the client trust the security of information on the Internet.

Security can be provided via public key encryption as follows:

The remaining problem is to confirm that the received message is from the source it claims to be from. This covers the authentication and non-repudiation requirements for security.

What is needed is a signature that only the sender can send. This is achieved by reversing the public key algorithm that has been described above: encrypt a message using the private key and decrypt it using the public key. Any message that can be decrypted using the public key could only have been produced by the person who holds the private key. As long as the private key has not been shared with anyone, this allows for a form of authentication.

There is, however, a fault with this approach. Consider the example of someone impersonating the President of the USA over the Internet. While the President may have a digital signature of their own, someone could create another digital signature and send the appropriate public key out over the Internet. The digital signature could then be decrypted using this public key, leading to people thinking that the person is the one who created the public key (which they are), and that as the sender of the message they are also the President of the USA (which they are not).

The solution is to place public keys in a safe place, where the identity of the key's creator has been validated.