If you pay attention to this site some of you may have noticed the inclusion of a new section of the site called build-logs. It essentially covers progress notes on various projects I am working on. One major project I am working on regarding this site is setting up automated PGP signing of the posts on it. I gave a brief explanation of how PGP works in one of the posts in that section, and I feel it gives a good and clear explanation of the concept of public key cryptography to a layman. I have however, for the longest time, wanted to do an in-depth explanation of how PGP works - this is not only because there seem to be very few non-academic resources on the subject, but also to bolster my understanding of the subject. This post is just that.

Cryptography and asymmetric encryption

Encryption has existed in some form since at least the time of Ceaser. During wartime, Julius Ceaser found that he needed to get messages to his generals, without the contents being read in transit. From this necessity was born the Ceaser Cypher, one of the most simple encryption algorithms, where letters of the alphabet are offset by a certain amount. This effectively made the plaintext message “we need help” appear as “yg pggf jgnr”, and thus the science of cryptography was born. What can be noticed however is that the ceaser cypher is ludicrously weak, and can be broken by an adequately neurodivergent child with a spare ten minutes. This opened the advent of two key types of cryptography, strong a weak. This is enshrined best by the following quote

“There are two kinds of cryptography in this world: cryptography that will stop your kid sister from reading your files, and cryptography that will stop major governments from reading your files.” ~ Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C.

• From a high-level overview, the way cryptography works is a mathematical function used in the encryption and decryption process. The algorithm works in combination with a key (number, word, phrase) to encrypt the plaintext. The same plain text encrypts to different ciphertexts with different keys. Given this, the security of encrypted data is entirely dependent on two things: the strength of the algorithm, and the secrecy of the keys. Under conventional cryptography (symmetric cryptography) a single key was used for encryption and decryption e.g. the Ceaser cypher.

Symmetric encryption is not considered to be secure by modern standards. The reason behind this is that key management under the advent of conventional encryption is inherently insecure. At some point, the secret key must be sent out into the aether for the receiving part to decrypt the message. You can layer on solutions to this like diffie-helman, but this does not change the fact that anything this important that is not verifiably air-gapped needs to be assumed to be compromised. Symmetric encryption is still used however, the reason is that it is significantly faster to compute than its alternative (we will discuss that in a moment). That being, very few security-conscious persons would ever use this method of encryption for anything other than encrypting data at rest.

The downfalls of symmetric encryption are addressed by the entrance of Asymmetric Cryptography, more commonly called Public Key Cryptography. This is an encryption scheme that uses a pair of keys for encryption, one public and one private

• The public key encrypts and the private key decrypts.
• The public key is made public for the whole world to see, and the private key is kept private.

What this means is that if you want to send me a message that only I will be able to read, then you would use my publically available public key to encrypt it. I will then use my private key to decrypt it. If I want to reply, I will use your publically accessible public key to encrypt a message, and you will use your private key to decrypt it. This solves a major issue with the previously used symmetric encryption, as at no point is it required for any party to make public a key that could decrypt the message. The primary benefit of this system is that it allows people who have no preexisting security arrangement to exchange messages securely. Some examples of this system are Elgamal, RSA, Diffie-Helman, and DSA.

PGP combines some of the best features of both asymmetric and symmetric encryption - it is a hybrid ecosystem designed to provide robust security for data transmission and communication. By utilizing asymmetric encryption for key exchange, digital signatures, and securing communications, PGP ensures a secure method for sharing symmetric session keys, which are used for encrypting the actual data. This hybrid approach enhances efficiency and security, as symmetric encryption is faster and well-suited for encrypting larger volumes of data, while asymmetric encryption offers secure key exchange and authentication. PGP’s versatility and use of strong encryption algorithms like RSA or ECC, alongside compression techniques, make it a widely adopted and trusted tool for ensuring confidentiality, integrity, and authenticity in sensitive data handling and secure communication scenarios.

How PGP encryption works

When a user encrypts plaintext with PGP, it first compresses the data using a compression algorithm. While typically data compression is used to save transmission time and disk space, in this case, it also strengthens the cryptographic security. By compressing the data this hamstrings typicall code breaker techniques, where they use known patterns found in the plain text to reverse engineer the cypher. Compressing the data reduces the prevalence of these patterns reducing the attack surface. Historically the algorithm used has been the ZIP compression algorithm, which is known for its balance between its compression speed and ratio. This however can vary between different implementations of PGP, with some offering support for Zlib and BZIP2.

Once compression is complete the next step is to create a session key, which is a one-time-only secret key. Entropy is generated for random movement of your mouse and keystrokes are used to generate a number, which is in turn used as the key. This session key works with a secure and fast symmetric encryption algorithm to encrypt the compressed plaintext. Typically AES is used for this process, but in the past IDEA and CAST-128 have also been used.

Once the data is encrypted, the session key is encrypted using the recipient’s public key. Historically the asymmetric encryption used in PGP is typical RSA, however never version of PGP has been known to support ECC which offers similar security to RSA but with shorted key lengths. This public-key encrypted session key is then transmitted along with the cyphertext to the recipient. Once the recipient receives the data, they decrypt the session key and use it to decrypt the data. The combination of these two encryption methods combines the security of public key encryption with the speed of conventional encryption. It in essence solves the key problem of symetric encryption, of relying on a secure back channel to communicate secret keys.

Digital signatures and Hash Functions

One of the biggest benefits of PGP is the ability to sign data with digital signatures. Digital signatures provide a mathematically robust method of verifying data origin. It essentially acts as a digital version of a handwritten signature. For the longest time whenever I have explained how digital signatures with with PGP or GPG, I have said that the private key can encrypt the data. I then promptly after that say “That’s not exactly true, but for simplicity’s sake let’s agree it is encryption”. I’m going to explain what I mean when I say that.

In a way I am lying here, in basic public key cryptography this is in fact what happens. Assuming vanilla public key cryptography, if I wanted to sign a message with a digital signature then I would encrypt it using my private key. As only I have access to my private key, it stands to reason that I was the one who signed the message. This system has some problems, first and foremost it is slow, and second, it produces an inordinate amount of data (often double the size of the clear text). PGP addresses these issues with the inclusion of a one-way hash function, typically SHA-246, SHA-384, or SHA-512 (that being said SHA-1 used to be used, and RIPEMD-160 is sometimes used). I won’t get into the inner workings of hash functions, as I am sure if you are reading this you know what they do, however for the uninitiated a hash function essentially takes in a variable-length input and produces a fixed-length output. The hash function ensures that if the information is changed in any way, the output will be entirely different.

Firstly, PGP uses one of the previously mentioned hash functions on the plaintext data the user is signing. This compresses it down into a fixed-length string of data items, known in this context as a message digest. Following this PGP uses the digest and the private key to create the signature. The signature can then be appended to the plaintext data and sent to the recipient. The recipient can then use the public key to decrypt the signature and see if the hash plaintext matches the decrypted message digest.

Digital certificates

One issue that is not discussed as often as the sexy parts of PGP i.e. the hash functions, signatures, and encryption, is digital certificates. I think this is wrong because it is an integral part of ensuring the security, and trustworthiness of public keys. One of the biggest issues with this new ecosystem of secure communication is that users must constantly ensure they are encrypting the correct person’s key. In an environment where it is safe to just pass your key around by posting it openly online for anyone to see, MITM attacks begin to shine. Say I post a phoney key pretending to be you, if someone is unable to verify if it’s your key, then I could send data they believed was securely being sent to you with the full capability to decrypt it. This is where digital certificates come into play.

A certificate is a form of credential - examples of AFK certificates could be birth certificates or passports. These have information on them identifying you, with some authorisation stating that someone else has confirmed this information. A digital certificate functions similarly to this, only it contains information that is included with a person’s public key that helps others verify if the key is genuine. Typically they consist of three items of information

• A public key
• Certificate information (“identity” information about the user, such as name, and user ID)
• One or more digital signatures

The most important of these three things is the digital signature at the end. It states that the information on the certificate has been confirmed by some other person or entity. The signature does to vouch for the authenticity of the certificate as a whole, only that the signed identity information goes along with, or is bound to, the public key. As such a certificate is a public key, with one or two forms of ID, with a stamp of approval from another trusted individual.

Certificates are utilised when it’s necessary to exchange public keys with someone else. Within small groups of people, they are less needed, as you can pass your public keys to one another in person, however, there is a critical mass at which point it stops being practical. This necessitates the need for an infrastructure to do so, typically in the form of storage-only repos called Certificate Servers. This is essentially a database that allows users to submit and retrieve digital certificates. Typically these provide admin features that enable a collection of users to maintain its security policies i.e. only allowing a certain strength key to be stored.

Beyond this, you find a structured system that provides additional key management features called Public Key Infrastructures (PKIs’s). A PKI’s main feature is the introduction of what is known as a Certification Authority (CA), which is an entity that a group has allowed to issue certificates to its devices. A CA creates certificates and digitally signs them using the CA’s private key. Because of its role in creating certificates, the CA is the central component of a PKI. Using the CA’s public key makes it possible to verify a certificate’s authenticity at any one point.

Officially PGP recognises two certificate formats

PGP certificate format Other than the information below, one unique factor of a PGP signature is that it can contain multiple signatures. Several other people can sign it to essentially say “Yes trust this key”. This includes (but is not limited to) the following information

• PGP version number - The identifies which version of PGP was used to create the key associated with the certificate
• The certificate holder public key - The public portion of your key pair, together with the algorithm of the key (usually RSA)
• The certificate holder information - This consists of the identifying information on the user, i.e. username
• The digital signature of the certificate owner - Also called a self-signature, this is the signature using the corresponding private key of the public key associated with the certificate
• The certificate validity period - The certificate start date/time and expiration date/time; this indicates when the certificate will expire
• The preferred symmetric encryption algorithm for the key - This indicates the encryption algorithm to which the certificate owner prefers to have information encrypted

X.509 certificate format This is a very command certificate format. All X.509 certificates comply with the ITU-T X.5098 internal standard; thus these certificates can be used by any application that complies with the X.509 standard (this is only true in theory, I practise a lot of organisations have diverged from this). The certificates require someone to validate that a public key and the name of the key holder go together. The key difference between this type of cert and the PGP cert is with a PGP cert anyone can sign it, with this only a PKI CA can sign it. All X.509 certs have the following data

• The X.509 version number- This identifies which version of the X.509 standard applies. This can affect what information can be specified in the cert.
• The certificate holder public key- The public key of the certificate holder, together with an identifier which specifies which PKI the certificate belongs to
• The serial number of the certificate- The entity that created the certificate is responsible for assigning it a unique serial number to distinguish it from another certificate it issues.
• The certificate holder’s unique identifier- This name is intended to be unique across the internet. This in itself is a rabbit hole, but will typically consist of multiple subsections that come together to describe a holder’s common name, organisation unit, organisation, and country
• The certificate validity period- This specifies the certificate start date/time and expiration date/time, and is used to establish when the cert expires.
• The unique name of the certificate issuer- This is normally a CA. Using the certificate implies trusting the entity that signed this certificate
• The digital signature of the issuer- The signature using the private key of the entity that issued the cert
• The signature of the algorithm identifier- Identifies the algorithm used by the CA to sign the certificate

So how does one check the validity of a public key, for you to give it your stamp of approval? Well of course you could verify it by saying you met the person and verified it AFK, however, this is not always practical. The other way is to manually check the certificate fingerprint, which is a hash of the user certificate and appears as one of the certificate properties. In PGP, the fingerprint can appear as a hexadecimal number or a series of biometric words, which makes the identification process easier. You use this by getting in contact with the key owner, and asking him to verify his fingerprint - this is essentially similar to what Signal does with the QR codes, which allows you to verify each other’s chat. A less hands-on way however is to trust that a third individual has gone through the process of validating it, for example, a CA. The defacto system is this web of trust with various people trusting on other people’s behalf, and you use the fingerprint to confirm in cases where this is required.

Closing thoughts

PGP and asymmetric encryption are the cornerstones of secure communication, providing robust methods for encrypting and decrypting data, and ensuring confidentiality, integrity, and authenticity in digital exchanges. I feel I have made my best effort to explain the three underlying cornerstones of the ecosystem it has built. This is not to say this post is the be-all end of all of this subject - The if GPG, trust models, and the issue of how quantum computing will affect this.