# [cryptography] RSA signatures without padding

Filip Paun paunfilip at gmail.com
Fri Jul 10 19:42:05 EDT 2015

Hello,

On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:

> On Fri, Jul 10, 2015 at 4: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
>
> This is a bad idea.
>

Specifically, I am interested in the reasons why this is a bad idea for the
case where e = 2^16+1 and the hash is SHA256. Also, it's important to point
out that given my particular use case, an attacker can only see a few
pre-computed signatures and cannot generate any new signatures by using the
signer as a oracle.

> Note that the Full-Domain Hash (FDH) signature scheme would use a hash
> mapping the message to all of Z*_N, where here you have a hash mapping
> to the (much smaller) space of 256-bit strings.

My first impression was similar to yours where it just didn't feel right to
exponentiate a 256-bit number instead of a 2048-bit number. So now I'm
trying to search for an actual proof for why this would be bad.

> The problem is that this makes attacks based on factoring H(m) (in
> your case a 256-bit number rather than a 2048-bit number) and then
> using multiplicative properties of RSA much easier. The size of e is
> irrelevant.
>

Not sure what you mean by factoring H(m). Why would an attacker try to
factor H(m)? Do you instead mean finding the e-th root of H(m)? (My
assumption is that finding e-th roots in mod N is hard as claimed in RFC3447
<https://tools.ietf.org/html/rfc3447#section-8.2>.)

Thanks,
Filip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150710/6a76bc2a/attachment.html>