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

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.

• "the fact that adding extra security to single textbook RSA is unnecessary"... hmmmm, the term "textbook RSA" is often used to mean "RSA without nontrivial padding; that is, just doing zero padding", and that is usually insecure. Is that what you meant by the term? Or, did you have a different meaning in mind? May 4, 2022 at 3:29