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 ?
