7
$\begingroup$

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

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
5
$\begingroup$

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.
Improve this answer
$\endgroup$
4
$\begingroup$

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.
Improve this answer
$\endgroup$
-2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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$'. $\endgroup$
    – poncho
    Commented Apr 17, 2012 at 14:38
  • 3
    $\begingroup$ 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) $\endgroup$
    – Paŭlo Ebermann
    Commented Apr 17, 2012 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.