RSA signatures without padding by using XOF output in range [1, n-1]

Question

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?

Answer 1

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.

Answer 2

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:

• RSA signature was standardized long before there was any XOF defined.
• No attack on proper implementation of RSASSA-PKCS1-v1_5 (hash, pad, apply private-key permutation) was ever found; same for the earlier PKCS#1 signature when applied to a hash (resulting in a slightly different padding); or other similar padding schemes, like ANS X9.31.
• The concept of making a hash (nearly) as wide as the public modulus, as the question considers, is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction to the RSA problem. It was introduced by Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin (in proceedings of EuroCrypt 1996) only after RSA signature got standardized. And that paper gave a security reduction for RSA-FDH requiring a large RSA modulus. It recommended a randomized signature padding (much like in RSA encryption), RSA-PSS, leading to a much tighter security reduction for common RSA modulus size. Thus RSA-FDH was not standardized, and RSASSA-PSS was added to PKCS#1 in version 2 (and has some level of adoption).
• From a practical perspective, it made no difference that Jean-Sébastien Coron later improved the security argument for RSA-FDH in On the Exact Security of Full Domain Hash (in proceedings of Crypto 2000) and Optimal Security Proofs for PSS and Other Signature Schemes (in proceedings of EuroCrypt 2002).