Cryptography
Updated Fri, 20 May 2022 19:51:03 GMT

# RSA Signing: SHA512 incompatible with PSS?

I am wrapping the RSACng class from the .Net API. Whilst unit testing, I run checks against an array of possibilities:

• Key Size = 1024, 2048, or 3072 bits
• Padding Mode = PKCS v1, or PSS (=PKCS v2?)
• Hash Algorithm = SHA-1, SHA256, SHA512

I test for all 3*2*3=18 possible configurations. All tests pass except one combination:

• Key size = 1024 bits
• Hash Algorithm = SHA512

Should this be expected, and how could have I anticipated it? So far, Google has not been my friend.

I also ran a similar batch of unit tests for RSA encryption, and noted a 1024 bits key is incompatible with OAEP-SHA1 and OAEP-SHA256 padding modes. I suspect the key is not large enought, but I was again unable to read some info as to why this was happening.

## Solution

Yes, this is expected, if the RSASSA-PSS signing code/test uses salt the width of the hash, which is customary. In that case, a $$h$$-bit hash (with $$h$$ multiple of 8) requires an RSA public modulus at least $$2h+9$$ bits.

That's semi-clearly stated in PKCS#1 v2.2, section 9.1.1, condition on enBits, with actual test in step 3. That's because the message representative needs to convey $$h$$ bits for the message hash, $$h$$ bits for the salt, $$8$$ bits for a one-byte identifier, and then some.

In PSS, the salt length can be made a parameter, rather than fixed to the hash width as usual. Also, it can optionally be deterministic or fixed, rather than random as usual. But far from all APIs allow that.

There are similar limitations for RSAES-OAEP (without flexibility: the tag's hash always is as wide as the hash, even when the tag is empty/absent, as it often is).

That identifier BCh plays a role when using PSS padding for Rabin signatures or when it is used $$r\to\min(r^d\bmod N,N-(r^d\bmod N))$$ instead of the textbook RSA private key operation, in order to allow immediate textbook-RSA encryption of the signature with any public key with public modulus of the same size as the one used for signature.