Would encrypting a message twice with RSA with different keys be more secure that once?

Question

This was a practice problem for a class. The class is over now and I never solved it, so I thought I'd ask here.

Let's ignored the fact that adding extra security to single textbook RSA is unnecessary. As hilariously stated here:

Think about it this way, if it is estimated to take 500 years for a prisoner to chew through the bars on his prison cell to escape, is the public any safer if we add a second set of bars so that it will take 1000 years to chew through the two sets before the prisoner can escape? Not really.

The proposed question:

Does encrypting data twice with RSA and different keys increase security over encrypting data once with RSA?

Thinking about it now, I feel it would because you're introducing a second factorization problem that the adversary must compute.

Could someone please explain, mathematically, why I am correct/incorrect?

Note: For notation and algorithms, I am more familiar with that used in the original paper, particularly the use of Euler's totient function, not Carmichael's totient function.

Answer 1

Could someone please explain, mathematically, why I am correct/incorrect?

This isn't a mathematical explanation, however I believe it's not a mathematical situation.

By performing RSA twice, the attacker would need to break through both (presumably by factoring the modulii), hence making his work effort twice as much.

If we assume that the attacker does not have the capability of breaking RSA, this is no more secure. If he has the capability of breaking RSA without extreme effort, this is not secure (as he can just break both). Hence, this works on that relatively narrow region where the attacker just has barely enough resources to break it once, but can't afford to do it twice. We, in general, don't know enough about the attacker's capabilities to make this determination, and so if the attacker may have enough capabilities to break RSA, he is likely to have enough capabilities to break it twice, and so no real security is added.

On the other hand, doing RSA twice doubles the time taken by the valid encryptor and decryptor. If we're happy with doubling that time, we can (say) increase the size of the single RSA modulii by 25%; that vastly increases the time needed to break RSA (on a conventional computer using known algorithms) by much more than a factor of 2, hence that is a considerably more attractive trade-off.

In addition, another possibility is to use, instead of a second RSA operation, a totally different public key cryptosystem, for example NTRU. That would mean that, even if the attacker happened to have a fast way to break RSA (e.g. with a Quantum Computer), he would still have to break NTRU, and the two systems RSA and NTRU are sufficiently different that it is unlikely that the same breakthrough would apply to both.