How to encrypt one message for multiple recipients?

Question

What are the fundamentals to accomplish data encryption with exactly two keys (which could be password-based), but needing only one (either one) of the two keys to decrypt the data?

For example, data is encrypted with a user's password and his company's password, and then he or his company can decrypt the data. Neither of them know the other password. Only one copy of the encrypted data is stored.

I don't mean public/private key. Probably via symmetric key cryptography and maybe it involves something like XORing the keys together to use them for encrypting.

Update: I would also like to find a solution that does not involve storing the keys at all.

Answer 1

The way this is customarily done is to generate a single symmetric key to encrypt the data. Then you encrypt the symmetric key with each recipient's key or password to that they can decrypt it on their own. S/MIME (actually the Cryptographic Message Syntax on which S/MIME is based) uses this technique.

This way, you only have to store one copy of the encrypted message, but multiple copies of its key.

Answer 2

Generally speaking, what you do is encrypt the data with a randomly generated key, and then append versions of that random key that have been encrypted with every known key. So anybody with a valid key can discover the 'real' key that was used to encrypt the data.

Answer 3

If I understood you correctly, you have some data that you are willing to encrypt and distribute the encryption key splitted into n 'key pieces'.(In your case 2 pieces)

For that you could use the XOR based splitting, here is how it works: You provide the required number of pieces - n, and the secret key – K. To generate n pieces of your key, you need to create (n – 1) random numbers: R1, R2, R3, . . . , Rn−1. For that you can use a SecureRandom number generator, which will prevent us from duplicates.Then you operate XOR function on these Rn-1 pieces and your key - K:
Rn = R1 ⊕ R2 ⊕ R3 ⊕ . . . ⊕ Rn−1 ⊕ K

Now you have your n pieces: R1, R2, R3, …, Rn-1, Rn and you may destroy the K. Those pieces can be spread in your code or sent to users.

To reassemble the key, we use XOR operation on our Rn pieces:
K = R1 ⊕ R2 ⊕ R3 ⊕ . . . ⊕ Rn−1 ⊕ Rn

With the XOR function (⊕) each piece is inherently important in the reconstruction of the key, if any bits in any of the pieces are changed, then the key is not recoverable.

For more info and code, you can take a look at the Android Utility I wrote for that purpose:
GitHub Project: https://github.com/aivarsda/Secret-Key-Split-Util

Also you can try the Secret Key Splitter demo app which uses that Utility :
GooglePlay: https://play.google.com/store/apps/details?id=com.aivarsda.keysplitter

Answer 4

I think I thought of a solution that would work:

D = data to encrypt
h1 = hash(userpassword)
h2 = hash(companyPassword)
k = h1 concat h2

E = function to encrypt
//C is the encrypted data
C = E_h1(h2) concat E_h2(h1) concat E_k(D)

Then either person can decrypt the hash of the other person, and then combine them to decrypt the rest of the data.

Perhaps there is a better solution than this though?

Answer 5

In the more general case, a secret (in this application, a decryption key for the data) can be split into shares such that some threshold number of these shares is required to recover the secret. This is known as secret sharing or with n shares and a threshold of t, a (t,n)-threshold scheme.

One way this can be done is by creating a polynomial of order t-1, setting the secret as the first coefficient, and choosing the rest of the coefficients at random. Then, n random points on this curve are selected and become the shares.