# Security equivalence proofs for breaking RSA

It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.

In otherwords, theoretically, someone could mathematically break RSA without breaking the factoring problem.

Are there any problems for which breaking RSA would be equivalent to (besides the obvious RSA Problem)?

-
I think this paper people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf might answer your question, at least in part. –  Henrick Hellström Apr 16 '12 at 23:00
@HenrickHellström: Do you (or someone else) want to post a summary of the results in this paper (where they relate to the question) as an answer? –  Paŭlo Ebermann Apr 17 '12 at 20:08

The summary in the Rivest-Kaliski paper does indicate that two specific problems are equivalent to the RSA problem itself.

1. Due to the algebraic properties of the field $Z_n$, if there exists any small fraction of weak cipher texts (i.e. a particular subset of cipher texts $C$ for which finding the solution $M$ to $C = M^e \pmod N$ is easy), then the RSA Problem is at most as hard as the running time of the adversarial procedure for decrypting the weak cipher texts times a polynomial factor. IOW: The RSA Problem guarantees that all cipher texts are equally hard to invert.
2. A similar argument applies to each individual bit of a RSA cipher text. If an adversary has a non trivial advantage to determine any bit of a RSA plain text $M$ given a RSA cipher text $C$, then all bits of $M$ are equally easy to determine.
-

Actually, this is an equivalence (see http://www.jscoron.fr/publications.html#joc2007) when ed <= N^2.

-
Actually, no, that paper doesn't claim that 'if you can break RSA (that is, find the $e$'th roots modulo a composite of unknown factorization), you can factor the composite.' Instead, the paper shows that, given $N$, $e$ and $d$, you can factor $N$ (which we knew already with the probabilistic algorithm). The paper does not show that 'if you could break RSA, you can recover $d$'. –  poncho Apr 17 '12 at 14:38
Tukikun: Welcome to Crypto Stack Exchange! The confusion here is that one can see two ways of Breaking RSA: The key recovery one (i.e. from $N$ and $e$ and maybe some messages/signatures, recover $d$) is (which shows the paper you linked) equivalent to factoring of $N$. But there is a more general way of defining breaking RSA encryption, which simply is plaintext recovery, and this is called the RSA problem ... and this could be easier than key recovery/factoring. (cc @poncho) –  Paŭlo Ebermann Apr 17 '12 at 20:01

It seems that the RSA Problem stands alone (at least for now, right?). The paper pointed to by Henrick outlines the following.

1. The RSA Problem is no harder than factoring, but (especially for small encryption exponents) it is likely "easier" than factoring.
2. Computing the private key from the public key has been shown to be equivalent to factoring.
3. There are no easy-to-break ciphertexts.
4. If an adversary can break a single bit given the ciphertext, the whole ciphertext can be revealed.
-