Efficient integer factoring knowing the inverse of p mod q

❚ Several weeks ago, i heard a nice talk from one of my colleagues about the Coppersmith method and it application to factoring integers. It is a very powerful method and can, e.g., be applied if partial information of $p$ or $q$ is known, the factors $p$ and $q$ of $N=pq$ have a small differences or to obtain a deterministic algorithm that returns a factor if a multiple of $\varphi(N)$ is known.

The trigger for the talk was a discussion about the risk if the inverse of one factor modulo the other factor of an RSA modulus is leaked. That means knowing the following integer $I$: $$I \equiv p^{-1} \pmod{q},\;p,q \in \mathbb{P},\;N=pq$$ Since the Coppersmith method is very powerful it is actually not surprising that it could be used to accomplish this task, at least partially.

❰Coppersmith's Theorem❱ Let $0 < \beta < 1$ and $c,N \geq 1$ and $f \in \mathbb{Z}[x]$ be a monic polynomial of degree $\delta$. The set of all integer $a \in \mathbb{Z}$ with $$\gcd(f(a),N) \geq N^\beta \; \text{and} \; |a| \leq cN^{\beta^2/\delta}$$ can be computed in time $\text{poly}(c,\delta,\log N)$.

Suppose you are given $N=pq$ and $I \equiv p^{-1}\mod{q}$ and $2^{n-1} < p < q < 2^n$, that is a balanced RSA-Modulus, which counts as a secure choice in cryptography. Then you have $$I \equiv p^{-1}\mod{q} \Leftrightarrow Ip = 1 + qk, k \in \mathbb{Z}$$ which is equivalent to $Ip^2 = p + Nk$, hence we get the monic polynomial $$f(x) = x^2 - xI^{-1} \equiv 0 \pmod{N}$$ of degree $\delta = 2$ that has $p$ as a root modulo $N$. If we assume that $p < q$, it is $p \leq N^{1/2}$ and $\gcd(f(p),N) = N$, hence $\beta = 1$. So indeed we have a case where our root is $|p| < N^{\beta^2/\delta} = N^{1/2}$ and we can find it in polynomial time.

But what if we have the inverse of $q^{-1} \pmod{p}$? In that case it is $$|q| > N^{1/2} = N^{1/2+\epsilon} = N^{\epsilon}N^{1/2} = cN^{1/2}$$
If $\epsilon = c'\log n/n$, for a constant $c'$, one gets $$N^{\epsilon} = N^{c'\log n/n} \approx 2^{n\cdot c'\log n/n} = 2^{c'\log n} = n^{c'}$$ But already a non-constant but slightly increasing $c' = n$ would lead to a quasi-polynomial complexity.
To give an example, take $n = 2048$ and $c' = 1$, which leads to $\epsilon = 11/2048 \approx 0.0050537$. So the algorithm will only be successful if the larger factor is not much larger than $\sqrt{N}$.

Are there alternative Methods ?

❚ I was wondering if such a heavy weapon as the Coppersmith method is really necessary in this case. Intuitively, the integer $I$ should already give enough information to obtain the two factors $p$ and $q$ with more elementary methods than launching Coppersmith, lattice theory and the LLL algorithm. With "more elementary" i mean some basic group or integer operations that finally lead to an integer $t$ with $\gcd(N,t) > 1$. But it seems that my intuition is wrong in this case.

If you have both inverses, $p^{-1} \equiv I \pmod{q}$ and $q^{-1} \equiv J \pmod{p}$, you are done. Note that here $I$ and $J$ are both positive integers, hence they do not fulfill the equation $Ip + Jq = 1$ but $Ip + Jq = pq + 1$ It is easy to prove that $p < I + J < q+1$, so they can not be both small. Consequently, one of the two values $$I^{-1} \pmod{J} \; \text{or} \; J^{-1} \pmod{I}$$ yields either $p$ or $p - I$ or $p - J$, since at least one of $I$ and $J$ must be larger than $p/2$.

(Approach 1) Linear diophantine equation. Given the target integer $N=pq$, the most straight forward approach would be to find a linear diophantine equation $$ap + bq = c$$ with known $a$ and $c$. Given such an equation one could obtain the factor $q$ (with $Ip = 1+qk$) via $$\gcd(Ic-a,N) = q$$ since $$Ic = I(ap+bq) = a(1+qk) + Iqb = a + q(Ib+ak)$$ The method will only fail if $p | (Ib+ak)$. But how to find such an equation is not obvious.

(Approach 2) The inverse of I mod N. Another approach could be do compute the inverse of $I$ in $\mathbb{Z}^*_N$, denoted as $R$: $$IR \equiv 1 \pmod{N}$$ This $R$ must be of the form $$R = p + qs, s < p$$ It has the nice property that $R^e \equiv p^e + (qs)^e \pmod{N}$, for any integer $e$.  Note that $R$ is actually a linear diophantine equation with known $a$ and $c$ but
\begin{align*}
 IR & = Ip + qIs = 1 + qk + qIs \\
 \Leftrightarrow & \\
 IR-1 & = q(k+Is)
\end{align*}
But since $N|(IR-1)$, it is $p|(k+Is)$, so Approach 1 fails.

A representation of an integer $1\leq R \leq N$ as an linear combination of the two factors $p$ and $q$ is always possible, but what is special about $R$ is, that the coefficient of $p$ is not only known, but very small - it is ONE. This leaves much room to play and to learn something about the other coefficient $s$. But it seems, that this room is only half of the required size.

(Approach 3) Using the group order (p-1)(q-1). For an RSA modulus $N=pq$ Euler's Totient Function has the value $\varphi(N) = (p-1)(q-1)$. Hence for a co-prime integer $g$, it is $$g^{N+1} \equiv g^{p+q}\pmod{N}$$ Consequently, after subtracting $R$ in the exponent one gets is $$g^{N+1-R} \equiv g^{q(1-s)}\pmod{N}$$ The exponent, which is now a multiple of $q$, must be useful somehow, but not yet for me.

Likewise, the group order can be used to factor $$g^{N-1} \equiv g^{p + q - 2}$$ into the following two group elements. We know that $g^{q-2} \pmod{q}$ is the inverse element if $g$ in $\mathbb{Z}^*q$. So if we set $g = I$, we have
\begin{align*}I^{N-1} & \equiv I^{p+q-2} \equiv I^p\cdot I^{q-2} \pmod{N}\\
& \equiv (I+p\lambda)(p+q\gamma) \pmod{N}\\
\end{align*} for some integer $0 \leq \lambda_1 < q$ and $0 \leq \gamma_0 < p$.


❚ Perhaps since even the Coppersmith method isn't successful in solving this problem in every setup, the inability to find an easy elementary algorithm should be not surprising. However, i am not very pleased with this reasoning. If anyone of you knows a better way to do this or has some good ideas, leave me a note.