risk of attacker decrypting RSA ciphertext without public or private key

Question

As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a simple symmetric encryption like AES-256. The answer to that question pointed out that using RSA to encrypt the symmetric encryption keys cannot make the solution any more secure. But since there are practical advantages I wanted to ask a further question:

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data? I'm thinking that perhaps in my case the risk of the public key leaking from a trusted system that is doing the key-wrapped symmetric encryption is pretty small. And if by "broken" we mean the first alternative, and if we assume for a moment that the risk or the RSA public key leaks is zero (i.e. it's not public anymore) I am wondering if the more practical RSA+AES solution is for some reason actually less secure, rather than just equally secure, than the plain symmetric method.

Thank you!

Answer 1

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data?

First off, we always assume the attacker has the public key. Someone saying "RSA is broken" could mean either. The first is a key recovery attack; the second is a message recovery attack. The second (finding $p$ from $c=p^e\bmod{n}$) is what is known as the RSA Problem. It just so happens that currently the fastest way to solve the RSA problem is to recover the private key (think factoring) and then recover the plaintext. It has never been shown that there doesn't exist a better way to find $p$ however (for more on this, see this question).

Answer 2

Thinking a bit about your problem, you could potentially strengthen it by chaining key encryption algorithms. Using two-phase encryption (a symmetric algorithm like AES-256 protecting the data, and an asymmetric algorithm like RSA protecting the key) exposes you to weakness in either AES or RSA. You could attempt to strengthen the key protection by adding El Gamal or ECC as a step on top of RSA. This would not change the attacks on the AES data, but would mean a break of the key would require the attacker to crack both RSA plus a second algorithm. The advantage is that if RSA suddenly falls to a novel factoring attack, your key remains protected by a completely different algorithm based on discrete logarithms, or some other mathematically hard problem.

Nobody has a crystal ball that can tell how well any such algorithm will fare 30 years from now. What we do know is that we don't have a way to reliably crack either of those algorithms today, let alone both of them.

Any security measures also need to be practical against the likely threats. My guess is that if you're planning to protect a secret worth millions of dollars, an attacker would be motivated to find a different way to get the secret.

Consider the CIA (and/or the Mossad) recently used burglars to steal copies of the private certificate signing keys in order to pull off the Stuxnet attack on Iran. This was a direct attack on Iran's uranium enrichment capabilities, which to be honest is someone with a much bigger incentive than anyone planning to break your encryption scheme. If anyone had the resources to crack 4096-bit RSA it would be the U.S. government, yet they found it more cost effective to send safecrackers and technicians into Chinese factories in the middle of the night.