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$
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$
  • 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 '16 at 5:43
  • $\begingroup$ are the signature key and verify key are same in this case? $\endgroup$ – danny Jun 7 '17 at 9:57

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.