# Is it safer to encrypt twice with RSA?

I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the only way used to crack it is brute force. I submitted these theories to my teacher, but he claims that a double encryption doesn't make it any safer. I didn't follow his arguments entirely, so I decided to ask here.

So, if I encrypt a message with one key once, and the encrypt the resulting cipher text once more with a different key, does this make the encryption simpler?

EDIT: My teacher said that "it doesn't get safer with a double encryption, at least not if n is the same and e is different.". This is the part I don't follow, since you'd still need both p and q to derive the two different private keys that this would produce. I have made a few calculations and I do not quite understand. Why would the particular statement my teacher sent me mean that it doesn't get safer?

-
One should note the second public key would have to be larger than the first public key to guarantee correct operation. –  Thomas Nov 15 '12 at 13:27
For that matter, why not just encrypt with a longer key to begin with? –  Stephen Touset Nov 15 '12 at 19:38
@StephenTouset: This is a theoretical problem, not a practical. Therefore the option to choose a longer key is irrelevant, but thanks for the input. –  Psyberion Nov 16 '12 at 15:33
If you know $e$, $d$ and $n$ you can efficiently factor $n$ to obtain $p$ and $q$. Once you know $p$ and $q$ obtaining $d_2$ from $e_2$ is trivial. See Can two different pairs of RSA key have the same modulus? –  CodesInChaos Nov 16 '12 at 16:04
@CodesInChaos: Thank you, I'll take a look at that! –  Psyberion Nov 16 '12 at 19:43

Well, think about it this way. If breaking one encryption with brute force will take longer than the lifetime of the universe, are you any safer with an encryption scheme that will take twice the lifetime of the universe? No. The first encryption cannot be broken. Adding a second encryption just adds computation overhead with no real benefit.

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.

UPDATE
Given the update in the question, I thought I'd update.

So, you fix an $n$ and choose $e_1$ and $e_2$ as public exponents and compute $d_1$ and $d_2$ as the private exponents.

To encrypt, you are proposing $(m^{e_1})^{e_2}\bmod{n}$ and wondering why this is not stronger than just $m^{e_1}\bmod{n}$ in a brute-force attack[*].

So, you haven't given detail as to what the "brute-force" attack is, so let's look at two options.

1. Factoring $n$. If I factor $n$ using a brute-force attack, I then use the factorization to compute $d_1$ and $d_2$. Computing both $d_1$ and $d_2$ is not much more than just computing $d_1$ since you broke the factorization.

2. Instead of factoring $n$, what if you try to brute force $d_1$ and $d_2$. Recall that $d_i$ is chosen such that $e_i d_i\equiv 1\bmod{n}$. Furthermore, $(m^{e_1})^{e_2}=m^{e_1e_2}$. Raise that to $d_1d_2$ and you get $m$ back. Therefore, you really need to bruteforce $d_1d_2$ instead of $d_1$ and then $d_2$ (or vice-versa). If you assume each of the $d$s are $l$ bits, brute forcing $d_1$ then $d_2$ would be like brute forcing $l^2$ bits. Brute forcing $d_1d_2$ on the other hand is $2l$ bits. One could argue that this is harder, but asymptotically it isn't.

3. Brute force only $d_1$ then factor. It turns out if you know $d_1$ you can easily factor $n$ then use the factorization to compute $d_2$. (This comes from @CodesInChaos comment).

Any other brute force options you had in mind?

[*] My description of double encrypted RSA here is assuming textbook RSA. For padded RSA (which is what you find in the real world), points 1 and 3 are still valid, 2 however is not.

-
Furthermore, if the prisoner is given a hacksaw, he can cut through the two sets of bars pretty quickly anyway. Even if brute force is the only way to break algorithm X today, it may not be in ten years from now. This is why we don't see people boasting RSA-65536 keys - it's pointless and just serves to inconvenience the user. –  Thomas Nov 15 '12 at 14:02
I do follow your arguments, and I agree with them. Although, I was looking for a more mathematical explanation. I've added some info to the question to make it clearer. –  Psyberion Nov 16 '12 at 15:32
@Psyberion, I've added some mathematical arguments given your update. –  mikeazo Nov 16 '12 at 16:20
Not sure if you can call $(m^{e_1})^{e_2}$ encrypting twice since that only works with textbook RSA. With real RSA, you'd add padding before each encryption, making the intermediate ciphertext too large for a single exponentiation of the second encryption. –  CodesInChaos Nov 16 '12 at 16:27
@CodesInChaos, good point. I always seem to assume textbook RSA. Need to get all the intricacies of real RSA more firmly ingrained in my brain :) –  mikeazo Nov 16 '12 at 16:31

Double encryption/decryption with RSA is equal to single encryption/decryption with public/private exponents raised to the square. It doesn't make brute-forcing the private exponent harder. More, it doesn't complicate the factorization of N.

So, it is not more secure.

-
Not true if you include padding. Also, the OP specifically says that $e$ is different. –  mikeazo Nov 19 '12 at 11:55
It will be impossible with padding due to encrypted message size. –  Pavel Ognev Nov 19 '12 at 17:28

Assuming that you use a IND-CPA,CCA secure assymetric enncryption scheme that leaks some kind of information from the ciphertext. By re-encrypting the message is like you encode into a different form and you achieve all-or-nothing security. That means that the attacker in order to reveal 1 single block he should break the message in its entire form. A second point is that you actually re-encrypt sth if you have an intermediate node that transforms messages of key k1 into messages encrypted with key k2. This is so callade proxy re-encryption and is done for delegation of operations and transitivity purposes.

-
If it is IND-CPA secure, the ciphertext can't leak information -- that is self-contradictory. I'm not entirely sure I follow the rest of the answer, but it doesn't look right to me. –  D.W. Nov 16 '12 at 5:45
Does the fact that a tiny amount of information is discovered for the plaintext from the ciphertext violates the IND-CPA security? I am wondering as IND-CPA refers to fully recover the plaintext –  curious Nov 16 '12 at 12:47
Breaking IND-CPA security does not require fully recovering the plaintext -- it just requires you to learn enough about it to have a better than random chance of telling the encryptions of two plaintexts (of your choosing) apart. –  Ilmari Karonen Nov 16 '12 at 15:07
"Does the fact that a tiny amount of information is discovered for the plaintext from the ciphertext violates the IND-CPA security?" - In short: yes, it does. –  D.W. Nov 16 '12 at 19:33
@D.W. Is there a quantitative assessment in how large this partial plaintext recovering should be in order to be conjectured as CPA? –  curious Nov 19 '12 at 10:35