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$
    – poncho
    Dec 16, 2018 at 17:52
  • $\begingroup$ Possible duplicate of Why is RSA decryption the inverse of encryption? $\endgroup$
    – kelalaka
    Dec 16, 2018 at 17:54
  • $\begingroup$ @kelalaka I don't see how that would be a duplicate. $\endgroup$
    – Maeher
    Dec 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$
    – Maeher
    Dec 16, 2018 at 19:15
  • $\begingroup$ If there is an inverse it is the inverse in the modulus. (encryption-decryption) $\endgroup$
    – kelalaka
    Dec 16, 2018 at 19:17

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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