# Equations modulo phi(n)

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

• I'm somewhat sure that recovering $x$ in this case is equivalent to factoring $n$. – SEJPM Sep 16 '18 at 18:09
• Yes, I would also say so. – user51957 Sep 16 '18 at 18:10
• 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. – SEJPM Sep 16 '18 at 18:19
• So you assume that $\varphi(n)$ is known but not $n?$ Otherwise $n$ can be factored, see crypto.stackexchange.com/questions/5791/…. – gammatester Sep 16 '18 at 19:28
• Sorry if that was not clear, but only $n$ is known, not $\varphi(n)$. – user51957 Sep 16 '18 at 19:36

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)$.
• Nice answer. Can $f$ be zero ? – Ruggero Sep 18 '18 at 14:55
• 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)$. – fgrieu Sep 18 '18 at 16:33