How can I hash an input into an arbitrary domain point?

Question

I am trying to implement a signature scheme involving RSA signing of a message digest generated by SHA-$256$. I want to hash the input into an RSA domain point instead of the fixed $256$ bit digest generated by SHA.
Apparently, this can be achieved using a Full Domain Hashing

From the Wikipedia definition of Full Domain Hashing

In cryptography, the Full Domain Hash (FDH) is an RSA-based signature scheme that follows the hash-and-sign paradigm. It is provably secure (i.e., is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model. FDH involves hashing a message using a function whose image size equals the size of the RSA modulus, and then raising the result to the secret RSA exponent.

How would one go about practically implementing the following part of the FDH process:

hashing a message using a function whose image size equals the size of the RSA modulus

I have tried randomly padding the $256$ bit digest, however, it requires sending extra values to remove the padding before verification. I also looked at some papers on Random Oracles and FDH by Bellare and Rogaway(Paper 1,Paper 2) which are a little to esoteric for me and as such, I'm looking for simplified explanation of the process.

Answer 1

Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m||0)||h(m||1)||\cdots $, then take the leading n-bit. This way the hash value is deterministic and the size is arbitrary.

This is something like MGF1 defined in PKCS #1 v2.2, B.2.1.

Answer 2

Why don't you use an eXtendible Output Function (XOF) for that ?

For example, SHAKE-128, defined in the SHA-3 standard, allows you to hash a message and obtain as output as many bits as you want. This is flexible so that it can be easily adapted to the size of your RSA modulus.