0
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Are you sure that $x$ isn't actually defined $x = m^e \bmod n$, rather than how you have written it? $\endgroup$
    – poncho
    Jul 4, 2020 at 17:41
  • $\begingroup$ 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. $\endgroup$ Jul 4, 2020 at 17:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Oct 21, 2020 at 6:31

1 Answer 1

-1
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Oct 21, 2020 at 6:08
  • 1
    $\begingroup$ @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. $\endgroup$
    – tylo
    Oct 22, 2020 at 1:32

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.