# How to argue to a paranoid that RSA is safe?

From today's standpoint, most people would claim RSA to be secure. However, to my knowledge, this is purely based on the speculation that no one knows a computational feasible way to find a $d$ for given $n$ and $e$, s.t. $ed \equiv 1 \mod \varphi(n)$ - which can be reduced to the factorization problem.

However, it is still an assumption that the factorization problem is hard to solve but nothing that has been proven mathematically. Worse, as far as I understand it, it is not even clear to which complexity class integer factorization belongs. And if the past year has thought us anything then it is that often the "paranoia argument" is not that paranoid at all.

So I always wondered how probable it is that indeed no one has found an efficient solution to the factorization problem yet. How would one know? Or, in short: How do you convince a paranoid that RSA indeed is secure?

• Careful - while an efficient factorization algorithm implies RSA is insecure, the converse is not known to be true. In other words, it is not known (and probably false) that finding $d$ is the only way to "break" RSA. – Thomas Apr 29 '14 at 9:56
• @Thomas but this makes the paranoia argument that RSA is not secure even more probable, doesn't it? – Michael Osl Apr 29 '14 at 10:03
• Other paranoids (like banks) use it for transferring money. – j.p. Apr 29 '14 at 10:36
• There is little to argue beyond "many bright mathematicians tried to break it and nobody in published an attack faster than GNFS" – CodesInChaos Apr 29 '14 at 11:17
• Anyone lucid should wonder: how can I decide which implementations of RSA (or other crypto) I trust when even certified ones fail significantly? See factorable.net and these enjoyable slides hyperelliptic.org/tanja/vortraege/20131205.pdf – fgrieu Apr 30 '14 at 12:44

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed to be strong).

So one could "measure" the strength of an algorithm by the accumulated scrutiny it has sustained successfully. In that sense, RSA is about the best in class: it relies on mathematical principles which can be argued to have been studied for more than 2500 years by the smartest mathematicians in the World. Elliptic curves cannot compete with that.

This argument is, of course, debatable. At best. Yet one has to take into consideration that paranoia, by definition, is a distortion of the perception of reality and the balance of risks. So the paranoid can be convinced by arguments which depend on that distortion.

(*) Except the very few algorithms with unconditional security, like Shamir's Secret Sharing, but they are limited in scope. That which is done with RSA (asymmetric encryption, digital signatures) can be easily proven to be infeasible with unconditional security; e.g. signatures can always be theoretically forged through exhaustive search on signature values, since the verification algorithm is, by definition, public.

Convincing people is actually a more psychological than cryptographic endeavour. Context matters. If the context is economical, then it suffices to say: "Maybe RSA can be broken, but your competitors use RSA. Not doing the same incurs the risk of letting them run ahead of you." Indeed, the paranoid is averse to risk, and not doing the exact same mistakes as the competition is the biggest risk that can be taken by a business.

Well actually you can't!

Theoretical Perspective:

The RSA cryptosystem is based on the RSA Assumption, which is a stronger assumption than factoring.

• While we know Factoring is in NP, we don't quite know what complexity class the RSA Assumption is in.. i.e. we know if we have a efficient Factoring algorithm, we can use that to break the RSA, but don't know if the solving RSA would imply factoring.

• Factoring itself is not NP complete, so we don't really know if it is really really hard in the first place!!

Practical Perspective

• while look up tables seem almost infeasible theoretically, one can mount attacks on the Pseudorandom number generators.

• also, a bad implementation of RSA can always be fatal. (specially side channels attacks!)

To sum it up, it's hard to even convince anyone about the security of RSA.

• You should probably clarify that NP is (at best) a superset of P, so all problems in P are also in NP. We don't know factoring to be in P, nor do we know it to be NP-Hard. Saying "we know factoring is in NP" is about as convincing proof of security as "we know addition is in NP". – derobert May 2 '14 at 21:10
• i was expecting that to be implied :) when one says "something is in NP", I always assume there is a silent "and not known if in P" :) – Subhayan May 2 '14 at 21:51
• Well, that doesn't quite make sense, because then we do know what class the RSA assumption is in—it's in NP as well. – derobert May 2 '14 at 21:58
• okay, you win.. :) – Subhayan May 2 '14 at 22:07
• We know: Factoring is in NP, factoring is in Co-NP. P is a subset of NP, P is a subset of Co-NP. And if I recall correctly, P $\neq$ NP implies that NP-complete problems are not in Co-NP. And there's a one-way reduction between RSA and factoring (if they are equaivalent, we don't the the other reduction). In the end, we have no clue in which complexity class RSA and factoring actually are, but possibly in a yet unknown class, which is greater than P, both in NP and Co-NP, but contains neither NP-complete nor Co-NP-complete problems. – tylo May 5 '14 at 10:07

Any paranoia associated with using RSA can be alleviated by knowledge. Knowledge of the situation can remedy the fear involved when someone doesn't know or understand what they're contemplating. So let's look at RSA.

• In 2012, it was reported that four of every 1,000 public keys provide no security, based on the analysis of ca. 7.1 million 1024-bit RSA keys published online. In other words, the entropy of RSA keys just wasn't there.

• In 2013, RSA itself warned developers not to use RSA products, specifically the Dual_EC_DRBG random number generator (the generator in RSA’s BSafe cryptographic toolkit). Realize that, from 2004 to 2013, this was the default CSPRNG in BSafe for 9 years.

Matthew Green confirmed RSA's CSPRNG was both slow and biased (in 2013). Bruce Schneier branded the PRNG as "back-doored" back in 2007, just 3 years after NIST approved it. In the same year, Microsoft researchers devised an attack allowing adversaries to guess any key created with the PRNG with relative ease.

In 2013, Snowden and Reuters claimed NSA paid RSA a mere \$10 million to introduce the backdoor logic into their PRNG. The NSA hasn't commented, but RSA hasn't denied it.

RSA public key cryptography, when reliably implemented, is trustworthy. This means I trust someone other than RSA to implement it.

• This argues that products of RSA Security (the company, currently owned by Dell) should not be trusted. I believe that the question is about RSA (the algorithm), not RSA (the company); there certainly are implementations of the RSA algorithm that are independent of any products of RSA (the company) – poncho Jun 10 '18 at 22:11
• @poncho, point made. With the track record RSA (the company) enjoys, it seems the safe conclusion is to approach their wares with caution. I'm certainly not qualified to vet their implementation of RSA (the algo), and if others like Schneier hadn't scrutinized Dual_EC_DRBG, it might still be used to underpin TLS certs. It's not like the NIST could have been relied upon to prevent that, and it's not as if RSA (the company) itself knew how horribly insecure their PRNG was. That fact alone should give anyone pause when considering the company's security products (no matter who owns them now). – Mac Jun 10 '18 at 22:40
• Even before Snowden, people were very suspicious of Dual_EC_DRBG. RSA on the other hand is based on the RSA problem which itself is (currently) as hard as the integer factorization problem. It's been deeply studied, whereas Dual_EC_DRBG was immediately suspect. That is where the difference lies. Also note that RSA the algorithm was made by some folks (Rivest et al) who sold RSA the company decades ago. Even if you could say that everything RSA releases is backdoored, RSA the algorithm was created well before RSA the company "turned evil". – forest Jun 12 '18 at 7:40

RSA isn't secure from paranoid point of view!

• RSA is vulnerable to quantum calculus
• RSA could be broken very using large cluster, and for that only public key need
• RSA could be broken with use of soldering iron on author of message

Plus, you could use weak prime numbers at source, so your LargeNbits private key could be broken quick, with just know that you have it weak.

• An unreasonably paranoid point of view, perhaps. But none of those are terribly concerning or relevant: (1) we don't have a quantum computer capable of factoring anything near RSA-size semiprimes yet; (2) no, secure key sizes cannot be broken using a very large cluster by definition; otherwise they would be insecure (and we can 'simply' ramp up key size until security is met); (3) physical attacks are outside the purview of an asymmetric cryptosystem (mostly). Is RSA perfect? No - but the above are not really compelling imperfections. – Reid May 1 '14 at 7:19
• And using weak prime numbers is hardly RSA's fault. – Thomas May 1 '14 at 7:37