A complete specification of the use of public/private keys for communication is given in the OpenPGP protocol. The protocol is based on PGP, a program created by Phil Zimmermann in 1991. It implemented the RSA public-key algorithm. RSA was invented by three MIT researchers (Ron Rivest, Adi Shamir and Leonard Adleman, hence the name). The algorithm works by choosing big random two prime numbers and transforming them so that messages encrypted with the one can get decrypted by the other. Messages encrypted with one key cannot be decrypted with the same key, however. The MIT patented the algorithm, which made the existence of PGP somewhat unclear throughout it's history. Because Zimmermann felt that secure communication should be accessible for anyone, no matter the fate of the PGP application, he ordered the creation of a standardisation of the protocol, which eventually became OpenPGP. Today, more applications support the protocol, like the free and open software package GNU Privacy Guard, or GnuPG for short.
Even though we said earlier that by encrypting a message with the private key, an individual can show he wrote the text since it is decryptable with his public key, this is not done in practice. Since the authenticity of a message is not always necessary, being only able to read the message by decrypting it first is undesirable. To facilitate this, OpenPGP (and most other public key systems) use hashing functions.
Hashing functions generate a unique shot bit sequence from a larger amount of data. They do this by using some form of chaotic function, so that each added bit gives a completely different hash. The hashing function has the property that though the hash can be easily calculated from the plain text, creating a specific hash from (previously supplied) data is mathematically very implausible (called one-way transformation). This is useful in encryption, since when giving a hash and matching plain text, it is very unlikely the hash was generated by anything else than the plain text. Then, rather than encrypting the complete plain text with the secret key, only encrypting a hash of the plain text is enough to prove to other users that the owner of the private key wrote (or at least, is responsible for) the plain text. This encrypted hash is called a signature, and is attached to most encrypted messages to show to the recipient that the encrypted message was in fact sent from the user.
The basic OpenPGP protocol is actually pretty simple. Each user creates a public/private key pair, of which the public key is sent to a keyserver, thus making it available for everyone. Next to the public key, more information can be sent along, usually in the way of signatures. Signatures are short messages carrying some meaning in the protocol, that are signed with the private key of the owner of the keypair. Examples of signatures can be "I trust this user", "I grant this user the permission to revoke my key", and "This user identity is no longer used". Since these signatures are signed by the key owner, anyone can verify the owner of the key actually wanted to say that message, and thus they can be distributed publicly. Using this mechanism, a whole user profile of the person is created. People having access to this profile can thus choose a correct communication address, the correct encryption key and can determine some level of trust based on the signatures.
The RSA algorithm used is rather slow; the decryption or encryption of a full message can take a relatively long time. In order to speed up the process, OpenPGP does not use the public key algorithm for the encryption of a complete message. Rather, only a shared secret is encrypted using RSA. The shared secret can then be used to decrypt the symmetrically encrypted (using a password) message payload, which should be a lot faster.
We created a short example to demonstrate the OpenPGP protocol. The applet can be viewed in a pop-up by clicking on the image: