Raw RSA

James Muir jamuir at scs.carleton.ca
Fri Sep 8 14:48:49 EDT 2006


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



More information about the cryptography mailing list