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

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?

-
@fgrieu m^d mod n VS (m+salt)^d mod n – ispiro May 3 '13 at 14:04
Is your + denoting addition, or some other operation? Also: you can write $(m+salt)^d \bmod n$ as $(m+salt)^d \bmod n$. – fgrieu May 3 '13 at 14:09
@fgrieu concatenation. $(m+salt)^d \bmod n$ - Thanks. I was looking for that formatting. – ispiro May 3 '13 at 14:10
@fgrieu I'm converting a byte array to a BigInteger but first concatenating a new byte array to the end of the original one (before converting to BigInteger) and using that as $m$ in $m^d \bmod n$. – ispiro May 3 '13 at 14:19
Standard RSA implementations like PKCS#7 and CMS specify random padding to prevent two identical messages from yielding the same output. Is there a difference between what you are trying to accomplish with the salt and the standard implementations? – John Deters May 3 '13 at 14:51

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).

-
So... I understand from your answer that in the signature scheme where (as a licensing system) I'm signing a user's computer's hardware-id and returning it to the user's computer - having my application on that computer verify that the returned value is indeed the signed hardware-id: the following will be true: – ispiro May 5 '13 at 9:38
a) I should calculate a separate padding (is that the term instead of 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? – ispiro May 5 '13 at 9:38
Oh.. and thank you very much for your answer! – ispiro May 5 '13 at 9:50
@ispiro: Yes padding is right (added it in the answer). The simplest: use a standard signature and verification library implementing RSASSA of PKCS#1, or ISO/IEC 9796-2. If you want to roll your own implementation (which makes some sense for copy protection), you can still use a standard scheme. You will be very much on the safe side w.r.t. signature forgery doing as in a)&b) in your comment above, baring implementation mistakes (in particular: the verifier MUST check both the signed message/computer-id, and the deterministic random-like portion of the padding obtained from that). – fgrieu May 5 '13 at 13:29