2
$\begingroup$

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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer! I'm actually much interested in the composite case too. And I read your nice explanation of the "textbook RSA" before - it's very clear. Of course, a more correct padding scheme with a pre-hashing resolves many of those problems, but would be interesting to know if there's anything actually proven in the that "composite" case too... $\endgroup$ – Max Aug 29 '17 at 16:31
  • 1
    $\begingroup$ A variety of references on that topic can be found in these slides by Kenny Paterson from RWC 2013. The story is much more complex, of course! I don't know whether any of the references covers the specific case of (RSAES-OAEP, RSASSA-PSS), although Haber & Pinkas, ‘Securely combining public-key cryptosystems’, ACM CCS'01 might address it. (If that's paywalled, break down the wall.) $\endgroup$ – Squeamish Ossifrage Aug 29 '17 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.