0
$\begingroup$

Normally, the chinese theorem looks like this:$$ x = a_1 \bmod n_1\\ x = a_2 \bmod n_2\\ x = a_3 \bmod n_3$$ but what to do if in my situation it looks like this:$$ c_1 = x^e \bmod n_1\\ c_2 = x^e \bmod n_2\\ c_3 = x^e \bmod n_3$$

I know $c_1$, $c_2$, $c_3$, $e$, $n_1$, $n_2$ and $n_3$. So how do I find $x$?

$\endgroup$
1
  • 1
    $\begingroup$ This is the RSA broadcast attack, also known as Håstad’s broadcast attack. We have several questions about that. It assumes the same message is encrypted with textbook RSA without random padding (a big no-no). Also it's simple form works only up to some value of $e$ (related to the number of ciphertexts, size of message and muduli), but one should not rely on the later. $\endgroup$ Commented Dec 2, 2023 at 7:21

2 Answers 2

1
$\begingroup$

It is the same format. You can arrange the equations as $x^e \equiv c_i $ $mod$ $n_i $ by swapping sides, then you can apply Chinese Remainder Theorem to find the value of $x^e \equiv C $ $mod$ $n_1$$n_2$$n_3$. After that, you may try the cube root attack if public exponent $(e)$ is a small value.

$\endgroup$
1
$\begingroup$

NB_1907 gave the answer for small $e$ (3 if you are given three equations).

Now, let us look at the case where $e$ is potentially large.

In that case, what you end up needing to do is convert it into a series of conventional equivalences, that is:

From $c_1 = x^e \bmod n_1$, you find the value of $x \bmod n_1$ that satisfices it; if $e$ and $n_1$ are relatively prime, the sole value is $n_1 = c_1^{e^-1 \bmod \phi(n_1)}$ [1].

From $c_2 = x^e \bmod n_2$, you similarly find the value of $x \bmod n_2$

From $c_3 = x^e \bmod n_3$, you similarly find the value of $x \bmod n_3$.

From $x \bmod n_1, x \bmod n_2, x \bmod n_3$, you use the CRT conventionally to recover $x \bmod \text{lcm}( n_1, n_2, n_3 )$ (assuming, of course, if it exists)

Now, this is not a great help if you're giving three RSA encryptions of the same value (using the same exponent); it would be easier just to break one of the RSA public keys (rather than all three). However it might be of use if you're given a smaller problem, where the $x$ value might be larger than any of the moduli.


[1]: To determine $\phi(n_1)$, you'll need to factor $n_1$ as a substep.

$\endgroup$
2
  • $\begingroup$ @fgrieu: in any case, any problem involving factoring or exponentiation by public exponents tend to be labeled 'RSA'; hence I wouldn't necessarily deduce a great deal from that labelling. $\endgroup$ Commented Jan 2, 2024 at 14:38
  • $\begingroup$ I deleted earlier obsolete comments. Still I think we need $x\bmod n_1\;=\;{c_1}^{e^{-1}\bmod \phi(n_1)}\bmod n_1$ where there is now $n_1 = c_1^{e^-1 \bmod \phi(n_1)}$. $\endgroup$ Commented Jan 3, 2024 at 7:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.