Adding two RSA private key

Question

We've constructed a new private RSA key from two known private RSA keys $Priv_1$ and $Priv_2$ as follows:

$$p = next\underline{}prime\left(\frac{Priv_1(p) + Priv_2(p)}{2}\right)$$

and

$$q = next\underline{}prime\left(\frac{Priv_1(q) + Priv_2(q)}{2}\right)$$

where $Priv_{1}(p)$ is the first factor of $Priv_1$ and so on.

The keysize is 2048 bits. Suppose that we know the three public keys of $Pub_1$, $Pub_2$ and $Pub_3$, that $Pub_3$ corresponding public key for $p$ and $q$. Is it possible to find $p$ and $q$?

Answer 1

Problem re-statement and notations: we know three 2048-bit RSA public moduli $N_1$, $N_2$, $N$, of unknown factorizations $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, with $p_1<q_1$, $p_2<q_2$. We additionally know that $p$ is the smallest prime at least $(p_1+p_2)/2$, and $q$ the smallest prime at least $(q_1+q_2)/2$. Can we use that to help finding $p$ and $q$?

The quantity $N^2/(N_1\cdot N_2)$ reveals something about $p_1$ $p_2$ $q_1$ $q_2$ that we had no way to know without $N$. But there's no reason that this quantity would be strongly revealing of $q_1/p_1$ or $q_2/p_2$.

If we ignore the small increments to the next prime, and the Diophantine aspect of things, we have only 5 equations (ignoring inequalities: $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, $p=(p_1+p_2)/2$, $q=(q_1+q_2)/2$) among 6 unknowns ($p_1$ $q_1$ $p_2$ $q_2$ $p$ $q$), with 4 unknowns randomly seeded in a large interval and the other two also varying in a large interval. Given these, $q/p$ (or $q_1/p_1$, $q_2/p_2$) can still vary widely and can't be closely estimated, which would have enabled a Fermat-like factorization.

Thus as far as I can tell: no, we do not know how to find $p$, $q$ much easier than by factoring one of $N_1$, $N_2$, or $N$.