1
$\begingroup$

I am trying to understand RSA digital signature algorithm. I am planning to follow these steps:

Sign algorithm:

  1. Take some message $m$
  2. Create digital signature using my private key $[d,n]$: $s = S_a(m) = m^d \bmod n$
  3. Pass my message and signature $[m,s]$

Verification algorithm:

  1. Accept $[m,s]$
  2. Take public key $[e,n]$
  3. Retrieve message: $m' = P_a(s) = s^e \bmod n$
  4. Check authenticity of signature and message immutability by comparing $m$ and $m'$

But I also want to use hashing. I plan to sign not the message $m$, but its hash: $m_{\rm hashed}$. Sign algorithm will probably be changed to:

Sign algorithm (with hashing):

  1. Take some message $m$
  2. Generate hash of message: $m_{\rm hashed}$
  3. Create digital signature using my private key $[d,n]$: $s = S_a(m_{\rm hashed}) = m_{\rm hashed}^d \bmod n$
  4. Pass my message and signature $[m,s]$

I have question about verification steps. Specifically about checking message authenticity in step 4.

Verification algorithm (with hashing):

  1. Accept $[m,s]$
  2. Take public key $[e,n]$
  3. Retrieve message: $m' = P_a(s) = s^e \bmod n$
  4. Check authenticity of signature and message immutability by comparing $m$ and $m'$ ???

Before using hashing we could check authenticity and immutability by comparing $m$ and $m'$. But in this case after step 3, we will get $m'$ as a hashed version (not as original message). How can we compare $m$ and $m'$ if $m$ is original message and $m'$ is hashed version (taking into account that hashing is irreversible and there is no way to decrypt hash back)?


My question: what is the correct algorithm? How to correctly use RSA for digital signature with hashing?

$\endgroup$

1 Answer 1

2
$\begingroup$

You're missing two things:

First off, we don't try to retrieve the message from the hash; as you correctly point out, that's impossible. Instead, what we do is (using your notation):

  1. Accept $[m,s]$
  2. Take public key $[e,n]$
  3. Retrieve the hashed message: $m'_{hashed} = P_a(s) = s^e \bmod(n)$
  4. Generate the hash of the message being verified $m_{hashed} = Hash(m)$
  5. Check authenticity of signature and message immutability by comparing $m_{hashed}$ and $m'_{hashed}$

If we assume that the hash function is collision resistant, that is, it is infeasible to find two distinct messages $M_a, M_b$ with $Hash(M_a) = Hash(M_b)$, then if $m_{hashed} = m'_{hashed}$, then either we've demonstrated a hash collision (which we assume is difficult), or $m = m'$.

The other thing you are missing is padding. We (should) never take output of a hash function, interpret it as an integer, and hand it off to the RSA function; if we do that, then an attacker could potentially take advantage of the homomorphic property of RSA, namely, $a^e \bmod n \times b^e \bmod n \equiv (ab)^e \bmod n$, look through a pile of signatures for hashes that happen to have common factors, and cobble together a signature to a new message (whose hash is made up of those common factors). Instead, we always apply a padding function to the hash output to turn it into a large (nearly as large as $n$) integer, and then apply the RSA function to that.

There are a number of padding methods known that are believed to be secure, including PSS and RSASSA-PKCS1-v1_5; the reference I gave you short get you started.

$\endgroup$
6
  • 2
    $\begingroup$ There is an exception to "We (should) never take output of a hash function, interpret it as an integer, and hand it off to the RSA function": when the hash is wide enough, including few bytes less than the public modulus (which excludes most common hashes). It is unclear exactly how wide is necessary; related. $\endgroup$
    – fgrieu
    Sep 27, 2016 at 5:43
  • $\begingroup$ are the signature key and verify key are same in this case? $\endgroup$
    – danny
    Jun 7, 2017 at 9:57
  • $\begingroup$ if hash is padded randomly to make it equal to n-bit length, and then encrypted with private key to generate signature, is it a secure and valid signature generation scheme? $\endgroup$
    – crypt
    Jan 27, 2023 at 5:54
  • $\begingroup$ @crypt: the problem would be, if the padding bits are random, then the forger could set them to anything he wants, and the signature would still be accepted (as long as the bits containing the hash are still valid). Would the forger be able to use the homomorphic properties of RSA to find a valid signature? I'm not sure off the top of my head - I wouldn't be confident that they couldn't $\endgroup$
    – poncho
    Jan 27, 2023 at 15:24
  • $\begingroup$ @poncho so one should use approved RSA signature schemes rather than doing this random pad to avoid any hidden issue? $\endgroup$
    – crypt
    Feb 1, 2023 at 4:32

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.