Public key cryptography

Encryption

Every now and then you might want to have a private word with someone. Private in the sense that you can control who is following the conversation, excluding unwanted listeners, but not necessary hiding that the conversation is taking place. Technically speaking, this setting composes a secure channel. If you don't have control or cannot even estimate the number of people which can follow a conversation, this conversation uses an insecure channel.

People learn early in life how the establish a secure channel - for instance by whispering or changing the location. Both methods however are difficult to achieve in the internet. Apart from edge cases, the internet consists only of insecure channels - security was no design criteria, when the internet was first conceptualized. A secure channel over the internet has to be build on top of insecure channel(s). This can be done by using a "language", which can only be understood by the intended participants. This - in its broadest sense - is encryption.

Technically it's not exactly a new language which is used, but a new notation. The usual schemes contain methods like changing the alphabet and reordering the sequence of characters. Concrete schemes use an algorithm and a secret key to specify this notation. The algorithm itself is not secret. Certainly, keeping the algorithm secret makes an attack harder, but comes with drawbacks. Current algorithms are thoroughly scrutinized, so that their publication does not help an attacker.

Probably the biggest advantage with publicly available algorithms is that it can be reused for different secure channels, as its protective character lies completely within the secret key. Choosing a new secret gives you a new channel without sacrificing the protection of either the new channel or already existing ones.

Symmetric encryption

Symmetric encryption uses the same secret key for encryption and decryption, decryption is simply done by repeating the steps of the encryption, but in reverse order - undoing what encryption did to the original text. The constrictions for designing an algorithm for symmetric encryption are usually not imposed by capabilities of CPUs, which means that contemporary algorithms are optimized for performance - symmetric encryption is fast.

Symmetric encryption however is not well suited for establishing a secure channel. This is not due to weak algorithms, but merely the fact that sender and receiver have to have the same secret key - and nobody else. This implies that for the exchange of that key a secure channel is needed - a hen and egg problem.

Symmetric encryption is used where either a secret does not need to be shared (hard disk encryption, for instance), or where other effective ways exist for the exchange.

Asymmetric encryption

Asymmetric encryption solves the key distribution problem. Its design criteria however are radically different from symmetric encryption.

Asymmetric encryption uses mathematical functions, where the inverse of that function is infeasible to calculate in any meaningful time frame. As an example: it's easy to multiply two prime numbers, but it's hard to reverse this operation, finding the prime factors, if you only have the resulting number. Thus decryption cannot be achieved as it would be with symmetric encryption - reversing the encryption steps would be to costly, even if you know the key.

Instead, asymmetric encryption uses functions which allow for a trapdoor, a way to calculate the inverse of that function by different means. This is done by not reversing encryption, but by encrypting a second time - with a different key. Obviously there has to be a mathematical relationship between the key used for encryption and the one used for decryption. In fact, keys for asymmetric encryption are constructed as pairs. And: they are interchangeable - no matter which key you used for encryption, you need the other one of the pair to decrypt.

For a complete cycle - clear text -> encrypted text -> clear text - both keys are necessary. Knowing only one of them is not enough, so it doesn't compromise the security of this mechanism if one of them is publicly known. This is probably the most difficult part of asymmetric encryption to understand and rely on.

Given that one key of the pair is publicly known, it can be used for the clear text -> encrypted text step. Anyone who is in possession of the other key of the pair can complete the cycle: encrypted text -> clear text. So you better keep that key private.

In OpenPGP, the pair (both keys) is included in the "key", whereas the public part of the pair goes into the "certificate". The certificate can then be disseminated.

Hybrid encryption

OpenPGP uses both, symmetric and asymmetric encryption. It combines the speed of symmetric encryption, using the key distribution capabilities of asymmetric encryption.

A message is first symmetrically encrypted, using a random, unique key, which then is asymmetrically encrypted for each receiver of the message and appended to it. A receiver has to identify the right key, asymmetrically decrypt it and use it to symmetrically decrypt the message. Besides speed, this scheme has the advantage that each additional receiver only adds little to the resulting size of the encrypted message.

Signatures

Signatures are used to signify authenticity. The alleged creator of a message adds something to that message which only she can create, but everyone else can verify. This is done by encrypting the checksum of the message with the private part of the key pair. Since the public part of the pair is - well - public, anyone can decrypt that checksum and see if it is indeed the checksum of the message. Assuming the private key to really be private, this is a proof of authenticity.