[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:


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,

[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