6
$\begingroup$

RSA signatures are implemented by encrypting the padded hash with the private key.

Why not take the approach RSA-KEM is using by removing the padding entirely and replacing the hash with a XOF that would produce the m value in range [1, n-1].

XOF is just a hash with arbitrary output length.

Why hasn't it been done this way?

$\endgroup$
1

2 Answers 2

4
$\begingroup$

Why hasn't it been done this way?

It has been "done" but is sadly not a widely deployed scheme. This scheme is sometimes called RSA-FDH: RSA full domain hash. It's a general construction that works with any trapdoor one-way permutation, but so far, we don't have anything as practical as RSA).

Here's an example of its use in a practical construction, although they don't use an XOF.

This is also a secure scheme in the sense of strong unforgeability, assuming the RSA inversion problem is hard and the hash function "behaves" like a random oracle.

$\endgroup$
4
$\begingroup$

Two preliminary remarks on the question's

RSA signatures are implemented by encrypting the padded hash with the private key

  • The terminology "encrypt with the private key" is improper. That could be e.g. "apply the private-key textbook RSA permutation". At issue is that public key encryption is always with the public key, because the goal of encryption is to make what's encrypted unintelligible to adversaries (and the public key, which adversaries know, allows to undo the private-key textbook RSA permutation).
  • Not all standard RSA signature schemes work in this way, see RSA(SSA)-PSS below.

Why hasn't (RSA signature) been done (with the hash and padding replaced by a XOF)?

That's for historical reasons only:

$\endgroup$
3
  • 1
    $\begingroup$ One interesting note on the last point. I believe Coron's impossibility result is generic to any trapdoor permutation, and there are subclasses of trapdoor permutations for which a tight proof is possible. So, it's probably an open question for RSA whether assumptions are reasonable to allow certain RSA parameters to enjoy tight proofs. $\endgroup$ Jan 19 at 12:28
  • 1
    $\begingroup$ RSA encryption and decryption are identical, IIRC, so "encrypt with private key" is fine, but only for RSA. You can't encrypt with an ED25519 private key, for example. $\endgroup$ Jan 19 at 16:29
  • 2
    $\begingroup$ @user253751: in some definitions of textbook RSA, encryption and decryption are identical. But even then we do no "encrypt with private key", for we could decrypt with public key, thus anyone could decrypt, which goes against what encryption does. And, in RSA as typically practiced, encryption and decryption differ. 1) For efficiency, decryption often uses the factorization of the modulus, which then is in the decryption/private key. That's never the case for encryption/public key. 2) Encryption/public exponent is typically small (e.g. 65537). Decryption/private exponent is always large. $\endgroup$
    – fgrieu
    Jan 19 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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