What length should the padding be when encrypting or signing with RSA?

Question

I am wondering what length the padding should be when encrypting or signing with RSA.
Does it matter what length the padding is, and if so — what length should it be?

Another point: Should it be random?

Answer 1

First and foremost: it is a bad idea to invent a method to sign or encrypt with RSA (or any crypto). Standards like PKCS#1 or ISO/IEC 9796-2 are here for that purpose, and even these occasionally have more or less subtle flaws.

Given comments, I'll assume that the question is about an RSA encryption scheme enciphering message $M$ into $(M||S)^e\bmod N$, and an RSA signing scheme with appendix producing a signature for $M$ as $(M||S)^d\bmod N$, where $||$ stands for concatenation. $m$ and $s$ will be the bit size of $M$ and $S$ (including leading zeroes), and $n$ the bit size of the public modulus $N$ (excluding leading zeroes). I'll assume $m+s<n$, implying $(M||S)<N$, which allows decryption. The question is about choosing $S$ (designated as salt), and $s$.

In the context of RSA, salt is not a common term; we use padding. In particular, salt is typically assumed random and public, and that is not what $S$ should be.

In the encryption scheme, if $S$ is made public, and $M$ is a message from a small set (e.g. coin or dice throw, winner of an election, password, serial number) or more generally low-entropy, the adversary can compute $(M||S)^e\bmod N$ for plausible $M$, and the only result matching the ciphertext will be that for the right plaintext. Similarly, $S$ must not be a public function of $M$ (e.g. obtained by hashing). The best choice would be $S$ random, undisclosed, and drawn for each ciphertext produced (rather than for each message encrypted; the difference is critical if there are multiple recipients). I'm then confident, without proof, that $s\ge 2\cdot n/3+256$ is safe. That bound is far from optimal, but that answer shows that $s\gg n/e$ is necessary to guard against attack by Coppersmith's theorem, and $s\gg 256$ is necessary to guard against a square-root attack.

In the signature scheme, if $S$ was entirely random, the adversary could choose it freely in attempted forgeries. This is a huge problem, in particular the signatures $1$ and $0$ are both admissible for the empty/all-zero message (other attacks are possible; the larger $s$, the more unsafe). Thus $S$, or at least a sizable portion of $S$, must be non-malleable by the adversary (though some of $S$ can be left random, if it is tolerable or desirable that signing the same message twice does not lead to twice the same signature; that's also useful for some security arguments). $S$ (except for its random portion, if any) is best a public random-like function of $M$, like $S=H(M)||H(H(M))||H(H(H(M)))\dots$ until $S$ is wide enough. Again I'm then confident, without proof, that $s\ge 2\cdot n/3+256$ (including at most 256 random bits) is safe, even if the adversary is assumed to be able to obtain signatures for messages of her choice; again that bound is far from optimal. Update: the verifier must of course check the validity of the padding $S$ (except for its random portion, if any).