[cryptography] RSA signatures without padding

Jeffrey Walton noloader at gmail.com
Fri Jul 10 17:42:20 EDT 2015

> Suppose I have a message M for which I generate an RSA-2048 digital
> signature as follows:
>   H = SHA-256(M)
>   S = H^d mod N
> Assume N = p*q is properly generated and d is the RSA private key.
> And I verify the signature as follows:
>   S^e mod N == H'
> where H' is the SHA-256 of the message to be authenticated. Assume e is the
> RSA public key.

I *think* the signature could be malleable. That is, you could get
both S to verify, and N - S to verify. Whether its a problem (or not)
depends on your expectations.

> 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?

Bernstein provides a really good history in "RSA signatures and
Rabin–Williams signatures: the state of the art",
http://cr.yp.to/sigs/rwsota-20080131.pdf. He discusses why various
steps are performed, like hashing the message rather than using the
message directly.

You should be OK with 3 or even 2, though it complicates signing.
Taking from Bernstein:

    State-of-the-art systems use exponent 2 rather than
    exponent 3. This speeds up verification, and improves
    the signature-compression and signature-expansion
    features discussed in subsequent sections. The signer’s
    secret primes p and q are chosen from 3 + 4 Z to
    simplify signing


More information about the cryptography mailing list