Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$?
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)$.
