I'm trying to understand the precise requirements on padding when using RSA for encryption.
Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ to Bob, with a padding procedure to be determined. Assume reasonable sizes, say a 1024-bit RSA key and a 256-bit payload. Alice may send the same payload $M$ to multiple recipients, encrypted with each recipient's private key. Only a recipient must be able to recover $M$. But it's ok if an external observer can tell that Alice sent the same $M$ to Bob and Charlie (sent as $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ and $\mathrm{RSA}_{C_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ respectively)¹.
With no padding, this is broken: the plaintext can be reconstructed from $e$ ciphertexts. In general, RSA padding must be random and not recoverable without knowing the private key, if only because otherwise the attacker could verify a guess of the payload; but here I assume the payload is unguessable. So what are the requirements on padding in this scenario?
- Is it ok to use a deterministic padding function that depends only the recipient, say $\mathrm{pad}(B) = \mathrm{SHA256}(B_{pub})$?
- Is it ok to use a predictable padding function, say by incrementing global counter for each recipient (assume Alice does have a reliable monotonic counter)?
- Is it ok to use random padding that is leaked? In other words, in this scenario, is the mere fact that the attacker knows the padding a problem?
¹ What prompted this line of thought was a message $M$ that was a single-use symmetric encryption key; the long message encrypted with that symmetric key would be identical for all recipients anyway.