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.

  • 2
    $\begingroup$ Does the RSA-PSS is not enough for you? $\endgroup$
    – kelalaka
    Feb 5, 2019 at 7:22
  • 1
    $\begingroup$ "provably secure in the random oracle model"... I thought the random oracle model had fallen out of favor. Isn't the random sponge model the preferred model for analyzing protocols based on hash functions nowadays? $\endgroup$
    – kasperd
    Feb 5, 2019 at 12:47

2 Answers 2


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.

  • $\begingroup$ Thank you. This technique seems to be working perfectly. $\endgroup$
    – Tabish Mir
    Feb 6, 2019 at 5:31

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.

  • $\begingroup$ While that would address the problem I have, I would like a method of extending the hash output based on any simpler hash function (SHA256) in my case. $\endgroup$
    – Tabish Mir
    Feb 6, 2019 at 5:34

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.