4
$\begingroup$

(This is inspired by this question 1; have also read this question 2 but it's one-time pad)

I would like to know, given two message $m_1$ and $m_2$, as well as public keys $(e,n_1)$ and $(e,n_2)$, can I create a ciphertext $C$ such that decryption with private key 1 $(d_1, n_1)$ gives $m_1$ and $(d_2, n_2)$ gives $m_2$? $$C^{d_1}\equiv m_1\pmod {n_1}$$ $$C^{d_2}\equiv m_2\pmod {n_2}$$

I think it is possible because by Chinese remainder theorem, I can find a unique $C$ for any $m_1\ ^e$, $m_2\ ^e$, and respective coprime $n_1$ and $n_2$, such that $$C\equiv m_1\ ^e\pmod {n_1}$$ $$C\equiv m_2\ ^e\pmod {n_2}$$

Is it possible? If so are there any significant limitations, or public implementations for this?

$\endgroup$
  • $\begingroup$ Just wondering what is the usage of this? RSA is should not be used for encryption and this is valid for Textbook RSA. If you want to encrypt with RSA you should use PKCS#1v1.5 padding, and normally we prefer hybrid encryption, so there are no implementation for this. Today RSA is preferred either for signatures with PSS padding ( RSA decrypt!=signature) or Key Encapsulation Mechanism. $\endgroup$ – kelalaka Jan 18 at 9:02
  • $\begingroup$ @kelalaka Not really any use, it just pop up when I look up for honey encryption and rubber hose cryptanalysis: "can I choose which key to reveal in case I was captured by organization like CIA/MI5/SVR/CCP"? Of course I'm not (I hope) their prime target, and a single integer modulo won't save me if I pissed them off, but it seems like a good learning point to me $\endgroup$ – R. Wang Jan 18 at 16:27
6
$\begingroup$

For the problem as stated in the question, yes what's asked is possible, exactly per the method stated in the question. For textbook RSA (except with unusually tolerant decryption code), no, that's not possible. For RSA as practiced, there exists solutions or not, and it can be found on not, depending on methods and parameters.

The critical differences are due to different definitions of a valid ciphertext $C$ for a message $m$ and public key $(n,e)$:

  • In the question's RSA, that's $C\equiv m^e\pmod n$, which allows arbitrary many integers $C$, since that notation only means that $n$ divides $C-m^e$, and implies that if $C$ is valid, then $z\,n+C$ also is for any $z\in\Bbb Z$. Notice that this version of RSA makes $C=m^e$ a valid ciphertext, and this choice of ciphertext allows decryption without the private key, as $m=\sqrt[e]C$.
  • In textbook RSA, that's $C=m^e\bmod n$, which further implies $0\le C<n$. This should be tested before decryption (and actual implementation often do this, or at least depend on $C$ not having much more bits than $n$). That leaves a single (or relatively few) valid ciphertext for any message $m$. A ciphertext is uniquely defined for $m_1$ with $(n_1,e)$, and there's no way to make it coincide with the uniquely defined ciphertext for $m_2$ with $(n_2,e)$. A spontaneous match won't occur by chance for even half-realistic modulus size.
  • in RSA as practiced, well there's not a single practice, but at least there again are many ciphertexts for any given plaintext, because the message is always combined with randomness for encryption¹. Block RSA encryption usually has $C=g(r,m)^e\bmod n$ where $r$ is a large random bitstring and $g$ is injective with output domain a subset of $[0,n)$. The size of $m$ is severely restricted compared to textbook RSA. If $r$ has sizably more than half as many bits has $n$, by the birthday bound, it is likely that one of the valid ciphertexts for $m_1$ with $(n_1,e)$ coincides with one of the valid ciphertexts for $m_2$ with $(n_2,e)$, implying there's a solution².

Doing what the question wants is easy: one computes $C_1=m_1^e\bmod n_1$ and $C_2=m_2^e\bmod n_2$ per textbook RSA, then by the Chinese Remainder Theorem one computes a $C$ such that $C\equiv C_1\pmod{n_1}$ and $C\equiv C_2\pmod{n_2}$. There is exactly one such integer $C$ in $[0,n_1\,n_2)$ under the hypothesis that $n_1$ and $n_2$ are coprime, which should hold for proper RSA keys. It can be computed as $$C=\bigl(({n_2}^{-1}\bmod n_1)(C_1-C_2)\bmod n_1\bigr)\,n_2+C_2$$ This $C$ will decipher to $m_1$ for private key $(n,d_1)$ and to $m_2$ for private key $(n,d_2)$ under implementations of textbook RSA decryption that do not check that their ciphertext input is less than the modulus, and still compute exactly despite the anomalous input.


¹ Deterministic RSA allows anyone to check a guess of the plaintext, e.g. find who's name on a public class roll was encrypted. The addition of randomness fixes that often devastating weakness.

² For PKCS#1 v1.5 encryption padding (but not the better OAEP) it is conceivable to actually exhibit a solution if the message is very short and the corresponding private key is known and of the same size. With $m_1$ short, we compute various ciphertexts for $m_2$ and different random padding, and decipher each under $(n,d_1)$ until that does not cause an error, and the deciphered plaintext has the desired size, and it happens to match $m_1$. For 2048-bit $n_1$ and $n_2$, and $m_1$ of $k$ bytes, this is expected to require on average less than $2^{8k+26}$ attempts.

| improve this answer | |
$\endgroup$

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.