# Why hash or salt when signing?

I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV.

Why is that needed?

-

A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this:

Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA signature" (without a hash and any padding), you now have a message $m$ with a fitting signature $s$.

With a hash, the signature checking equation is $H(m) \equiv s^e \mod n$ instead of $m \equiv s^e \mod n$, and this does not allow to create a message $m$ fitting to an arbitrary signature $s$ (assuming the hash function is preimage-resistant). Beware however that it is remains possible to create working $(m,s)$ pairs given the capability to obtain the signatures $s_j$ of chosen messages $m_j\ne m$, using an attack devised by Desmedt and Odlyzko (see section 3 of this paper).

(The padding scheme normally present in signatures serves the same purpose, and is designed to also resist chosen-messages attacks.)

-
Thanks for the answer. –  ispiro Apr 30 '12 at 14:32

Signing a hash is cheaper than signing the whole document. RSA is relatively costly, and, as long as the hash function is not weak, there isn't any practical difference in security between signing the whole plaintext and signing its hash, because the hash uniquely identifies the plaintext.

Wikipedia says:

There are several reasons to sign such a hash (or message digest) instead of the whole document.

• For efficiency: The signature will be much shorter and thus save time since hashing is generally much faster than signing in practice.
• For compatibility: Messages are typically bit strings, but some signature schemes operate on other domains (such as, in the case of RSA, numbers modulo a composite number N). A hash function can be used to convert an arbitrary input into the proper format.
• For integrity: Without the hash function, the text "to be signed" may have to be split (separated) in blocks small enough for the signature scheme to act on them directly. However, the receiver of the signed blocks is not able to recognize if all the blocks are present and in the appropriate order.
-
Thanks. So if my message is short enough – there's no need. Correct? –  ispiro Apr 27 '12 at 13:58
@ispiro: yes, theoretically. In practice hash is (usually?) still computed (e. g. GPG). –  Mischa Arefiev Apr 27 '12 at 14:45