Alexander Klimov asks: > If an attacker is given access to a raw RSA decryption oracle (the > oracle calculates c^d mod n for any c) is it possible to extract the > key (d)?
This is equivalent to asking whether factoring reduces to RSA inversion. That is, given access to an RSA inversion oracle, can you factor the modulus? (Factoring the modulus is equivalent to finding d.) Then see "Breaking RSA May Not Be Equivalent to Factoring" by Boneh and Venkatesan, Eurocrypt 98. Abstract (with my added emphasis): "We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. THUS, IN EFFECT AN ORACLE FOR BREAKING RSA DOES NOT HELP In FACTORING INTEGERS. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the RSA System." So the answer would appear to be no, an oracle for RSA does not help in factoring and therefore will not reveal d. See also http://citeseer.ist.psu.edu/bellare01onemorersainversion.html "The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme" by Bellare et al for some discussion of this issue. Hal Finney --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
