Is it ever OK to to sign RSA messages with padding random bytes? If a message is padded with cryptographically secure random bytes, is there any reason why this would be less secure than the standard signature padding schemes (PKCS1 v1.5 and PSS)? To give context to the meaning of the word &quot;secure,&quot; I would note that my only intention is to prevent others from being able to forge the message signature.
The correctness of the padding should be verifiable from the hash of the message - that is, given the hash of the message, the same padding should be reproducible. Otherwise, &quot;existential forgery&quot; would be possible.
So what is &quot;existential forgery&quot;?
Basically, you just produce a random string of bytes as your signature. When it's interpreted as an integer and raised to e'th power mod n, the lower 256/384/512 bits will be as valid a hash value as any other, so even though we don't know what message produces such hash value, we've found one that exists, hence &quot;existential forgery&quot;.
To actually make the attack work requires some extra effort, including but not limited to:

mounting collision attack on the hash function against the verification exponent with many random messages.

for small modulus, GNFS may yield results with part of lower-order bits matching the candidate message digests.


As noted by @fgrieu in the comment, the question asks a hypothetical situation that cannot be universally applied, thereby making it a false proposition.