# Discrete logarithm with exponentiation oracle

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

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.
• 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. – enedil Apr 21 '19 at 20:51
• @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...) – poncho Apr 21 '19 at 21:31
• @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$... – poncho Apr 21 '19 at 22:03