Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
As you may know, PKCS#1 defines two different padding in it's v1.5 : one for signature and one for encryption. Here they are :
The middle part is refered as PS in the standard.
There is only one thing bothering me : why does PS differ between signature and encryption ? I can't see any reason ti fixe PS to a '0xFF' string for both padding.
The 01 and 02 valued bytes before the PS are used for domain separation; each scheme has it's own unique value that way.
For a generic cipher it is required that the method is non-deterministic. The reason is simple: otherwise you would be able to identify which messages are identical, as they would result in identical ciphertext:
$$E_{pk}(p) = E_{pk}(p') \iff p = p'$$
In other words: repetition of the ciphertext shows to an adversary that the plaintext is identical as well; absence of identical ciphertext likewise shows that no plaintext messages were repeated. So obviously this does not result in a cipher that is resilient against chosen plaintext attacks.
Non-determinism is not a strict requirement for digital signatures, even though many of such schemes are indeed non-deterministic. Examples of non-deterministic schemes are ECDSA and RSA-PSS. The latter has been defined in version 2.1 of the PKCS#1 standard referenced in the question.
The submission to the IEEE 1363 workgroup called "PSS: Provably Secure Encoding Method for Digital Signatures" shows that a random seed can be used to tighten the security proof for PSS and that it allows for weaker assumptions on the security of the mask generation function that is used within PSS. But it also states that PSS remains provable secure (assuming the RSA cryptosystem is secure) even if the random number generator fails or if the seed is provided by an adversary.
In the end random number generation is not required for signature generation. The fact that an RSA signature can be generated without relying on a cryptographically secure random number generator is certainly an advantage; it will speed up computation and it doesn't rely on a resource that may need to block until entropy becomes available.
Maarten Bodewes answer is correct, but it is missing one important point.
It is actually NOT secure to have randomness in PKCS#1V1.5 padded signatures, otherwise signatures could be forged via bleichenbacher's e=3 attack.
Take a look at https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ to see what happens when signature verification implementations forget to assert that those bytes are actually 0xFF.
