Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Here's a method to sign the message with RSA: http://upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Digital_Signature_diagram.svg/800px-Digital_Signature_diagram.svg.png 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?

share|improve this question
add comment

2 Answers 2

up vote 9 down vote accepted

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, as it clearly is 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$ and 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 forgery by construction. Observe, however, that the adversary can not control what the message $m$ will exactly be. In particular, it will be a random element of $Z_N$. However, this may be sufficient in some applications, e.g., when only signing random numbers when issuing some tokens. Applying a redundancy scheme to messages, i.e., hashing and padding prior to signing, renders so computed forged signatures useless in practice.

Final Remarks

Consequently, textbook RSA signatures must not be used and instead standardized padding methods for RSA involving hashing and padding the message must be used. Then, RSA signatures provide strong security guarantees (UF-CMA security).

share|improve this answer
add comment

Well, one reason to hash the data before signing it is because RSA can handle only so much data; we might want to sign messages longer than that.

For example, suppose we are using a 2k RSA key; that means that the RSA operation can handle messages up to 2047 bits; or 255 bytes. We often want to sign messages longer than 255 bytes. By hashing the message to something small, and then signing the hash, we get around the problem of message length. Now, we could also solve this problem by breaking up the message to smaller chunks, and signing each chunk; however this adds a great deal of complexity and expense for no particularly good reason.

I would like to add a warning not directly related to your question: that image you showed is simplified, and is missing an important piece of the RSA signature process. After you perform the hash, it is essential that you pad the hash out before you give it to what they have labeled the 'encrypt hash with the signer's private key' step. Conversely, after the signature verifier has used the signer's public key, they need to verify that the padding in the 'decrypted' message looks valid (in addition to the hash being the expected value). There are known weaknesses that result by not performing the padding correctly.

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.