How safe and secure is RSA? [closed]

Question

I am using RSA for encryption and decryption. I've heard that it's vulnerable to attacks. Is it? How safe is it to use?

Answer 1

The usual attack on RSA involves factoring a large number which is the product of two very large prime numbers. The general idea behind this is that finding prime numbers is fairly easy, and multiplying them together to get a single large number is also quite easy, but if you only start with that large number, finding the factors is quite hard.

Back when they were an independent company, RSA Data Security Inc., ran a factoring challenge. IIRC, the last few prizes were won by teams from RSA DSI themselves. These were done using the General Number Field Sieve (GNFS). The typical implementation uses a large number of workstations for a few months or so to build a "factor base". Then (the hard part) you feed that to a single machine with gargantuan amounts of RAM (think terabytes as a starting point) and have it crunch for a few weeks to get the factors.

The point of that is to point out that the most common attack on RSA has a very high initial cost (i.e., getting something like a Cray supercomputer) to even get started. In all honesty, however, I don't believe any machine currently exists that can hold enough RAM to even begin an attack on something like a 1024-bit RSA key (not to mention the 2048 or even 4096-bit keys some of the paranoid types insist on using).

There are, of course, other factoring methods that don't require that huge machine, but they're enough less efficient that even at best, you'd be looking at years of work to break even a fairly small key by RSA standards -- 512 bits, for example.

Realistically, the security of RSA itself is generally the least of your concerns in designing a system that uses it. In fact, that's true of nearly all reasonably modern encryption algorithms. When something gets broken into, it's essentially never by actually breaking the fundamental algorithm involved -- it's by finding weaknesses in how keys are distributed, "social engineering" attacks, etc.

While (as I said) this tends to be true of encryption in general, it's even more consistently true with RSA than most other encryption. This is simply because the normal use-case for RSA is comparatively complex. In particular, you do not normally want to use RSA to encrypt large streams of raw data. RSA is slow enough that you generally do not want to use it to encrypt a lot of data. Instead, you typically use RSA in conjunction with some symmetric-key (aka private key) encryption algorithm such as AES.

When using the two together, you start by getting the public key of the person to whom you want to send some data. You then generate a random number of the correct size to be used as the key with the symmetric algorithm you've chosen. You encrypt your random number with RSA and send it to the target. You then use that number as the key with the symmetric algorithm, and use that symmetric algorithm to encrypt the actual data.

This means that in real use, RSA has some weaknesses that don't necessarily apply to most symmetric encryption algorithms. Just for an obvious example, if the method use to choose the "random" key for the symmetric algorithm isn't really entirely random, an attacker may be able find the key and decrypt the data, without attacking the RSA encryption itself at all (and yes, this has been the source of a real vulnerability in real, publicly released software).

Also note that what I've described above is pretty much the simplest way that RSA is normally put to use. Real systems often get considerably more complex still to provide such things as "perfect forward secrecy"¹. The RSA in such a system is still perfectly normal RSA, but the rest of the system that uses it is considerably more complex still.

Summary: if you're going to use RSA encryption, the security of RSA itself is probably the least of your concerns. The route from "RSA" to "secure communication system" is a bit like something out of a twisted combination of Greek mythology and the Christian Bible: a maze with a thousand wrong turns, each of which leads to a place that looks exactly like where you wanted to go--but taking any wrong turn will damn you to an eternity of torture and torment.

---

^{1. No, I'm not going to try to describe this right now, but I'm sure searching for it on Crypto.SE will turn up some relevant results. I should probably add, however, that although RSA can be used in a system that provides PFS, it's fairly unusual in practice.}

Answer 2

Assume RSA is safe for all your realistic needs.

But of course it depends on what you are doing, how you do it and whom you want to defend against.

If you want to secure your connection and you stick to the usual recommended stuff RSA is safe enough.

If you want to run a covert operation under the NSA nose, then you have lost already because you have to ask such a question.

PS: You may want to have a look at the IT-Security Site here on StackExchange for stuff like this..