[cryptography] RSA signatures without padding

Michael Greene mgreene at securityinnovation.com
Fri Jul 10 18:45:54 EDT 2015

It is my understanding that, on a very basic level, using RSA without padding allows computing “valid” signatures for new messages by combining two existing signatures, because a^d * b^d == (a * b) ^ d

The use of sha256 in this case probably makes this task slightly more annoying, but by no means impossible - it raises the bar only to crafting a message m where Hm(m) == H(m1) * H(m2) mod N. With padding the scheme becomes H = (PAD(SHA256(M))) which makes the resulting signature probabilistic rather than deterministic, and combining signatures to create new signatures no longer works.

It is also my understanding that the malleability problem with textbook (i.e. unpadded) RSA relates to encryption/decryption rather than signing/verification, not signing/verification, but I could be wrong about that.
Michael Greene
Software Engineer
mgreene at securityinnovation.com

> On Jul 10, 2015, at 1:15 PM, Filip Paun <paunfilip at gmail.com> wrote:
> 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.
> 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?
> Your guidance is much appreciated.
> Thank you,
> Filip
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150710/ad47a6f2/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3298 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150710/ad47a6f2/attachment-0001.p7s>

More information about the cryptography mailing list