2
$\begingroup$

PKCS#1 v2.1/RFC3437 defines the OAEP padding mode for encryption and the PSS for signature padding. Both schemes are based on the generic constructions not specifically tailored to RSA by Rogaway & Bellare.

One of the alterations done for RSA-OAEP is, that the actual padding is only done to a length of $n-1$ (where is the octet length of the modulus) and a single zero byte is prepended to the whole string. This is done, since a message padded to $n$ bytes could be larger than the modulus, thus creating an ambiguity when decrypting.

My question is: The same argument could be raised for RSA-PSS, but here no zero byte is prepended to the padded hash. Why is that not necessary for signatures?

Improve this question
$\endgroup$
5
  • $\begingroup$ Signatures are not "decrypted", so no, the same argument does not apply. $\endgroup$
    – fkraiem
    Apr 11, 2017 at 15:16
  • $\begingroup$ The padded messages are processed by the same encryption and decryption function in RSA. So if $modulus<PSS(M)<2^n$ the same problems should arise as with OAEP, shouldn't they? $\endgroup$
    – mat
    Apr 11, 2017 at 15:19
  • $\begingroup$ Yes, they should. Anything where the input to the modular exponentiation can be equivalent to another value (for instance negative or larger than the modulus) will result in ambivalence (or just plain verification failure) during verification. $\endgroup$
    – Maarten Bodewes ♦
    Apr 11, 2017 at 15:49
  • $\begingroup$ RSA signing is not RSA decryption. $\endgroup$
    – fkraiem
    Apr 11, 2017 at 16:04
  • $\begingroup$ @fkraiem Technically ,the actual RSA operations are just encryption/decryption. What makes them different is the different padding/armoring needs as done by OAEP and PSS. That is also clearly stated in the link you provided. $\endgroup$
    – mat
    Apr 12, 2017 at 8:26

1 Answer 1

Reset to default
1
$\begingroup$

I think it actually is, lets read through chapter 8.1.1 Signature generation operation:

EMSA-PSS encoding: Apply the EMSA-PSS encoding operation (Section
9.1.1) to the message M to produce an encoded message EM of length
\ceil ((modBits - 1)/8) octets such that the bit length of the
integer OS2IP (EM) (see Section 4.2) is at most modBits - 1, where
modBits is the length in bits of the RSA modulus n:  

    EM = EMSA-PSS-ENCODE (M, modBits - 1).

Note that the octet length of EM will be one less than k if
modBits - 1 is divisible by 8 and equal to k otherwise.  If the
encoding operation outputs "message too long," output "message too
long" and stop.  If the encoding operation outputs "encoding
error," output "encoding error" and stop.

Now the sentence "Note that the octet length of EM will be one less than k if modBits - 1 is divisible by 8 and equal to k otherwise." clearly indicates that this is similar to OAEP encryption.

Furthermore, if you look at the encoding operation in 9.1.1:

11. Set the leftmost 8emLen - emBits bits of the leftmost octet in
maskedDB to zero.

12. Let EM = maskedDB || H || 0xbc.

You'll see that the leftmost (most significant bits) are set to zero.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So you mean, that emBits is not actually meant to be the modulus length (2048) but has to be manually calculated such that the encoded message doen not get too long. Something like $emBits = max_n 2^n<modulus$? $\endgroup$
    – mat
    Apr 11, 2017 at 16:02
  • 1
    $\begingroup$ Yes, "... such that the bit length of the integer OS2IP (EM) (see Section 4.2) is at most modBits - 1 ... ". So for 2048 bits the bit length is at most 2047 bits. Then comes "Note that the octet length of EM will be one less than k if modBits - 1 is divisible by 8 and equal to k otherwise.". The octet length of K, k is 256 bytes for a 2048 key / modulus size. But EM is one less so that would be 255 bytes. In other words, when interpreted as a number, the maximum value represented by EM will be $2^{2040}$. $\endgroup$
    – Maarten Bodewes ♦
    Apr 11, 2017 at 20:50
  • $\begingroup$ Note that the total size of EM can still be 256 bits, it's just that the leftmost bits are set to zero (which results in the same value as the bits not being present at all, we're talking unsigned big endian integer representations after all). 0080 == 80 in hexadecimals. $\endgroup$
    – Maarten Bodewes ♦
    Apr 11, 2017 at 20:53
  • $\begingroup$ Thanks. I wonder why they wrote it that complicated in the RFC and have not made it as obvious as in the OAEP part. $\endgroup$
    – mat
    Apr 12, 2017 at 8:45
  • $\begingroup$ @mat Yeah, I agree that it hasn't been written very comprehensively. Then again, it is at least clear to me that there won't be any issues with modular exponentiation. However, if I had to implement the scheme I might have to perform some testing against (intermediate) test vectors the way it is written. OAEP indeed seems to be described more clearly. $\endgroup$
    – Maarten Bodewes ♦
    Apr 12, 2017 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.