2

An RSA key is actually a key pair: a public key and a private key. The public key is usually uploaded to a server. If I understand correctly, in this situation, attacking RSA amounts to solving a math factoring problem, for which there are (currently theoretical) efficient quantum algorithms.

My question is, what if the RSA public key is not actually made public at all? Is it as easy to attack such "purely private" RSA encryption than it is to attack "normal" RSA encryption, in which the public key is known? Is the public key somehow embedded in the RSA encrypted message? If not, do the quantum algorithms need the RSA public key to work?

If purely private RSA is harder to attack, how does purely private 2048/4096 RSA encryption compare to 128/256 AES?

Edit: I understand that:

  • RSA is usually only used to encrypt a random "session key", which is then used for symmetric (say, AES) cryptography. E.g., in OpenPGP: https://www.rfc-editor.org/rfc/rfc4880#section-2.1 .

  • The extra RSA layer introduces an extra vulnerability: one can attack it by breaking either RSA or the session AES.

  • If the extra RSA layer uses a known public key, it is "much easier" to break that, at least in theory, using future quantum algorithms, than it is to break AES.

What I'm trying to understand is, how does "purely private" RSA + session AES compare with AES alone (assume the same AES key size).

Edit 2: To avoid unnecessary tangents, I added an extensive clarification of what I'm trying to understand here. The question there is "Is there a hacky way to remove the unnecessary RSA?". The OP here asks "Just how bad is the unnecessary RSA?"

Improve this question

2 Answers 2

Reset to default
4

No widely used system uses RSA to encrypt data. RSA is slow. Really slow. RSA is used together with an symmetric cypher like AES. A random key is created for AES, the data is encrypted with AES and that key. Then the Key is encrypted with RSA and thrown away.

If you can crack the symmetric cypher (usually AES nowadays) you can also break the hybrid encryption. In practice, there is no advantage for you. In one case, the attacker has to break AES. In the other case, he can either break AES or RSA to get your message!

I don't think there is a thorough analysis of the RSA strength without the publik key known. It depends on the exact software/format you use, if the public key is embedded or not. It is quite possible to not embed it. But in the end, RSA just has no use case when it is not used as asymmetric cryptography.

If RSA is secure and no fault is found, then it still can be decrypted if you have the public key and can factorize it. For AES this isn't true. If no flaw is found in AES, it cannot be cracked. It is just possible to brute-force attack it. This means trying all keys and check if a valid message is output. Depending on the format of your message, even deciding if the message is valid is very hard.

If you don't need asymmetric cryptography, use symmetric cryptography!

Improve this answer
3
  • I understand that public key crypto has very specific use cases, and also that it's usually combined with symmetric (see edit). However, the reason for the OP is to understand how secure some already existing software is, again, provided that the RSA public key is kept private. Specifically, I'm looking at git-annex: git-annex.branchable.com/design/encryption , "The generated cipher is then checked into your git repository, encrypted using one or more OpenPGP public keys". But the OP should stand on its own.
    – Matei David
    Aug 2, 2016 at 16:13
  • Both are secure when large enough key sizes are used, unless there are breakthroughs in breaking them. No one can predict if/when/what breakthroughs will happen.
    – Josef
    Aug 2, 2016 at 17:21
  • For all applications (crypto or not) the optimal choice of alternatives will depend on the actual usages. In the present context, it is evident that for the communications of the common people, whose messages are practically invariably of highly limited sizes, the speed of RSA can never play a decisive role in the choce between (1) direct encrypton with RSA and (2) use RSA only to transfer a secret key for a block cipher to do the proper encryption work. I found with my coding that (1) for a message of 10000 characters need only a couple of secs. See s13.zetaboards.com/Crypto/topic/7234475/1/
    – Mok-Kong Shen
    Aug 3, 2016 at 8:08
2

An RSA key is actually a key pair: a public key and a private key. The public key is usually uploaded to a server. If I understand correctly, in this situation, attacking RSA amounts to solving a math factoring problem, for which there are (currently theoretical) efficient quantum algorithms.

There are no known practical implementation methods to factor large prime numbers. If this were accomplished it would make world news.

My question is, what if the RSA public key is not actually made public at all? Is it as easy to attack such "purely private" RSA encryption than it is to attack "normal" RSA encryption, in which the public key is known?

The design of RSA (or any public key encryption) is that the Public key offers no assistance in decrypting the message.

If a new advancement in technology allowed us to factor prime numbers then having the Public key may prove useful, depending on the capability of the new technology.

Otherwise there would be no practical way to decrypt the message without the Private key. (assuming proper implementation)

Is the public key somehow embedded in the RSA encrypted message?

No. The Public Key is exchanged prior to message encryption. Neither key is stored within the encrypted method.

If not, do the quantum algorithms need the RSA public key to work?

There is no you could simply ask "Would a quantom algorithm that breaks RSA encryption require the Public Key to work." on Theoretical Computer Science Stack Exchange. The folks here on Security Stack Exchange are more familiar with practical implementations today.

If purely private RSA is harder to attack, how does purely private 2048/4096 RSA encryption compare to 128/256 AES?

AES is a Symmetric encryption algorithm. (not public key, or Asymmetric) AES is much more efficient since it has no need to support Public Keys. For high-security applications it is better to use AES-256, but AES-128 is more than sufficient for most purposes.

Both RSA 2048/4096 and AES-256 should prove equally effective based on our understanding to day. While you could post a question on how likely one algorithm is to be broken over the other... from a practical stand-point, both of them have had many years of high-intellect peer review and are considered secure.

I'm afraid I'm not familiar with quantum computing, but the folks at Theoretical Computer Science will probably understand this subject better than I.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .