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?

  • $\begingroup$ @fgrieu m^d mod n VS (m+salt)^d mod n $\endgroup$ – ispiro May 3 '13 at 14:04
  • $\begingroup$ Is your + denoting addition, or some other operation? Also: you can write $(m+salt)^d \bmod n$ as $(m+salt)^d \bmod n$. $\endgroup$ – fgrieu May 3 '13 at 14:09
  • $\begingroup$ @fgrieu concatenation. $(m+salt)^d \bmod n$ - Thanks. I was looking for that formatting. $\endgroup$ – ispiro May 3 '13 at 14:10
  • 1
    $\begingroup$ @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$. $\endgroup$ – ispiro May 3 '13 at 14:19
  • 1
    $\begingroup$ 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? $\endgroup$ – 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).

| improve this answer | |
  • $\begingroup$ 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: $\endgroup$ – ispiro May 5 '13 at 9:38
  • $\begingroup$ 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? $\endgroup$ – ispiro May 5 '13 at 9:38
  • 1
    $\begingroup$ @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). $\endgroup$ – fgrieu May 5 '13 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.