What do you think about this signature scheme using RSA with 4096 bit keys?

Being R pseudorandom padding, fixed length (4096 - 512 bits):

RSApriv(R || SHA512(M))

I know that it's not as secure as RSASSA-PSS, but it looks better than RSASSA-PKCS1 to me (because of the random padding).

Am I missing anything important?

Thanks in advance.

  • Does 4096 - 512 represent 3584 or the range 4096,4095,4094,...,514,513,512?
    – user49075
    Commented Feb 3, 2015 at 9:53
  • I meant that the length of the random padding (R) will be 3584 bits (448 bytes). Commented Feb 3, 2015 at 12:12
  • In that case, int(R || SHA512(M)) may be greater than the modulus.
    – user49075
    Commented Feb 3, 2015 at 12:18
  • I don't understand. AFAIK, if the key length is 4096 bit, the "encoded message" should be 4096 bit long. Padding/armoring/encoding is used to create "encoded messages" (derived from the original message) with this length. For example, RSASSA-PKCS1 uses EMSA-PKCS1 encoding, the standard states: "Apply the EMSA-PKCS1-v1_5 encodinga operation to the message M to produce an encoded message EM of length k octets (where k is the length in octets of the RSA modulus n)." Commented Feb 3, 2015 at 15:46
  • A google search doesn't find that phrase. Is the standard you're referring to publicly available?
    – user49075
    Commented Feb 3, 2015 at 19:29

1 Answer 1

  1. If you want a simple yet secure signature scheme, take a look at Full-Domain-Hash (FDH).
  2. Properly randomized padding (as in PSS) can strengthen the scheme against chosen-plaintext attacks. AFAIK the main effect is that it improves the tightness of the security proof a bit, which I consider a relatively small advantage.

    But since the attacker can choose arbitrary values as padding, improperly randomized padding can also cause weaknesses. Yours allows the attacker control over most of the message.

    Assuming you're using big-endian encoding, the message hash will land in the least significant bits in your scheme. The attacker has full control over all the other bits. This means the padding is clearly weaker than even PKCS#1v1.5 padding.

    I expect practical forgeries, at least for small values of e.

  • Ok, I see. I'll implement something similar to EMSA-PKCS1, the requirements for this system are not so high. Thanks for your comments. Commented Feb 3, 2015 at 19:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .