3
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm somewhat sure that recovering $x$ in this case is equivalent to factoring $n$. $\endgroup$ – SEJPM♦ Sep 16 '18 at 18:09
  • $\begingroup$ Yes, I would also say so. $\endgroup$ – user51957 Sep 16 '18 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♦ Sep 16 '18 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$ – gammatester Sep 16 '18 at 19:28
  • $\begingroup$ Sorry if that was not clear, but only $n$ is known, not $\varphi(n)$. $\endgroup$ – user51957 Sep 16 '18 at 19:36
8
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice answer. Can $f$ be zero ? $\endgroup$ – Ruggero Sep 18 '18 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♦ Sep 18 '18 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.