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$?
$\begingroup$
$\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$– ponchoCommented 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$– Ketan ChaturvediCommented 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 ♦Commented Oct 21, 2020 at 6:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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}
-
$\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 ♦Commented 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$– tyloCommented Oct 22, 2020 at 1:32