Public-key cryptography

Public-key cryptography is a method of encryption where the sender and recipient do not need to rely on a shared secret. It is known also as "asymmetric cryptography" because the key used to encrypt is not the same as the key used to decrypt. Symmetric cryptography uses the same key for both operations, requiring that the sender and recipient of something both know the key used before they can exchange encrypted data.

Basic concepts

A large random number is generated, and used to create a public-key pair.

Anyone can encrypt using the public key, but only the holder of the private key can decrypt.

The basics of public-key cryptography are fairly simple. You start by generating a rather large random number, and then using that number as input to a key generation algorithm. This will give you a private key, and from that private key you derive a public key (the reverse is not possible - one cannot determine the private key from the public key). The private key is usually protected by encrypting it with a symmetric cypher, using a passphrase, to protect the key from direct copying and use - otherwise the unprotected key could easily be copied and any messages encrypted to that key could be decrypted by the copier.

The public key is then shared with anyone who may wish to send you encrypted messages. Due to the one-way nature of generating public keys, there is no fear that someone with your public key could create your private key and decrypt messages sent to you. Though there are some who prefer to keep their public keys private as well, only sharing them with people they trust, this creates the same problem that public-key cryptography was designed to circumvent: the parties who wish to converse must first exchange information in a secure manner.

Encryption

Armed with your public key, any person can now encrypt something to you. The encrypted data can only be decrypted by using the corresponding private key, so the security of the data is directly related to how securely the private key is kept. The public key is not actually used to encrypt the entire data stream, as it would be computationally prohibitive. Instead, a "session key" is generated, a more simple symmetric cypher is used to encrypt the data with the session key, and the asymmetric cypher is then used to encrypt the session key.

Signing

Another feature of many public-key encryption methods is the ability to digitally sign data. This is done using the private key instead of the public key, and the public key can then be used to verify the signature. Of course, unless you have verified that the public key actually belongs to the person in question, all you have verified in the signature is that a particular private key did in fact sign the data. This brings us to the next issue of public-key cryptography, namely how to verify identities.

Verification of identities

The biggest problem with public-key cryptography is the fact that it says nothing about who owns the key. For this reason, there's a few methods of ensuring identities, the most common being a public-key infrastructure (PKI) or a web-of-trust method. In both methods, the public key is signed, much like any other data would be, by the private key of someone else. This signature can then be verified by anyone else, and trusted based on the trust instilled in the signer by the verifier.

PKI

PKI works by a central authority verifying the identity of keyholders, and then signing their public key with the PKI authority's own key. Assuming you have a copy of the authority's key, you can then verify that any person is who they claim to be by the presence of that signature. A good example of this is how SSL and TLS encryption, commonly used on secure websites, is setup. You generate a certificate, and send it (and your money) to a "trusted" third party, such as Verisign. They will verify your identity, then sign your certificate and send it back to you. You can then use the signed certificate on a web server, because Verisign's signing certificate is installed by default in web browsers. You can, in fact, use a self-signed certificate (or one signed by an unknown certificate authority) and simply instruct visitors to install the unknown certificate authority's certificate into their browser. However, this defeats the purpose of any kind of PKI, since it goes back to relying on someone's word (without further verification) that their identity is correct. In some cases, this is acceptable - for example, on a company Intranet where the local signing certificate can be manually installed on desktop computers by the systems administrators, there's no need to rely on a third party certificate authority.

PKI falls apart when the certificate authority cannot be trusted - either because it is discovered to not do proper verification of identities, or their certificates have been compromised.

Web-of-trust

The verification method used by GPG, for example, is called the web-of-trust method. This works by signing keys of people whose identities you have verified completely, and then trusting (to various degrees) those people's abilities to verify others' identities. For example, if you trust Alice completely in her ability to verify someone's identity, and Alice sign's Bob's key, then you'll trust that Bob's key belongs to him simply because Alice verified it. If you trust Alice's ability less, you may require signatures of more people on Bob's key before you will trust it. Or, if you only trust your own abilities, then you will have to verify Bob's key yourself (usually in person).

To make the web-of-trust work, everyone should sign keys of people they meet - of course, after thorough verification. This way, should one of the people who signs your key be trusted by someone else (or through the web a few steps to someone they trust), that person can be relatively sure of your identity even without ever having met you. Then if you do meet and sign each other's keys, the web is strengthened even more. These key signings used to be more common, as a key signing party.

The problem with a web-of-trust model is more of a social one; namely that the trust is spread out amongst many people. If one person in the web is found to be untrustworthy, there could be other relationships which were formed (or broken) based on the trust of that person and now are not valid. However, by each user applying their own opinion of the trust abilities of persons whose keys they have signed, they can usually limit any damage from a break in the web-of-trust. Of course, once such a problem is discovered, others can distrust the person's ability entirely, and will see that reflected in the keys that person had signed.

Key signing party

One way to strengthen a web-of-trust is to hold a key signing party. There's a couple ways to do it, but they're similarly designed (and depending on scale, one method may work better than another).

1. A "host" for the party is chosen, and everyone sends their public key to the host.
2. The host generates a list of public keys (usually their fingerprint, a hash of the key which is much smaller) and publishes it to the guests.
3. The guests arrive, either bringing a key list with them or picking one up at the party, and verify the keys on the list with their owners.

   This could either be one-on-one (verifier mingles and meets the owners of the keys) or many-to-one (each person in turn gets in front of the guests, introduces themselves and shows some identification, and then verifies that the key attributed to them on the list is in fact their key).

4. As a guest verifies each identity (and verifies their identity with each key holder), they mark the key on their list.
5. Upon returning home, the guest then signs the keys on the list for people whose identity they verified.