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)?
The summary in the Rivest-Kaliski paper does indicate that two specific problems are equivalent to the RSA problem itself.


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