# Breaking RSA using known root

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

• Unless I'm missing something, we necessarily have $m \equiv x \pmod n$. Are you sure you wrote the equations correctly? – poncho Dec 16 '18 at 17:52
• Possible duplicate of Why is RSA decryption the inverse of encryption? – kelalaka Dec 16 '18 at 17:54
• @kelalaka I don't see how that would be a duplicate. – Maeher Dec 16 '18 at 19:14
• But poncho is correct. What you wrote can basically be paraphrased as "Can I learn $m$ if all I know is $m$?" – Maeher Dec 16 '18 at 19:15
• If there is an inverse it is the inverse in the modulus. (encryption-decryption) – kelalaka Dec 16 '18 at 19:17

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