Raw RSA

[Hal Finney]

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 majordomo at metzdowd.com