Hal Finney wrote:
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.
Making practical conclusions from the Boneh & Venkatesan result is not a
very easy task. See Section 3 of the following
N. Koblitz and A. Menezes
Another Look at Provable Security II
http://www.cacr.math.uwaterloo.ca/~ajmenezes/publications/ps2.pdf
-James
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
