5
$\begingroup$

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?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ One should note the second public key would have to be larger than the first public key to guarantee correct operation. $\endgroup$ – Thomas Nov 15 '12 at 13:27
  • 2
    $\begingroup$ For that matter, why not just encrypt with a longer key to begin with? $\endgroup$ – Stephen Touset Nov 15 '12 at 19:38
  • $\begingroup$ @StephenTouset: This is a theoretical problem, not a practical. Therefore the option to choose a longer key is irrelevant, but thanks for the input. $\endgroup$ – Psyberion Nov 16 '12 at 15:33
  • 4
    $\begingroup$ 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? $\endgroup$ – CodesInChaos Nov 16 '12 at 16:04
  • $\begingroup$ @CodesInChaos: Thank you, I'll take a look at that! $\endgroup$ – Psyberion Nov 16 '12 at 19:43
10
$\begingroup$

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{\varphi(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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Nov 15 '12 at 14:02
  • $\begingroup$ 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. $\endgroup$ – Psyberion Nov 16 '12 at 15:32
  • $\begingroup$ @Psyberion, I've added some mathematical arguments given your update. $\endgroup$ – mikeazo Nov 16 '12 at 16:20
  • 3
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Nov 16 '12 at 16:27
  • $\begingroup$ @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 :) $\endgroup$ – mikeazo Nov 16 '12 at 16:31
2
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Not true if you include padding. Also, the OP specifically says that $e$ is different. $\endgroup$ – mikeazo Nov 19 '12 at 11:55
  • 1
    $\begingroup$ It will be impossible with padding due to encrypted message size. $\endgroup$ – Pavel Ognev Nov 19 '12 at 17:28
0
$\begingroup$

Yes it is.

If we accept that a brute force attack against cannot be broken in a lifetime then it makes no sense to add a second layer. But what happens if one of the keys becomes compromised? having a second, entirely different encryption key, keeps the data safe.

In a single decryption operation if you had the right key you would convert your cipher text into plain text and yay! with a double encryption you'd convert cipher text to cipher text which would appear the same as using a wrong key...

Why do nuclear submarines have two keys to launch their missiles?!

(It's more secure than one key!)

|improve this answer
$\endgroup$
  • $\begingroup$ People don't break RSA, people break lame ass passwords used to 'secure' private keys. $\endgroup$ – Joseph Jun 6 '17 at 1:48
  • 1
    $\begingroup$ Why do nuclear submarines have two keys to launch their missiles?! — They don't. They have single launch codes. And when it comes to nuclear weaponry, such launch codes are merely split into several parts to gain additional authorisation layers… just like nuclear warheads are kept separated from the missiles themselves up until the point they are being put to action. All that can hardly be compared with double-encryption as described in the question, or with cryptographic security in general — which makes your argument/example as relevant in this context as bananas are relevant to coconuts. $\endgroup$ – e-sushi Jun 6 '17 at 3:20
  • $\begingroup$ If the same $n$ is used (as stated in the question), then a "compormised key" (knowing either the factorization or $d$) actually breaks both encryption layers (which are actually just one in the case of textbook RSA). $\endgroup$ – tylo Jun 6 '17 at 13:04
-2
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 16 '12 at 5:45
  • $\begingroup$ 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 $\endgroup$ – curious Nov 16 '12 at 12:47
  • 4
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Nov 16 '12 at 15:07
  • 2
    $\begingroup$ "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. $\endgroup$ – D.W. Nov 16 '12 at 19:33
  • $\begingroup$ @D.W. Is there a quantitative assessment in how large this partial plaintext recovering should be in order to be conjectured as CPA? $\endgroup$ – curious Nov 19 '12 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.