2
$\begingroup$

Suppose $(n, d)$ is an RSA private keypair. We know the public key only (wlog suppose it's $(n, 2^{16}+1)$ and we are given oracle $E$, decryption oracle for $(n, d)$. Is there any efficient algorithm to recover $d$? This is a bit easier than directly attacking for known pair of plaintext and ciphertext, as for any $m$ we can astablish this relation:

$$ E(m) \equiv m^d \pmod n $$

$\endgroup$
2
$\begingroup$

No, there is no known way to recover $d$ using an Oracle that, given $m$, returns $m^d \bmod n$; there is also no proof that such a method does not exist.

Such a method would imply that the RSA problem (which is, given $m^e \bmod n$, recover $m$) is equivalent to the factorization problem (which knowledge of $d, e$ would allow you to solve); it is unknown if these two problems are equivalent.

$\endgroup$
  • $\begingroup$ I don't understand. Suppose we have this oracle, and we can recover $d$ with it. Then we indeed can factorize $n$. But that is not any of the known open problems - one of open problems is to show that breaking RSA (as you described) implies factorizing mudulus. But that is true only with this oracle, so the computation model is different. These are two separate problems. $\endgroup$ – enedil Apr 21 at 20:51
  • $\begingroup$ Nonetheless, I appreciate your insight $\endgroup$ – enedil Apr 21 at 20:51
  • $\begingroup$ @enedil: no, they're not really separate problems. Suppose you knew a method that, given an oracle that computes $m^d$, recovers $d$. Then, the RSA problem and the factorization problem would be equivalent; to prove that, you'd take your hypothetical RSA problem solver, put that within an oracle, and hand that oracle off to your method that would return $d$ (which, along with $e$, allows you to factor) Since we don't know that equivalence to hold, there is no known method (and any such news would be noteworthy...) $\endgroup$ – poncho Apr 21 at 21:31
  • $\begingroup$ It might be worth mentioning that breaking RSA generically was shown to be equivalent to factoring. $\endgroup$ – Marc Ilunga Apr 21 at 21:49
  • $\begingroup$ @MarcIlunga: unless I missed something, that was not shown; a method of breaking RSA that allows you to recover $d, e$ does allow you to factor; however that still leaves open the question of methods of breaking RSA that don't give you $d$... $\endgroup$ – poncho Apr 21 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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