# Is RSA provably secure in the sense of Douglas Stinson's provable security''?

Here's a quote from Douglas Stinson:

“[i]f a cryptosystem can be ‘broken’ in some specific way, then it would be possible to efficiently solve some well-studied problem that is thought to be difficult. For example, it may be possible to prove a statement of the type “a given cryptosystem is secure if a given integer n cannot be factored.” [...] [B]ut it must be understood that this approach only provides a proof of security relative to some other problem, not an absolute proof of security. This is a similar situation to proving that a problem is NP-complete [...].”

Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.

Does this apply to RSA? Suppose I find the private exponent by some other way other than factoring $$n$$. Then I would have broken RSA without factoring.

So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key. What do you say?

• Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for. – Ilmari Karonen Dec 8 '18 at 18:40
• @IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult". – Maeher Dec 8 '18 at 18:42
• @IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $\phi(n)$ (or to factor $n$)? – user45491 Dec 8 '18 at 18:48
• Yes, there is. – Ilmari Karonen Dec 8 '18 at 18:53
• @user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key. – Mikhail Koipish Dec 8 '18 at 20:02

This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $$e$$-th roots mod $$n$$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.