How to correctly use RSA for digital signature with hashing? I am trying to understand RSA digital signature algorithm. I am planning to follow these steps:

Sign algorithm:


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


Verification algorithm:


Accept $[m,s]$
Take public key $[e,n]$
Retrieve message: $m' = P_a(s) = s^e \bmod n$
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):


Take some message $m$
Generate hash of message: $m_{\rm hashed}$  
Create digital signature using my private key $[d,n]$: $s = S_a(m_{\rm hashed}) = m_{\rm hashed}^d \bmod n$
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):


Accept $[m,s]$
Take public key $[e,n]$
Retrieve message: $m' = P_a(s) = s^e \bmod n$
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?
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):


Accept $[m,s]$
Take public key $[e,n]$
Retrieve the hashed message: $m'_{hashed} = P_a(s) = s^e \bmod(n)$
Generate the hash of the message being verified $m_{hashed} = Hash(m)$
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.