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