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.

Itu

I believe the standard way to get additional security is to use a bigger keysize. – Shortfall

no, do you think it will be secure by encrypting message with two keys ? – Pitchman

Even assuming nothing more subtle, encrypting your message with two keys will double the difficulty of decrypting it - whilst encrypting it with one key, double the original length, will use the same number of key bits in total, but provide many orders of magnitude more difficulty. – Interviewer

Think of it this way. If encrypting twice doubles the difficulty for an attacker, you could get exactly the same increase in difficulty by adding a single bit to the first encryption key. Hope that helps. – Overblouse

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.

Hokusai

Does this mean that RSA(Key1, RSA(Key2, Message)) can be unencrypted by a single Key3? Otherwise, I find it hard to believe that there is "no additional benefit". – Jermainejerman

@mike: I'm pretty sure that Key3 may not exist and that if it does it has a torturous (uninvertable?) relationship with Key1 and Key2. However, I'm not a cryptologist. This is speculation based on the manner in which messages to multiple recipients are encrypted and the use of multi-factor key systems. Don't try this at home, offer void in Nebraska. – Hokusai

I'm positive that Key3 exists however the relationship is uninvertable. The best case is it's like trying to break RSA(Key1) where compromising part of Key1 won't help. However, Key3 likely has more bits than Key1. – Fungi

@Joshua: Positive? Then what is it, or at least why are you positive? – Haakon

GregS: Because RSA fails the uniform zero knowledge proof, Key3 must exist (note the algorithm for Key3 is not guaranteed to be RSA). There are no weak plaintexts for RSA so the problem can't get any easier for adding more depth. QED. – Fungi

@Joshua: That's pretty silly, of course if you allow any algorithm you can recover the original plaintext. The question concerns RSA. – Haakon

GregS: no it's not. I'm talking about the complexity of the attack. – Fungi

Answer 2

No.

It is not safe to do thought experiments regarding cryptography. You are advised to keep narrowly to the path trodden by the experts.

And when the experts want to protect something better, they use a bigger key-size (at least 2048 bits is required, smaller certificates are insufficient for any peace of mind) or use elliptic curve certificates in preference to RSA.

Incidentally, you're remember that your message body is typically encrypted with a symmetric cipher and a random key, and that just this random key is encrypted with the public key of the recipient. Double-encrypting this secret key won't make this secret key longer, and won't impact an attacker's ability to brute-force that.

Quantum cryptography - I mention it only as an exciting aside, you need not factor this into your choice - promises interesting things for the keysizes: the RSA keys will be wiped out by Shor's algorithm, but the symmetric keys (Grover's) will be only half-lengthed (128-bits will be equiv to 64-bits, so will be crackable). There is of course debate about whether such quantum machines can be implemented etc etc :)

Jenness

Answer 3

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.

Brahmani

Answer 4

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

Photodrama

Answer 5

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.

Haakon