[41703] in cryptography@c2.net mail archive
Re: Raw RSA
daemon@ATHENA.MIT.EDU (James Muir)
Sat Sep 9 14:28:50 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 08 Sep 2006 14:48:49 -0400
From: James Muir <jamuir@scs.carleton.ca>
To: cryptography@metzdowd.com
In-Reply-To: <20060907221255.109C714F6BD@finney.org>
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@metzdowd.com
