# Why do we need to compute message digest of a message first while signing it?

Why it is more efficient to compute a message digest of message and digitally sign it then, rather than sign the message directly?

One of the main reasons for hashing is that hashing destroys any algebraic structure that is hidden in the signatures. If you don't hash, then in most signature schemes the messages will satisfy some algebraic relation. A typical example is that

$$Sign(m_1m_2)=P(Sign(m_1),Sign(m_2))$$

meaning that the signature of a product/concatenation/whatever of two messages is a polynomial in the signatures of the individual messages. For RSA, we would have $P(x,y)=xy$. These dependencies can be more complicated and as long as they are efficiently computable, we have problems. What a hash function does, informally speaking, is that in terms of bit strings, $H(m_1),H(m_2)$ and $H(m_1m_2)$ become totally unrelated, therefore it removes any sort of efficiently computable dependency of $H(m_1m_2)$ on $H(m_1)$ and $H(m_2)$.

The point of removing these dependencies is that it prevents us from using previously seen message/signature pairs for forging signatures on new messages. This is what breaks EUF-CMA security. Therefore, hashing is not just an issue of efficiency, but also one of security.

Another issue is of course that the message to be signed needs to be of the proper form before a signature is issued. Since a signature scheme typically operates on elements in some group $G$, there needs to be a function that takes a message $M\in\mathcal{M}$ from the message space and maps it to a group element. Therefore, we need some function $H:\mathcal{M}\to G$ that allows us to transfer messages to a format that we can sign. For RSA we need to take an arbitrary bitstring and then turn it into an integer modulo $N$. The kind of a function that does this in a way you want is precisely a cryptographic hash function.

There is actually a theoretical issue here as well. It's very very hard to build a EUF-CMA secure signature scheme without relying on a hash function (meaning not proving security in the Random Oracle Model). There are some quite efficient structure-preserving signature schemes that are EUF-CMA secure and don't use a hash function, but they rely on the generic group model. To my knowledge, no practical construction is known to date, which only depends on a standard assumption.

Because signing is very expensive and hashing is orders of magnitude faster. If your message was a gigabyte, for instance, it would take many minutes to sign it. With hash-then-sign it is only a few seconds.

Also without the hash the signature of a message would be as long as the message itself, which can be inconvenient.

• does it serve any security purpose apart from improving efficiency? – Vinnie Nov 8 '14 at 5:34

To add another point to what Travis has already mentioned, some signature schemes like textbook RSA signature is not EUF-CMA secure under random oracle model, but Hashed-RSA signature is. So, even for a small message is would would be better to hash-then-sign, though it is not an efficiency concern.

• can you shed some light on EUF-CMA here? – Vinnie Nov 11 '14 at 23:53
• @Vinto EUF-CMA stands for Existential Unforgeability under Chosen Message Attack. Consider this as a game between adversary $\mathcal{A}$ and challenger $\mathcal{B}$. $\mathcal{B}$ generates a (pk, sk) pair and gives the pk to $\mathcal{A}$. Then $\mathcal{A}$ asks polynomial (in the security parameter) many signature queries (say for m$_{1}$ to m$_{q}$) to the oracle and gets back their signatures. Then $\mathcal{A}$ has to produce a valid signature on m*, which she has not queried before. $\mathcal{A}$ wins the game if she can do it. Advantage($\mathcal{A}$) := Prob($\mathcal{A}$ wins). – Bitswazsky Nov 12 '14 at 6:42

Alongside the other arguments: signing (with RSA) means exponentiating it modulo $N$ (with power $d$, the secret exponent). So anything you sign that way must be of bitsize smaller than $N$, and hashing (plus padding it) makes it so. Otherwise you'd have to split the message in small chunks and sign them, and concatenate the chunks etc. This would make the signature at least as long as the message and also susceptible to all sorts of forgery attacks, possibly (reordering the message and its signature blocks would remain valid, e.g.). Hashing first enables the signing itslef, and due to the non-colission properties of the hash also makes forgeries harder.

Because most asymetric (that's what you need) crypto algorithms can not encrypt arbitrary long texts. However if you limit yourself to the (short) length of a digest (Hahs). Then the message text is short enough to be put throgh the asymetric crypto and it works.