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

  • I'm curious of why you are asking this question. I presume you would not be able to calculate the public key either, right? Is this a specific functionality you're after? – Maarten Bodewes Sep 18 '15 at 11:55

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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