# Why hash the message before signing it? Digital signature with RSA

Here's a method to sign the message with RSA: Why hash the data before signing it? Why not sign the whole message? It'll save time if you sign the hash value, but I've heard there are also security issues?

-

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho:

Reordering

If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires $k$ such signatures and write the message $m=(m_1,\ldots,m_k)$ and the overall signature will be $\sigma=(\sigma_1,\ldots,\sigma_k)$, i.e., $k$ RSA signatures. Now without any additional measures anyone getting to hold $(m,\sigma)$ can manipulate the message and adopt the signature by 1) swapping any pair of submessage $m_i$, $1\leq i\leq k$ and corresponding subsignature $\sigma_i$ or 2) dropping a submessage and corresponding subsignature.

As an example for swapping lets say we have $m=(m_1,m_2,m_3)$ and thus $\sigma=(\sigma_1,\sigma_2,\sigma_3)$, i.e., 3 indepenendet RSA signatures for a message consisting of 3 blocks, then an adversary who gets $(m,\sigma)$ can simply swap, for instance to $m'=(m_2,m_3,m_1)$ and $\sigma'=(\sigma_2,\sigma_3,\sigma_1)$, which is a forgery, but clearly a valid signature.

Existential forgery

If you do not use a redundancy scheme for messages prior to signing within RSA (textbook RSA signatures), they are susceptible to existential forgeries. Let $(e,N)$ be the public signature verification key of RSA, then one can randomly choose a signature $\sigma \in Z_N$ and compute the corresponding message as $m\equiv \sigma^e \pmod N$.

Note that given an RSA signature $\sigma$, a message $m$ an a public verification key $(e,N)$, the signature verification for the textbook RSA signature will be to check: $m\stackrel{?}{\equiv} \sigma^e \pmod N$.

Clearly, this check will hold for the computed forgery by construction. Observe, however, that the adversary cannot control what the message $m$ will exactly be, in particular it will be a random element of $Z_N$. However, this may be enough in some applications, i.e., when only signing random numbers. Applying a redundancy scheme to messages, i.e., hashing and padding prior to signing, renders so computed messages useless.

Final Remarks

Consequently, textbook RSA signatures should not be used and standardized padding methods for RSA involve hashing and padding the message.

In general this approach is known as the hash-then-sign paradigm.

-
Addition: If one hashes then apply the naked RSA signature function $x\mapsto x^d\bmod N$ without padding, one stands vulnerable to multiplicative forgeries in a chosen-message setup using an attack devised by Desmedt and Odlyzko, combining signature of messages which hashes are smooth into the signature of another such message. Even with proper padding on the signing side, implementations of signature verification have been vulnerable to incorrect verification of the padding; here's an example. –  fgrieu Jan 8 at 8:16