Sorry in advance if this question is silly. Suppose we want to break RSA, that is find the message $m$ s.t. $c \equiv m^e \pmod n$ Now suppose we know an $x$ s.t. $c \equiv x^e \pmod n$. Could we use that information to somehow find $m$?
-
5$\begingroup$ Unless I'm missing something, we necessarily have $m \equiv x \pmod n$. Are you sure you wrote the equations correctly? $\endgroup$– ponchoDec 16, 2018 at 17:52
-
$\begingroup$ Possible duplicate of Why is RSA decryption the inverse of encryption? $\endgroup$– kelalakaDec 16, 2018 at 17:54
-
$\begingroup$ @kelalaka I don't see how that would be a duplicate. $\endgroup$– MaeherDec 16, 2018 at 19:14
-
$\begingroup$ But poncho is correct. What you wrote can basically be paraphrased as "Can I learn $m$ if all I know is $m$?" $\endgroup$– MaeherDec 16, 2018 at 19:15
-
$\begingroup$ If there is an inverse it is the inverse in the modulus. (encryption-decryption) $\endgroup$– kelalakaDec 16, 2018 at 19:17
1 Answer
Breaking an instance of (textbook) RSA encryption is: given $(n,e)$ and $c$, finding $m$ such that $c\equiv m^e\pmod n$ (meaning by definition: $n$ divides $m^e-c\ $), and $0\le m<n$.
For proper establishment of $(n,e)$, there is a single such $m$ for each integer $c$.
If we are additionally (or instead of $c$) given an integer $x$ such that $c\equiv x^e\pmod n$ (meaning by definition: $n$ divides $x^e-c\ $), then we can compute the desired $m$ as $x\bmod n$. That is the uniquely defined $m$ such that $n$ divides $x-m$ and $0\le m<n$.
For non-negative $x$, we can compute $x\bmod n$ as the remainder of the Euclidean division of $x$ by $n$. For negative $x$, we can use that $x\bmod n$ is $(n-1)-((-x-1)\bmod n)$, where $(-x-1)\bmod n$ is computed as the remainder of the Euclidean division of $-x-1$ by $n$.