RSA signatures without padding?

Question

Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows:

$H = H(M)$, $H(M)$ being the SHA-256 of the message $M$
$S = H^d \bmod N$

Assume $N = pq$ is properly generated and $d$ is the RSA private key. And I verify the signature as follows:

$S^e \bmod N = H'$

where $H'$ is the SHA-256 of the message to be authenticated. Assume $e$ is the RSA public key.

Since I've not used any padding then are there any flaws with the above approach? What if $e = 3$? What if $e = 2^{16}+1=65537$?

Your guidance is much appreciated.

Answer 1

One property that this unpadded system is that it is homomorphic; if $A^d = X$ and $B^d = Y$, then we know that $(AB)^d = XY$, and it doesn't matter if we don't know what $d$ is. More generally, if we have a collection of $H_1, H_2, H_3, ... H_n$, and a collection of signatures $S_1, S_2, S_3, ..., S_n$, then for any set of integers $e_1, e_2, e_3, ..., e_n$, we have:

$$(S_1^{e_1} S_2^{e_2} S_3^{e_3} ... S_n^{e_n})^d = H_1^{e_1} H_2^{e_2} H_3^{e_3} ... H_n^{e_n} $$

So, if we take a large collection of valid message and signatures pairs, hash the messages, and then factor the hashes. Then, we look for multiplicative combinations of those hashes that yield a hash that we haven't seen (going through a long list of messages to hash); if we find a message that hashes to a value we know a linear combination of, we can immediately deduce the signature.

The attack works for any value of $e$