1
$\begingroup$

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

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

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

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