Using public key cryptography with multiple recipients

Question

I have a message that I want to send to multiple recipients.

Can I encrypt the message separately with each of the recipient's public keys, then send the message thus encrypted to the respective recipient?

If an attacker obtains all the encrypted messages and knows that all of them have the same content but are encrypted with different keys, would that make the attack easier?

How about if the attacker manages to decrypt one of the messages, or obtains the plaintext by other means, would that compromise any of the other private keys?

Is there a form of asymmetric encryption that would work better than others in this scenario?

Answer 1

You did not specify the details of your method to analyze, however, the usual method is not purely based on the encryption with public-key cryptography, rather a hybrid cryptosystem, where the symmetric key is transferred with the public key cryptography and the key is used in the symmetric key cryptography.

With RSA

Let's say we want to send the message $m$ to $n$ parties each have $pub_i$ and $prv_i$ keys (use RSA with OAEP).

Now, generate a uniform random AES256 key $k$ and encrypt the message with AES-GCM,

$$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$

Now encrypt the $k$ for each person $$\bar k = \operatorname{RSA-OAEP-Enc}(pub_i,k)$$ and send each user $(\bar k, c, IV, tag)$. Now each user can individually get the key $k$ and decrypt the message.

The weakness is that an observer can see that you have sent the same message to all. To mitigate this, if necessary, use a different IVs per user. Note that this will increase the encryption time.

Other candidates

RSA-KEM

The above was direct usage of the RSA. Normally one can go for RSA-KEM (in short below, full detail here)

• Generate a random $r \in [1,n-1]$ and use HKDF to derive a key.
• Encrypt the message with AES-GCM by using the derived key
• send the $r$ with textbook-RSA together with the $(c,tag)$

NaCL

NaCl has existing solutions for this; the authenticated encryption

Integrated Encryption Scheme (IES)

Integrated Encryption Scheme (IES) has multiplicative and an elliptic curve version, too.

In the Elliptic curve version ECIES, first, there are agreements on

• the elliptic curve parameters $(q,n,b,G,n,h)$
• Key Derivation Function (KDF)
• Message authentication code like HMAC-SHA256 ( or directly use AES-GCM or ChaCha20-Poly1305)
• each user has $x_i$ as private key and the public key $P_i = [x_i]G$

Then the message can be sent as

1. The sender generates a random integer $r \in [1,n-1]$ and set $R = [r]G$

2. Let $P=(x(P),y(P)) = [r]P_i$ and make sure that $P \neq \mathcal{O}$

3. Let $S = x(P)$

4. Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$

5. Encrypt with AES-GCM or ChaCha20Poly1305.

   $$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$

6. Send $(R,c,IV,tag)$

On the decryption side

1. Calculate $P = [x_i]R$ due to $$P = [x_i]R=[x_i r]G =[r x_i] G = [r]P_i $$ as prepared
2. Let $S = x(P)$
3. Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$
4. Decrypt $$(m,\perp) = \operatorname{AES-GCM-Dec}(k,IV,c,tag)$$Never accept an incorrect tag, halt $(\perp)$?
   
   

WhatsApp

WhatsApp uses a similar idea.

---

Note: If possible, I would go for the NaCL

Answer 2

Is there a form of asymmetric encryption that would work better than others in this scenario?

Plain old GPG already supports this capability.

You can add as many --recipient name parameters as you like. It works similarly to the method described by kelalaka only it's built-in to GPG already.

Answer 3

I have a message that I want to send to multiple recipients.

Fine

Can I encrypt the message separately with each of the recipient's public keys,

Actually, when we talk about encrypting a message using their public key, it's a simplification and we use mixed cryptography. The message is encrypted using a symmetric algorithm (such as AES) with a random key, and then that key is the one strictly encrypted with the public key.

then send the message thus encrypted to the respective recipient?

Yes. Note that you could encrypt to all the recipients using the same random key (this allows you to send a single copy of the file to everyone), or a fully re-encrypted file to each.

If an attacker obtains all the encrypted messages and knows that all of them have the same content but are encrypted with different keys, would that make the attack easier?

No. (Assuming proper algorithms, obviously)

How about if the attacker manages to decrypt one of the messages, or obtains the plaintext by other means, would that compromise any of the other private keys?

And no. The point of public/private key crypto is precisely that knowledge of the public key does not compromise the private one. Note that the attacker could be creating its own encrypted messages to all those people himself, thus infinite messages whose plaintext knows.

Is there a form of asymmetric encryption that would work better than others in this scenario?

Not really. You actually want hybrid encryption, but the exact algorithm doesn't really matter, provided it is a good one. I would recommend using Elliptic Cryptography since that requires shorter keys and messages, but other than being bigger, RSA is fine as well.

Answer 4

CMS (Cryptographic Message Syntax) supports this as standard. Your data is encrypted with a random symmetric key, and this key is then encrypted once for each of the public keys of the recipients that you want to send the message to.

The OpenSSL utility implements this. You need a certificate for each recipient that you want the message to be able to be received by.

If you have a file source.bin that you want to send securely to three recipients, you could do:

openssl cms -encrypt -in source.bin -out encrypted.cms -recip friend1.cert -recip friend2.cert -recip friend3.cert 

You send them encrypted.cms.

Your "Friend 1" can then:

openssl cms -decrypt -in encrypted.cms -recip friend1.cert -inkey friend1-private.pem -out source.bin

"Friend 2" and "Friend 3" can do the same with their keys and also obtain the original data.

If you wish, you can also sign the data to authenticate it as coming from you.

See: https://www.openssl.org/docs/man1.1.1/man1/cms.html

There are lots of examples and guidance for OpenSSL and CMS on the Internet (some of it even on Stack Exchange/Overflow! :-) )