# 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

Not at all - as was pointed out by other answers, it isn't even known whether non-quantum cryptography (more precisely: one-way functions) exists at all (in a suitable sense).

It is a pure leap of faith if you trust cryptography to protect information assets. The only hint that cryptography in general and RSA in particular might work is that despite many attempts there's no evidence for the contrary.

-

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