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?
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 communityI 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?
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).
salt
?) for each computer (in a random-like manner). And perhaps add a really-random part to it. b) The padding should be at least $256 + (2/3) n$ bits (which, if $n$ is 2048 - would leave me with a maximum of 426 bits (=53 bytes) for the computer-id (or its hash). Did I understand correctly?
$\endgroup$
$(m+salt)^d \bmod n$
. $\endgroup$