Cryptography
Zero byte header in RSA-OAEP vs. RSA-PSS
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?
Solution
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.
Comments (5)
- +0 – So you mean, that
emBitsis 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$? — Apr 11, 2017 at 16:02 - +1 – 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}$. — Apr 11, 2017 at 20:50
- +0 – 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 == 80in hexadecimals. — Apr 11, 2017 at 20:53 - +0 – Thanks. I wonder why they wrote it that complicated in the RFC and have not made it as obvious as in the OAEP part. — Apr 12, 2017 at 08:45
- +0 – @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. — Apr 12, 2017 at 11:01