1
$\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?

$\endgroup$
  • $\begingroup$ Signatures are not "decrypted", so no, the same argument does not apply. $\endgroup$ – fkraiem Apr 11 '17 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 '17 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 '17 at 15:49
  • $\begingroup$ RSA signing is not RSA decryption. $\endgroup$ – fkraiem Apr 11 '17 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 '17 at 8:26
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.

$\endgroup$
  • $\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 '17 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 '17 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 '17 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 '17 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 '17 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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