Is RSA signature as strong as the RSA encryption?

Question

Is it proven that breaking RSA signature is as hard as breaking the RSA encryption, considering the same key size?

I know that they both are based on the RSA function, but I believe that, as always with cryptography, the answer can't be that simple.

First, technically, RSA signing and RSA encryption use different exponents: the former uses a private exponent, and the latter uses a public exponent (which is typically smaller).

Second, padding schemes do matter - but I'm assuming in my question that a "good" padding scheme is used - for instance, for signatures it's RSA-PSS or RSASSA-PKCS1-v1_5 (the latter is non provably correct, but it's still widely deployed and not actually cracked yet).

Third, does the answer depend on the allowed usages of the RSA keys in question? I.e. comparing situations: a) having two keys, one restricted to only Digital signature, and another to only Key/Data encipherment, b) having a single key, with both usages allowed.

Any references to books/standards/conference presentations will be appreciated. Thanks!

Answer 1

Breaking RSAES-OAEP encryption for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization. (Likewise RSA-KEM, which is much simpler.)

Forging RSASSA-PSS signatures for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization. (Likewise RSA-FDH, which is much simpler.)

(Forging Rabin-Williams signatures—which involves square roots, not odd roots—for generic hash functions is as difficult as factoring a large composite of unknown large prime factorization.)

This is the story for the individual cryptosystems RSAES-OAEP under a key independent of RSASSA-PSS under another key. The security of a composite cryptosystem (RSAES-OAEP, RSASSA-PSS) under the same key, in which the adversary can witness decryptions and signatures of arbitrary messages, requires its own analysis: security of RSAES-OAEP and RSASSA-PSS individually does not imply security of the composite scheme.

The standard pathological example, in the scheme I like to call do you even RSA, bro‽, is that if I want to decrypt a ciphertext $c \equiv m^e \pmod n$, and if I can ask you to sign the message $c$, then your signature is $s \equiv c^d \equiv m^{ed} \equiv m \pmod n$, so you just unwittingly decrypted $c$ for me.

Are there attacks on (RSAES-OAEP, RSASSA-PSS) under a single key? Unlikely, but I don't have a handy citation for a reduction of security to the RSA problem.