Mathematical explaination of file encryption for multiple persons with multiple keys

Question

Let's say I want to encrypt a document which only can be read by John, Mike, and Dave. This can easily done with PGP/GPG:

1. Import John‘s, Mike‘s, and Dave's public key
2. Encrypt the document using those keys, and send it to them
3. Each of them can decrypt the document using their own private keys.

What I don't understand is the math behind this. How to encrypt data using more than 1 keys? When I studied cryptography at the campus, I learnt the basics of RSA, but only limited to someone encrypting a document for me using my public key, then decrypt it using my private key. Never tried doing this for multiple persons.

Answer 1

What PGP (like pretty much any software that can do bulk data encryption with public keys) does is hybrid encryption. Basically, it generates a random key for a symmetric cipher (e.g. AES), encrypts the file with that randomly generated key, and then encrypts the random key with the recipient's public key and attaches it to the encrypted file. When decrypting, it first uses the recipient's private key to decrypt the encrypted symmetric key attached to the file, and then uses that symmetric key to decrypt the actual content of the file.

Wikipedia's article on PGP has a nice diagram illustrating this process:

^{Diagram from Wikimedia Commons, by "xaedes & jfreax & Acdx"; used under the CC By-SA 3.0 license.}

One of the main reasons why hybrid encryption is so widely used is that symmetric ciphers like AES tend to be much (as in, hundreds or thousands of times) faster than asymmetric ciphers like RSA in encrypting large amounts of data. But it also has a number of other convenient features — including, notably, that it's very easy to extend the process to allow for multiple recipients, simply by making multiple copies of the random symmetric key, encrypting each one with a different recipient's public key, and attaching all of these encrypted keys to the message. The recipient then just needs to locate the correct encrypted key (e.g. based on attached metadata, or even just by trying them all until they find one that decrypts into something sensible and consistent), decrypt it and then proceed to decrypt the data with it.

Answer 2

If you know how it works between two parties then you can just scale it up to multiple recipients. The important thing here is that you have to encrypt messages individually.

There are of course multiple possibilities of how to achieve this, here are two simplified examples:

Asymmetric encryption

1. Import John‘s, Mike‘s and Dave‘s public key
2. Encrypt the message with their public key individually (don‘t encrypt a message twice)
3. Send the encrypted messages to the recipients
4. The recipients (John, Mike & Dave) can decrypt the message by using their own private key

Symmetric encryption

1. Create a symmetric key, i.e. for AES
2. Encrypt the message with this key
3. Send the encrypted message to the recepients
4. Encrypt the symmetric key with the recipients‘ public keys individually
5. Send the encrypted key to the recipients
6. The recipients can decrypt the symmetric key by using their own private key
7. The recipients can now decrypt the message with the symmetric key