The basics of public-key cryptography

A broad overview of public-key cryptography (with an emphasis on the RSA algorithm) and a brief tutorial on the basic usage of the GNU Privacy Guard software.

Communication can be carried out over all sorts of media: telephone lines, internet cables or the post system, just to name a few. In spite of how different all these channels can be, they share a common trait — they are insecure. In principle, nothing would prevent a sophisticated-enough attacker from intercepting information sent through any of these channels or from trying to impersonate a sender. This is a problem, but one for which we have some solutions.

In order to communicate securely over an insecure medium, two essential components are necessary:

An authenticity verification protocol enabling receiving parties to verify the origin of any messages they get. These protocols typically work by adding a digital signature to the message.
An encryption protocol. For communication over insecure channels to be private, any message must be encrypted before it is sent. If the encryption protocol is well-designed, only the intended receiver should be able to recover the original message once it has been encrypted.

Public-key cryptography offers protocols for both encryption and authenticity verification.

An overview

In public-key cryptography, each of the two communicating parties has their own pair of keys: a private key and a public key. These keys are linked in some way and, as their names suggest, public keys can be shared with anyone (attackers included!), whereas private keys are kept secret and must never be disclosed. Private keys are used to sign and decrypt messages while public keys are used to encrypt them and to verify signatures. In order to make this precise, consider a fixed key pair (with a public key \(p\) and its associated private key \(k\)):

If a message is encrypted with the public key \(p\), it can only be decrypted with the associated private key \(k\).
If a message is signed with the private key \(k\), anybody can verify that it was signed with the private key associated to the public key \(p\).

Perhaps an example will clarify how this can be used in practice.

Let's say that two people, named Alice and Bob, want to communicate with each other, but — for reasons that I will leave to your imagination — they can never meet in person and they can only communicate through insecure media. In order to secure their communications using public-key cryptography, both of them need to generate their own key pair and share their public keys with each other; it wouldn't matter if these public keys were intercepted by an attacker. Then, if Alice wants to send a message to Bob, this is what she has to do:

Sign the message using her private key.
Encrypt the message using Bob's public key.

Lastly, once Bob has received the encrypted message, he needs to:

Decrypt it using his private key.
Verify the signature using Alice's public key to check that the message has not been altered.

In this way, no third party would have been able to intercept the message. The best that an attacker could have done is intercepting the encrypted message, but there is no way of retrieving the original message from it without the recipient's (Bob's) private key. Analogously, Bob can rest assured that the message he received came from Alice, for he can use Alice's public key to verify that the message was signed using her private key (which only she has).

Nevertheless, there is still a potential vulnerability in this example. When Alice and Bob shared their public keys, there could have been a man in the middle that replaced their keys with his own public key, and, since that point, he could have been relaying all communication between Alice and Bob through him, intercepting the messages and perhaps altering them. At some point, you do need a secure channel, but, at least, once you have managed to exchange your public keys securely, you never need it again. Over the internet, this is sorted out using "Certification Authorities", whose public keys come pre-installed with your internet software.

The RSA algorithm. Prime numbers save the world

The idea behind public-key cryptography sounds interesting, but you may be wondering how it can possibly work. We will now explore one of the industry-standard implementations of public-key cryptography: the RSA algorithm (named after Rivest, Shamir and Adleman). You might want to have your arithmetic and algebra notes at hand.

Key generation

In order to use the algorithm, we first need to generate a pair of keys (a public key and a private key). The procedure for doing so is the following.

We choose two random very large prime numbers \(p\) and \(q\). The larger, the better. With these numbers, we compute \(n = pq\).
We now compute \(\varphi(n)\), where \(\varphi\) is Euler's totient function. If we had been given \(n\) and we didn't know its prime factorization (\(n = pq\)), it would be unfeasible –– at least using today's technology –– to compute \(\varphi(n)\) for a sufficiently large \(n\). That is the essence of this algorithm. Nonetheless, as we know that \(n = pq\), we can use the well-known formula \[ \varphi(n) = (p-1)(q-1).\]
We choose an encryption number \(e\). This will be any natural number smaller than \(\varphi(n)\) and coprime with it. In other words, it will be the smallest positive representative of any element of the multiplicative group of integers modulo \(\varphi(n)\).
Finally, we compute the decryption number \(d\), which will be the multiplicative inverse of \(e\) modulo \(\varphi(n)\); we shall take it to be the smallest natural \(d\) such that \[ ed \equiv 1 \pmod{\varphi(n)}.\] Euclid's algorithm gives us an efficient way of computing this number.

The public key of the pair will be \((n, e)\) and the private key will be \(d\). The numbers \(p\), \(q\) and \(\varphi(n)\) must be kept secret or destroyed, because, as we have seen, they easily lead to the private key.

Encryption and decryption

Let us assume that the intended recipient of a message has a public key \((n,e)\), with \(n = pq\) as before. After codifying our message as a natural number \(m\) smaller than \(n,\) the encrypted message will be \[ c \coloneqq m^e \bmod n.\] This encrypted message can only be decrypted with the private key \(d\) associated to the public key \((n,e)\). The decryption process would simply involve computing \[ c^d = m^{ed} = m^{\kappa\phi(n) + 1} \equiv m \pmod{n}.\] Notice that we have applied Euler's theorem, which states that, given any integer \(a\) coprime with another integer \(x\), we have \[ a^{\varphi(x)} \equiv 1 \pmod{x}.\] The theorem is a direct consequence of Lagrange's theorem for groups.

If you look closely, you will realise that there are only two particular situations in which this method can fail: when \(m = p\) and when \(m = q\). In these two scenarios, Euler's theorem doesn't guarantee that \[ m^{\phi(n) + 1} \equiv m \pmod{n}.\] However, this is not a problem, because these corner cases are immensely unlikely. Just to give you an idea of how unlikely they are, consider that, in real-world applications, \(n = pq\) will have hundreds of decimal digits. For context, the number of atoms in the observable universe is estimated to have less than eighty decimal digits.

Signing and verification

Now that we know how to encrypt and decrypt messages, let's discuss how to sign them and how to verify signatures. This involves no new mathematical machinery. Assume that, as before, we have a message \(m\). Its signature with the private key \(d\) will be \(s \coloneqq m^d \bmod n\). Then, in order to verify the signature against a public key \((n,e)\), it suffices to check whether \(s^e \bmod n = m\) holds.

On a side note, we should remark that there is no need to sign the whole message. A hash of the message can be used instead.

Using GNU Privacy Guard (GPG)

The GNU Privacy Guard is an open-source cryptographic software that implements public-key protocols. If you use a Linux distribution, it probably came pre-installed with it. If you use macOS, you can get the latest version through Homebrew. I will assume that you have already installed it and that you are running version 2.4.

Key generation

The first thing that you should do is generating a key pair so that you can sign messages and receive encrypted messages. This is done with the following command:

gpg --full-generate-key

Right after executing it, you will be asked to choose an encryption and signing algorithm (I will pick RSA for both). Then, you will have to specify a key size. A longer key is more secure, so I will ask for a key of 4096 bits, the largest size available.

Please select what kind of key you want: (1) RSA and RSA (default) (2) DSA and Elgamal (3) DSA (sign only) (4) RSA (sign only) (14) Existing key from card Your selection? 1 RSA keys may be between 1024 and 4096 bits long. What keysize do you want? (2048) 4096 Requested keysize is 4096 bits

Your private key may, at some point, be compromised. Somebody may steal it or you may simply lose it. That's why it is a good idea to set an expiration date for the key. This way, if someone uses it after the expiration date, a message will pop up letting them know that the key has expired and is no longer safe to use. Now, GPG will ask you for how long you want your key to be valid. I will set it to one year.

Please specify how long the key should be valid. 0 = key does not expire <n> = key expires in n days <n>w = key expires in n weeks <n>m = key expires in n months <n>y = key expires in n years Key is valid for? (0) 1y

After this step, you will be asked to provide your real name and email address. These will be used to identify your key pair and will be visible to anyone in possession of your public key. Lastly, you will have to provide a passphrase for your key. This passphrase will be necessary to sign and decrypt any messages, and it is meant to serve as an additional layer of protection should your private key ever be stolen, so it's wise choose a strong password.

In this process, you have been able to specify exactly what kind of key pair you wanted to generate. Alternatively, you can use the instruction gpg --generate-key if you'd rather just use the default settings.

Running gpg --list-keys will show you a list of all the public keys gpg knows of. The command gpg --list-secret-keys will display the list of known private keys. If you've done everything correctly, these commands should list you newly generated public and private keys.

Encryption and decryption

We will now discuss how to encrypt a file in order to send it to someone (let him be Bob). Firstly, you need to obtain Bob's public key. You could ask him for it directly or look it up on his website or on a public key server (such as keys.openpgp.org). Once you have downloaded the key and stored it as, for instance, bobkey.gpg, you can import it using gpg --import bobkey.gpg. If you can't find yourself a Bob with a public key, you can use my own public key for this example. If you run gpg --list-keys, you should be able to see your newly imported key: it will be identified with the name and email that Bob, its owner, provided in the key generation process.

Now you are ready to encrypt your first file. Let it be, for example, cute-cat.jpeg. The command that you need to run to encrypt it is the following:

gpg --output encrypted-cat.gpg --encrypt --recipient bob@example.org cute-cat.jpeg

This will generate a file called encrypted-cat.gpg that will be the result of encrypting cute-cat.jpeg with Bob's key. Keep in mind that the argument of the --recipient flag, which I have set as bob@example.org, should be replaced by the name or email address associated to the public key to be used in the encryption process.

That's it for encryption. Now how can you decrypt a file for which you have a private key? If, as in our previous example, the file is encrypted-cat.gpg, you just need to run this command:

gpg --output decrypted-cat.jpeg --decrypt encrypted-cat.gpg

If you have the appropriate private key loaded into GPG, this will generate the decrypted file decrypted-cat.jpeg. It doesn't matter if you have many private keys loaded; GPG will find the right one.

Signing and verification

There are three ways to sign files. The first of them generates a "signed file" which can be used to verify the signature and to retrieve the original file. To sign a file this way, use this command:

gpg --output signed-cat.sig --sign cute-cat.jpeg

Of course, signed-cat.sig is the name of the output file and cute-cat.jpeg that of the file that needs to be signed. The signature can be verified and the original file can be recovered with the following command:

gpg --output cute-cat.jpeg --decrypt signed-cat.sig

If you just want to verify the signature but are not interested in retrieving the original file, you can run this instruction:

gpg --verify signed-cat.sig

There is no need to specify which user signed the file: GPG will try all the public keys it has imported and will find the right one.

This signing method has one major inconvenience, which is that, in order to retrieve the original file, there is no option but to use a GPG command. A solution to this problem is to use a clearsign signature. This will produce a file output of the form

-----BEGIN PGP SIGNED MESSAGE----- < ORIGINAL FILE > -----BEGIN PGP SIGNATURE----- < SIGNATURE > -----END PGP SIGNATURE-----

To clearsign a document, you need to use the flag --clearsign instead of --sign. The signature verification process doesn't change.

There is one last signing method. In the two approaches we have considered, the receiver always needs to perform some operation to retrieve the original file. A useful alternative is to store signatures as detached signatures. These signatures are fully separate files, which do not contain the original file and should instead be sent along with it. Detached signatures can be generated using the --detach-sign flag. Given any file cute-cat.jpeg and a detached signature signature.sig presumably signing the file, the signature verification can be carried out with the following command:

gpg --verify signature.sig cute-cat.jpeg

Key management

If you want to export to a file pubkey.gpg a public key associated to a particular email email@example.com, you may do so with this command:

gpg --output pubkey.gpg --export email@example.com

If you want the export to be in human-readable ASCII, you can use the flag --armour:

gpg --output pubkey.gpg --armour --export email@example.com

Not providing an output will lead to the key's being printed to standard output. If you want to export a secret key associated to a certain address, the procedure is analogous with the exception of using the --export-secret-key flag instead of --export-key. You can use this to keep a back-up of your key pair on an external drive.

What else?

There is so much more to public-key cryptography than what we have been able to cover in this post.

If you want to have a deeper look at the RSA algorithm, you can read this paper. Of course, Wikipedia is also your friend.

If you want to learn more about the use of GPG, you should check out its wonderful documentation. Some things that we haven't covered about GPG and that you can read about on your own are

There are plenty of other public-key protocols that are worth having a look at. A notable example is the Diffie–Hellman key exchange protocol.

In addition to this, you may also wish to learn a little bit about symmetric-key cryptography, which is often used in conjunction with public-key cryptography for reasons of efficiency. Since public-key algorithms can be computationally costly, they tend to only be used to exchange keys that are then employed by (more efficient) symmetric-key protocols.

Oh! And what's up with those quantum things?

Of course, you may have heard about quantum computing and how it endangers the safety of some of our cryptographic protocols. While symmetric cryptography would be somewhat immune to quantum computing, most of our current public-key protocols could be easily broken by a powerful-enough quantum computer. And, yes, that includes our beloved RSA algorithm.

In general, public-key cryptography is built on the assumption that a specific problem is too hard to be solved; in the case of the RSA algorithm, that problem is the factorisation of a large enough natural number. As it turns out, quantum computers can — in theory — efficiently solve quite a few of these problems on which we have built our public-key protocols.

Thankfully, there is no reason to panic just yet. On the hand, considering our current technology in terms of quantum hardware, it will still take a long good while for quantum computers to break any cryptographic protocol. On the other hand, right now, there is a massive ongoing effort to transition to "quantum-safe" cryptography (also known as "post-quantum cryptography"). Actually, we already have some public-key protocols that should be resistant against attacks with quantum computers.

As you are reading these lines, quantum-safe cryptographic protocols are being developed, standardised and even implemented. You can have a look at the NIST post-quantum cryptography initiative for more information.