Question

When using secure hash functions in an RSA signature, why do we sign the hash Sign (H (m)) instead of taking the take the hash H (Sign (m)) ?

Answer 1

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 ZN. Let us assume that it requires k such signatures and write the message m=(m1,…, mk) and the overall signature will be σ=(σ1, …, σk), i.e., k RSA signatures. Now without any additional measures anyone getting to hold (m, σ) can manipulate the message and adopt the signature by 1) swapping any pair of submessage mi, 1 ≤ i ≤ k and corresponding subsignature σi or 2) dropping a submessage and corresponding subsignature.

As an example for swapping lets say we have m=(m1, m2, m3) and thus σ=(σ1, σ2, σ3), i.e., 3 indepenendet RSA signatures for a message consisting of 3 blocks, then an adversary who gets (m, σ) can simply swap, for instance to m' = (m2, m3, m1) and σ′=(σ2, σ3, σ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, they are susceptible to existential forgeries. Let (e, N) be the public signature verification key of RSA, then one can randomly choose a signature σ ∈ ZN and compute the corresponding message as m≡σe(modN).

Note that given an RSA signature σ, a message m and a public verification key (e,N), the signature verification for the textbook RSA signature will be to check: m≡ σ^e(modN).

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 ZN. 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).