[cryptography] RSA question

Ralf-Philipp Weinmann ralf at coderpunks.org
Tue Aug 31 08:45:14 EDT 2010


On 08/31/2010 09:07 AM, Justin Ferguson wrote:
> Hi,
>   
Hi Justin,
> I'm not really much of a crypto guy so when the details come up it's often kind of hard for me to entirely wrap my head around. That said, I'm currently dealing with a situation where the public key, plain-text and cipher-text are all known to an attacker; furthermore, the random oracles/et cetera employed during the OEAP scheme are also known to the attacker. 
this is a very, very common situation (knowing the public key and the
actual encryption scheme [with parameters] used): Since you know the
public key & scheme and can choose arbitrary plaintexts, you can also
produce corresponding ciphertexts for them...
> Furthermore, the attacker can modify those
> values (id est random oracle values of zero, or whatever the attacker
> wants) and repeat the plain-text to cipher-text process as they see
> fit. 
This is called a adaptive chosen-text scenario in cryptographer's circles.
> Furthermore, the key length exceeds the length of the message. Basically, only the private key is not under the attackers control.
>   
OK. That's good for the defender :)
> From that, what I am getting is that this is virtually the same as RSA without the padding scheme and should be vulnerable due to it being a deterministic algorithm; 
The padding scheme is crucial! This is what provides the security over
other RSA variants; also, n.b.: the OAEP padding is randomized.
> however my question is how much does it really reduce the complexity? Is an attack against this even feasible in any practical terms?
>   
The proof is in the pudding, errr... padding here. For RSA-OAEP Fujisaki
et al. proved that OAEP provides semantic security against adaptive
chosen-text attacks in a CRYPTO 2001 paper for which you can find the
extended version (published in the Journal of Cryptology) here:

http://www.di.ens.fr/~pointche/Documents/Papers/2004_joc.pdf
<http://www.di.ens.fr/%7Epointche/Documents/Papers/2004_joc.pdf>

Finally, please be aware that proofs need not necessarily be correct, as
has been demonstrated by an earlier attempt to prove OAEP secure [0,1]
which was later found to be flawed by Shoup [2].

Hope to have helped,
RPW

[0] S. Goldwasser and S. Micali: Probabilistic Encryption.
    Journal of Computer and System Sciences,  28:270-299, 1984

[1] C. Racko
 and D. R. Simon: Non-Interactive Zero-Knowledge
    Proof of Knowledge and Chosen Ciphertext Attack. In CRYPTO 1991,
    LNCS 576, pages 433-44, Springer-Verlag, Berlin, 1992

[2] V. Shoup. OAEP Reconsidered. In CRYPTO 2001, LNCS 2139,
    pages 239-259. Springer-Verlag,  Berlin



More information about the cryptography mailing list