How to deliver an encrypted message to multiple recipients without revealing keys

Question

Let's say I have generated a private and a public key. I create a message and encrypt it with the public key. I deliver this encrypted message and a private key to multiple recipients.

Why would I do this?

I want to be able to deliver a message that can only be decrypted. I don't want anyone to be able to encrypt a dummy message and deliver this to all recipients with them assuming it was from me.

I think I am on the right track using RSA - but somehow I need it all in reverse.

Also, if I give people the private key, and I keep the public key safe, am I right in believing that it's possible to generate a new public key just using the private key itself?

Let's take an example of my problem.

I create an encrypted message using my public key:

ajjfjdksdjkdfjfjdjfd

The end user decrypts it using the private key to:

green:1234:table

All good so far. The above message and be authenticated very basically checked for the three strings within a :.

However, as these encrypted messages could be from untrusted sources, I want it impossible for any untrusted source to be able to create these messages since they know the simple format. I don't want the key I provide be enough for them to reverse engineer the public key.

I am finding it hard to explain, I am hoping that this can be answered.

Answer 1

I think you've gotten public key cryptography all out of whack, here.

1. You don't give out a private key. Period. They're called "private" for a reason.

2. You don't send an encrypted message along the same channel, let alone at the same time, as you send the only key that is needed to decrypt it. That completely defeats the purpose of the encryption in the first place.

3. A key pair is only useful for authentication (i.e.: digital signature) if the public key has been verified by the recipient(s) (or a trusted third-party) prior to use.

So, how do you deliver an encrypted & signed message to multiple parties without allowing them to impersonate you in return? The answer lies back in #1: No two people hold the same private key.

If you're the only one with a copy of your private signing key, nobody can impersonate you. You simply sign the message with your private signing key before any encryption is done. Recipients then use your public signing key to verify the message's authenticity after they've decrypted it.

The encryption portion is a completely different matter. And for that, you have a few options.

1. No encryption. Just sign and deliver. Authenticity is protected regardless, but this method offers no confidentiality.

2. Encrypt with pre-shared key (PSK). Emphasis on pre-shared - this one doesn't get shipped along with the message. It should be shared among the group before-hand, preferably out-of-band. The PSK is used for encryption/decryption only. Your signing key is what provides authenticity.

3. Encrypt individually with public keys. Take the signed message, and make a copy for each recipient. Then, encrypt each copy with one recipient's public key and send it along. The recipients will use their private keys to decrypt the message.

4. Use private keys as key-encryption-keys (KEK) for a shared key. Depending on the size of the message, this can be quicker than #3 while still keeping the benefits of public key encryption. You generate a random, one-time use, shared key. Use that to encrypt the signed message. Make a copy of the shared key for each recipient. Encrypt each copy of the key with one recipient's public key. Bundle all the encrypted keys together with the encrypted message and send a copy of that same bundle to each recipient. Each recipient will use their private key to attempt decryption of each copy of the shared key until they find their copy, then they'll use that to decrypt the message.

Again, the main thing that protects the authenticity & verifiable origin of the message here is the fact that only you have a copy of the private key that was used to sign it. Beyond that, for authentication purposes only, it doesn't matter how or even if the message is actually encrypted. At the end of each of these processes, when the recipients have a cleartext copy of the signed message, your public signing key is what they'll use to verify its origin and integrity.

Answer 2

Chris wants to send a message to Alice and Bob.

Chris does not want Dave to send a message to Alice and Bob and purporting to be from Chris.

Thus, there must be a way for Alice and Bob to be able to distinguish between a genuine message from Chris, and an imitation by Dave. Like, something like a signature from Chris. This method exists, and is called (appropriately) a signature.

Conceptually, you want Chris to be able to do something (sending a message that will be accepted by Alice and Bob) that non-Chris (in particular Dave) cannot do -- so there must be some secret value that Chris knows but not Dave, because, in cryptography, knowledge is power. Moreover, this secret value must not leak in the process, and, in particular, you do not want Alice and Bob to learn it (otherwise, Alice could then try to Davify Bob, i.e. send to Bob a message as if she was Chris).

So, a secret value on the sender side, for an action verifiable on the receiver side, without leaking the secret itself. This is exactly the concept of digital signatures.

This holds regardless of any notion of encryption. This is a completely orthogonal discussion.

Answer 3

You don't have to reveal any keys, that's the main point of a public key encryption system.

In this message from gnupg list, they explain a way to create a multiple recipient message.

Based on it, you could create something like this:

1. Generate a random symmetric key S1

2. Encrypt the entire message with S1, creating the cyphertext C1

3. Encrypt S1 with each public key for the recipients, generating D1, D2, ... , Dn

4. Generate a secure hash of S1, creating H1

5. Generate the message as follows:

-- BEGIN CYPHERTEXT --
C1
-- END CIPHERTEXT --
-- BEGIN HASH --
H1
-- END HASH --
-- BEGIN KEYS --
D1
D2
D3
-- END KEYS--

Send the message to everybody. They will decrypt D1 to Dn to generate S1. Comparing the result with the hash on the message, they will know when they got the symmetric key.

With the symmetric key on hand, they can independently decrypt the message, without knowing each other keys.

To create an authenticable message, add a signature to the entire message, and nobody will be able to create a message posing as you, unless they get your private key.