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 necessarily hiding that the conversation is taking place. Technically speaking, this setting forms a secure channel. If you don't have control or can't even estimate the number of people who might be privy to a conversation, this conversation uses an insecure channel.

People learn early in life how to establish a secure channel, for example, by whispering or changing the location. Both methods, however, are difficult to achieve on the internet. Apart from edge cases, the internet consists only of insecure channels - security was not part of the design criteria when the internet was first conceptualized. Consequently, a secure channel over the internet has to be built on top of insecure channels. 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 transformation that renders a message unreadable (encryption), and a receiver can reverse the process to recover the original message (decryption). Naïve schemes use methods like changing the alphabet and reordering the sequence of characters. Stronger schemes use an algorithm and a secret key to achieve the same result. The algorithm itself is not secret. Certainly, keeping the algorithm secret makes an attack harder, but comes with drawbacks. Current algorithms are public and thoroughly scrutinized; their publication does not help an attacker.

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

Symmetric encryption

As its name suggests, symmetric encryption uses the same secret key for both encryption and decryption. Decryption is simply done by repeating the steps of the encryption in reverse order, undoing what encryption did to the original text. The constraints for designing an algorithm for symmetric encryption are usually not dependent on the capabilities of CPUs, which means that contemporary algorithms are optimized for performance—symmetric encryption is fast.

Symmetric encryption is, however, not well suited for establishing a secure channel. This is not due to weak algorithms, but the simple fact that sender and receiver, and nobody else, must have the same secret key. This implies that for the exchange of that key, a secure channel is needed—a chicken-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, but its design criteria are radically different from those of 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 to get a single result, but it's hard (effectively impossible or at least impractical) to reverse this operation, finding those same prime factors if you only have the resulting number. Thus, decryption cannot be performed as it would be with symmetric encryption - reversing the encryption steps would be too 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. There must be a mathematical relationship between the key used for encryption and the one used for decryption, so keys for asymmetric encryption are constructed in pairs. These keys are interchangeable – whichever key you used for encryption, you need the other one of the pair for decryption.

For a complete cycle — cleartext -> encrypted text -> cleartext — both keys are needed. Knowing only one of them is not enough, so it doesn't compromise the security of this mechanism if one of them is exposed. 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 cleartext -> encrypted text step. Anyone in possession of the counterpart key can complete the cycle: encrypted text -> cleartext. So you'd 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.

In practical terms, asymmetric encryption is very slow, so it's not suitable for high-throughput, low-latency protocols that are commonly needed for web protocols, but it's very well suited to encrypting small things like symmetric keys.

Hybrid encryption

Just like TLS and SSH, OpenPGP uses symmetric and asymmetric encryption together, combining the speed of symmetric encryption with the key distribution capabilities of asymmetric encryption.

A message is first symmetrically encrypted, using a random, unique key, which then is asymmetrically encrypted using each receiver's public key, and appended to the message. A receiver has to identify the right key, asymmetrically decrypt it using their own private key, and use it to symmetrically decrypt the message. Besides speed, this scheme has the advantage that each additional receiver only adds a 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 they 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, effectively exactly the same process as encryption, but with the keys swapped. 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 really is private, this is a robust proof of authenticity.

Signatures also provide an assurance that the message has not been altered since the creation of the signature. Otherwise, the message would have a checksum that differs from the encrypted one in the signature. To modify the message and adjust the checksum within the signature, the private key would be needed to re-sign the message.

Beyond messages, signatures are also used to allow the verification of the authenticity and integrity of downloaded files. The mechanism is the same.

While it does guarantee authenticity and integrity, a signature does not guarantee that a signed file doesn't contain malicious content or is free of bugs or is even fit for a specific purpose.

As signatures can be created by anyone, it's vital to verify that it was created by the right private key, and not one belonging to an impostor. How to do this is explained in the chapter on Authenticating certificates.