encryption/decryption with multiple keys

Question

Is it possible to encrypt data, such that it can be decrypted with several different keys?

Example:

I've encrypted data with key1, but I want to be able to decrypt with keys 2, 3, and 4.

Is this possible?

Apostrophe

The current answers seem to actually encrypt a common key multiple times which increases the header length proportional to each added recipient. I would wager there is a way to produce the desired effect in which multiple keys can decrypt the one same message using modulo logic somehow. A side effect of this concept of course would be that many keys would decrypt, not just the ones you know, but that could be possibly irrelevant the same way many inputs can produce the same hash, not just the input you know. So long as entropy's high enough. I wonder of modulo-based key scheme will ever exist? – Banderole

Answer 1

GnuPG does multi-key encryption in standard.

The following command will encrypt doc.txt using the public key for Alice and the public key for Bob. Alice can decrypt using her private key. Bob can also decrypt using his private key.

gpg --encrypt --recipient [email protected] \
    --recipient [email protected] doc.txt

This feature is detailed in the user guide section entitled "Encrypting and decrypting documents"

Bottrop

Ditto. It be cool to know how to do that, but I can't find hide no man page on it. – Hadji

@Mitch, I posted an answer that may have our answer! (Please test and commend if so/not - MUCH appreciated!) – Seymour

@MarkusQ, see my link to Mitch, above. Test/thanks if you can! :-) – Seymour

So this results in 1 encrypted file which can be read using either private key, not 1 file per key? – Nidify

@user8675309, Yes. The data is encrypted by a common symmetric key. Only the symmetric key is encrypted by each recipient's public key. It's not re-encrypting the entire data for each recipient. – Raby

Where is the common symmetric key in the above command? Will the above command result in a number of files equal to number of recipients? – Brusquerie

Answer 2

Yes it's possible

Yes encryption for multiple recipients is possible. Also it seems logical when you think that you might want to be able to read what you've sent to someone and to do so you need to be in the recipients list.

Command line

Here is how to do it through gpg command line (as described in David Segonds' answer):

gpg --encrypt \
  --recipient [email protected] \
  --recipient [email protected] \
clear-message.txt

GUI client

Your GUI must provide a way to encrypt for several people

Mechanism

There is a question on Information Security, GPG File size with multiple recipients?, that explain the encryption mechanism:

GPG encrypts the file once with a symmetric key, then places a header identifying the target keypair and an encrypted version of the symmetric key.

[...] When encrypted to multiple recipients, this header is placed multiple times providing a uniquely encrypted version of the same symmetric key for each recipient.

Lowlife

special thanks for the last two sentences: they made everything exactly clear now! – Clerissa

Answer 3

GnuPG and PGP clients in general usually encrypt the actual data with a symmetric key called a "session key". The session key is then encrypted with each "recipient key" (i.e. the ones you specify with -r/--recipient). This is sometimes referred to as a hybrid cipher. Right now, I believe GnuPG by default uses an 256 bit session keys and AES to encrypt the plaintext data to that AES-256 session key, and your recipient keys are your RSA/DSA/ECDSA/etc. assymetric key in this case.

One reason for doing it this way is that symmetric cryptographic algorithms like AES are generally a lot faster than asymmetric ones like RSA. GnuPG thus only has to encrypt ~256 bits (the session key) with RSA, and can use AES to encrypt the data (as large as you want it to be!) with that session key. Intel machines even have a built in instruction, AES-NI, to do some steps of the algorithm in hardware, which makes GnuPG extra snappy at encrypting/decrypting data.

Another reason for doing it this way is that it allows PGP-encrypted documents to be encrypted to multiple parties without having to double the size of the document. Notice that when you specify multiple recipients for an encrypted document (e.g. gpg -ea -r Alice -r Bob -o ciphertext.asc), the encrypted document that gets stored (ciphertext.asc) is not 2x as large as if you had just encrypted it to Alice.

See also the --show-session-key parameter in the gpg man page to be able to decrypt just the session key, for example to allow a third party to decrypt a document that is encrypted to you without having to transfer to them your private key or the plaintext data.

Stridulate

Thanks for the explanation on the encrypted document not being n-times larger where n is the number of signers. – Enthronement

Answer 4

Yes, it's possible. Google "multiparty encryption" for a start.

AFAIK, there are no drop 'em in and use 'em packages for it though.

-- MarkusQ

P.S. For a sketch of how it could be done, consider this. The encrypted message consists of:

• the payload, encrypted with a one-time pad
• the one time pad, encrypted with key1
• the one time pad, encrypted with key2
• ...
• the one time pad, encrypted with keyN

The recipient who hold key i just decrypts their copy of the pad with their key, and then decrypts the payload.

However, this is just a proof that it could be done and would suck as an actual implementation. If at all possible, you should avoid rolling your own encryption. If you don't understand why, you should definitely avoid rolling your own encryption.

-----Edit ------------

If I'm wrong and the Gnu tools do that, use them. But I can't seem to find any information on how to do it.

Hadji

What might suck about this is that once you know the one time pad, you have a known plain text, along with the encrypted values for other keys. Using this information, you could make it easier to find out what the others keys are. – Silkweed

Googling "multiparty encryption" doesn't turn up much. You'll likely have better luck with "broadcast encryption" which encompasses this case as well. – Clomb

@Kibbee: The keys are not secret, they're public. So making it easier to find out what they are doesn't matter. (These schemes are only used with keys that can only be used for encrypting, not decrypting.) – Limbourg

I'm pretty sure that the actual implementations don't use a shared one-time pad (which would need to be as big as the plain text and encrypted text, thus doubling the message size), but actually use a shared symetric encryption key (which is usually much smaller than the message). – Dolph

Answer 5

Multiple (more than two) key RSA is maybe like this - well i'm not a mathematician, so this algorithm is not necessarily secure, i just want to give an idea with it.

m=p*q*r; p,q,r are big prime numbers

fi(m)=(p-1)(q-1)(r-1)

d==(e1*e2*e3*...*ei)^(-1) (mod fi(m)); e1...ei are arbitrary numbers, d is calculated to fulfill the equation

y1==x^e1 (mod m)

y2==y1^e2 (mod m)

y3==y2^e3 (mod m)

...

x==yi^d (mod m)

This algorithm could be used for example to increase the speed of The Onion Router.

Clutch