Let $n$ be an RSA modulus and assume one has the two following equations

\begin{align} y_1 = (x+a_1)^{-1} \pmod{\varphi(n)}\\ y_2 = (x+a_2)^{-1} \pmod{\varphi(n)} \end{align} with known $y_1$, $y_2$, $a_1$ and $a_2$, and where $\varphi$ is Euler's totient function.

Is it possible to solve the system and recover $x$?

  • $\begingroup$ I'm somewhat sure that recovering $x$ in this case is equivalent to factoring $n$. $\endgroup$
    – SEJPM
    Commented Sep 16, 2018 at 18:09
  • $\begingroup$ Yes, I would also say so. $\endgroup$
    – user51957
    Commented Sep 16, 2018 at 18:10
  • $\begingroup$ I thought about this a bit more. If we can factor $n$, recovering $x$ is easy. If we can come up with $y_1,y_2,a_1,a_2$ such that the system only has one solution and we can somehow recover $x$ from such a system, we can factor $n$. This means that it suffices for a "no" answer to show how to construct the parameters for any given $n$ so that the system only admits one solution. $\endgroup$
    – SEJPM
    Commented Sep 16, 2018 at 18:19
  • $\begingroup$ So you assume that $\varphi(n)$ is known but not $n?$ Otherwise $n$ can be factored, see crypto.stackexchange.com/questions/5791/…. $\endgroup$ Commented Sep 16, 2018 at 19:28
  • $\begingroup$ Sorry if that was not clear, but only $n$ is known, not $\varphi(n)$. $\endgroup$
    – user51957
    Commented Sep 16, 2018 at 19:36

1 Answer 1


From your equations, one can write: \begin{eqnarray*} x + a_1 &=& \frac{1}{y_1} \mod \phi(n) \\ x + a_2 &=& \frac{1}{y_2} \mod \phi(n) \\ \end{eqnarray*} and thus: \begin{eqnarray*} a_1 - a_2 &=& \frac{1}{y_1} - \frac{1}{y_2} \mod \phi(n) \\ \end{eqnarray*} which leads to: \begin{eqnarray*} (a_1 - a_2) y_1 y_2 - y_2 + y_1 &=& 0 \mod \phi(n) \\ \end{eqnarray*}

Therefore, one can compute $f = (a_1 - a_2) y_1 y_2 - y_2 + y_1$, and the equation above tells you that $f$ is a multiple of $\phi(n)$. At that point, you can take a random prime integer $e$ which is relatively prime to $f$ (take a random prime $e$, compute the GCD with $f$; if it is distinct from $1$, start again with a new random prime). This value $e$ will be "an RSA public exponent". You can then compute $d = e^{-1} \bmod f$, i.e. the corresponding "RSA private exponent".

Given a pair of public/private exponents $(d,e)$, one can factor the modulus $n$, using the method described here (a more formal reference is Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem). Once $n$ is factored, you then compute $phi(n)$, at which point you can recover $x = y_1^{-1} - a_1 \bmod \phi(n)$.

  • $\begingroup$ Nice answer. Can $f$ be zero ? $\endgroup$
    – Ruggero
    Commented Sep 18, 2018 at 14:55
  • $\begingroup$ The methods to factor $n$ from $(d,e, n)$ use $d$ and $e$ only for computing a multiple of $\phi(n)$ as $e\,d-1$. Typically we'll have $e\,d-1\gg f$ and thus we are typically better skipping the choice of $e$ and computation of $d$, and using $f$ as the desired multiple of $\phi(n)$. $\endgroup$
    – fgrieu
    Commented Sep 18, 2018 at 16:33

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.