RSA: Encrypting message using multiple keys

Question

Is it possible to get additional security by encrypting a message using 2 or more RSA keys?

EDIT: A few clarifications:

The context I am most interested in doing this for is encrypting a randomly generated symmetric key.

I don't want to limit the question to encrypting twice in a row; the purpose is to avoid the high computational cost of large RSA keys. Using less straightforward tactics such as breaking the message into parts and encrypting them separately should be considered as an option.

It should be assumed that getting only part of the message is acceptable.

If you know of any publications where this is discussed specifically by an expert, or algorithms that use multiple RSA keys, then please contribute.

Answer 1

No.

If Key A is compromised than encrypted with A+B will protect against the compromise, but outside that special case, you get no additional benefit.

Answer 2

Yes!

But do not use raw encryption. Use RSA encryption schema. Instead of reencrypting the encrypted message with the second key, which might have weakening effet (I don't know), use the shared secret algorithm to split your secret in two. The shared secret algorithm make it possible to split a secret in n pieces and ensures that if an attacker manages to get n-1 pieces he knows nothing of the secret. So don't simply split the secret in two.

You can then have more then 2 RSA keys. Another powerful property of the shared secret algorithm is that it is possible to spread the secret over n pieces and require only m pieces, with m smaller than n, to recover the secret. This makes the secret recovery more robust to loss of pieces.

Look here for more information on shared secret: http://en.wikipedia.org/wiki/Shared_secret

Answer 3

In additional to the answers given, it also simply doesn't work unless you do some patching. Very simply, one of the moduli must be larger than the other. If you perform RSA mod the larger modulus first and mod the smaller last you lose information and cannot guarantee successful decryption. The obvious patch is to always encrypt with the smaller modulus first. Of course, you have to perform decryption in the opposite order. Another simple patch is choose moduli that a very close together in size, so that the probability that you encounter a ciphertext that cannot be uniquely decrypted is vanishingly small.

Answer 4

Composing ciphers

Say you have an encryption function E(M, K), where M is the plaintext message and K is the key. Say no known vulnerabilities exist in E.

You generate two completely unrelated keys K1 and K2.

It is guaranteed that if you compose them in the form E(E(M, K1), K2), it is impossible to actually lose security this way. If it was possible to lose security from encrypting E(M, K1), be it with K2 or any other key, the is cipher broken, because an attacker could just do E(E(M, K1), KF) where KF is any key the attacker wishes to choose.

For more info see here.

Encrypting every second block with a different key

The implications here are obvious. Assuming you are using properly composed cryptographic primitives with both encryption function:key combinations, if you encrypt every second block with a different key out of the set of two keys, the attacker can only decrypt the blocks he has the key for.