# Retrieve message from rsa ciphertext based on some conditions

Assume:

• $$x = m^{e-1}\bmod n$$
• $$y = m^{d-1}\bmod n$$

Here $$m$$ is a message, $$e$$ is the public exponent, $$d$$ is the private key and $$n$$ is the modulus of an RSA key pair.

Now if I know $$e=65537$$, $$x$$, $$y$$, and $$n$$, can I retrieve the message $$m$$?

• Are you sure that $x$ isn't actually defined $x = m^e \bmod n$, rather than how you have written it? Jul 4, 2020 at 17:41
• Yes I'm sure. Actually I came across this while trying to solve a CTF question. This was not asked directly but I generated this condition while trying to find a solution. Jul 4, 2020 at 17:53
• As poncho, I guess there is a problem in the statement. Raising $y = m^{d-1}\bmod n$ to the power $e$, we get $y^e\equiv m^{ed}\,m^{-e}\bmod n$ (assuming $\gcd(m,n)=1$, which is overwhelmingly likely for random $m$), thus $y^e\equiv m^{1-e}\bmod n$, thus $x=y^{-e}\bmod n$. Therefore the knowledge of $x$ brings nothing, which would be strange in a CTF. Short of checking $\gcd(x,n)$ and $\gcd(y,n)$ in hope of finding a factor of $n$, and otherwise checking $x=y^{-e}\bmod n$ to check givens, I don't see that we can make any progress. Unless we get to know $m^e\bmod n$ as in standard RSA, that is.
– fgrieu
Oct 21, 2020 at 6:31

let $$\begin{equation} x*y=m^{e+d-2} \mod n \qquad (1) \end{equation}$$ $$\begin{equation} m(x+y)=(m^{e}+m^{d}) \mod n \qquad (2) \end{equation}$$taking $$log_m$$ for each from (2) side with respect to $$\mod n$$, we will have $$\begin{equation} log_mm(x+y)=log_m(m^{e}+m^{d}) \mod n \qquad \end{equation}$$ $$\begin{equation} 1+log_m(x+y)=log_m(m^{e})+log_m(1+\frac{m^d} {m^e}) \mod n \qquad \end{equation}$$ $$\begin{equation} 1+log_m(x+y)\ge log_m(m^{e})+log_m(\frac{m^d} {m^e}) \mod n \qquad \end{equation}$$ $$\begin{equation} 1+log_m(x+y)\ge e+d-e \mod n \qquad \end{equation}$$ $$\begin{equation} d\simeq 1+log_m(x+y)\qquad (3) \end{equation}$$ substitute $$(3)$$ in $$(1)$$ $$\begin{equation} x*y=m^{e+(1+log_m(x+y))-2} \mod n \qquad \end{equation}$$ $$\begin{equation} x*y=m^{e-1}m^{log_m(x+y)} \mod n \qquad \end{equation}$$ $$\begin{equation} m^{e-1}=(x+y)^{-1}(x*y) \mod n \qquad \end{equation}$$
• The step "taking $\log_m$ for each from (2) side with respect to $\mod n$" is based on the premise that $a\equiv b\pmod n\implies\log_m(a)\equiv\log_m(b)\pmod n$. That premise is wrong. Proof by counterexample: $a=2$, $b=4$, $n=2$, $m=2$. It holds $2\equiv 4\pmod2$, $\log_2(2)=1$, $\log_2(4)=2$, but $1\not\equiv2\pmod 2$.
• @fgrieu As in your comment to the question: That only happens if $n$ and $m$ are not coprime, which should only happen with negligible probability. But there is a more serious issue: The way the logarithm is used and the lower estimation $log_m(1 + m^d / m^e) \geq log_m( m^d / m^e)$, I would guess the author means the logarithm function over the real numbers. And that does not work in the finite ring. And anything that follows, that doesn't work.