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:

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\)):

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 cannot 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. Remember, by the way, that these keys are public: they can be in the hands of anyone, even attackers. So Alice and Bob don't need to worry about anyone intercepting their public keys while they are exchanging them.

Then, if Alice wants to send a message to Bob, this is what she has to do:

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

In this way, no third party would have been able to read or alter 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, from that point on, 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 an authenticated channel over which messages cannot be modified by third parties, 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", who sign keys after verifying the identities of their holders, and 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.

  1. We choose two random and distinct large prime numbers \(p\) and \(q.\) The larger, the better. With these numbers, we compute \(n = p q.\)

  2. 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 factorisation (\(n = p q\)), 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 = p q,\) we can use the well-known formula \[\varphi (n) = (p-1)(q-1). \]

  3. We choose an encryption number \(e > 1,\) which we require to be any number smaller than \(\varphi (n)\) and coprime with it. Since these numbers are abundant, we can consider random numbers smaller than \(\varphi (n)\) until we find one that is coprime with it. We should emphasise that \(e\) will be the smallest positive representative of an element of the multiplicative group of integers modulo \(\varphi (n).\)

  4. 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 \[e d \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 = p q\) and \(p \neq q,\) as before. To send a message, we must first encode it as a natural number \(m\) smaller than \(n;\) if the message is too big and cannot be encoded in a number smaller than \(n,\) we can always split the message into smaller chunks.

With our encoded message \(m\) ready, we can encrypt it into the ciphertext \[c \coloneqq m^{e} \bmod n, \] which can be decrypted with the private key \(d\) associated with the public key \((n,e).\) Indeed, if we want to retrieve the original message, we only need to compute the number \(c^{d} \bmod n,\) which, as we are about to prove, is equal to \(m.\)

Unwrapping the definitions, \(c^{d} \equiv m^{e d} \pmod{n}.\) This means that, for some natural number \(\kappa ,\) we have \(c^{d} \equiv m^{\kappa \varphi (n) + 1} \pmod{n}\) as we took \(d\) to be the multiplicative inverse of \(e\) modulo \(\varphi (n).\) Now, according to the Chinese remainder theorem, the function \begin{align*} \mathbb{Z} / \mathbb{Z}n & \longrightarrow \mathbb{Z} / \mathbb{Z}p \times \mathbb{Z} / \mathbb{Z}q \\ (x \bmod n) & \longmapsto (x \bmod p, x \bmod q) \end{align*} defines a ring isomorphism. Therefore, if we show that \[m^{\kappa \varphi (n) + 1} \equiv m \pmod{p}, \qquad m^{\kappa \varphi (n) + 1} \equiv m \pmod{q}\] we will also have proven that \[m^{\kappa \varphi (n) + 1} \equiv m \pmod{n}, \] thus showing that our decryption procedure works as expected. Since the proofs for \(p\) and \(q\) are analogous, we will only consider the case for \(p.\)

Euler's theorem states that, given any integer \(a\) coprime with another integer \(x,\) we have \[a^{\varphi (x)} \equiv 1 \pmod{x}; \] this, by the way, is a direct consequence of Lagrange's theorem for groups. Applied to our case, if \(p\) does not divide \(m,\) we know that \(m\) and \(p\) will be coprime, hence \[m^{\varphi (n)} \equiv (m^{\varphi (p)})^{\varphi (q)} \equiv 1 \pmod{p} \implies m^{\kappa \varphi (n)+1} \equiv m \pmod{p}, \] as we wanted to show. And in the unlikely case that \(p\) divides \(m,\) any power of \(m\) will be equal to \(m\) modulo \(p\) either way. A fully analogous reasoning can be applied for \(q.\)

What makes this protocol secure is that there are no known (classical) algorithms that can efficiently retrieve a message \(m\) from the ciphertext \(c\) without the private key \(d.\) If such an algorithm were discovered, the world would be in trouble.

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 a piece of 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.5.

Key generation

The first thing that you should do is generate 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
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (9) ECC (sign and encrypt) *default*
  (10) ECC (sign only)
  (14) Existing key from card
  (16) ECC and Kyber
Your selection? 1
RSA keys may be between 1024 and 4096 bits long.  
What keysize do you want? (3072) 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 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 to 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 your 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 with 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-----

which allows for the original file to be recovered with any text editor, without the need for GPG.

To clearsign a document, you only 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 gets the original document and the signature in a single file, which can be inconvenient, as it requires the receiver to extract the original document in some way. A handy 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 with 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 with a certain address, the procedure is analogous with the exception of using the --export-secret-keys flag instead of --export. You can use this to keep a backup 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 one hand, considering our current technology in terms of quantum hardware, it will still take a good long 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 to attacks with quantum computers.

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

Published
Revised

The thumbnail used for this post is in the public domain and was obtained from Wikimedia Commons. Credit for the image goes to Bich Tran.