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?
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.