Factoring two RSA moduli $N_i=p_i\cdot q_i$ knowing that $p_2=p_1+2$?

Question

It is given two RSA moduli $N_1$ and $N_2$, known to be of the form $N_i=p_i\cdot q_i$, with $p_i$ and $q_i$ unknown primes, and such that $p_2=p_1+2$. Can we make use of that relation to factor the moduli much more efficiently than if it did not held?

If that helps, add extra assumptions if they are plausible for common RSA moduli, such as:

• $p_1<p_2<q_1<q_2$
• $p_1\equiv1\pmod 4\;$ so that $p_1$ and $p_2$ differ only by their second lowest-order bit
• $2^{(k-1)/2}<p_i<q_i<2^{k/2}$ with $k=1024$

This is a minimal subset of this more general question.

Answer 1

The fancy name for this is factorization with an implicit hint. If the primes are unbalanced, i.e., if $\log_2 p_i > 2 \log_2 q_i$, we know how to factor $n_1$ and $n_2$ quite easily. Let $k$ be the number of bits $p_1$ and $p_2$ differ by (a very small $k$, usually, for $(p, p+2)$); reduce the following lattice

$$ \begin{pmatrix} 2^k & 0 & n_2 \\ 0 & 2^k & -n_1 \end{pmatrix} $$

using LLL or equivalent. The resulting shortest vector will be $(2^k q_1, 2^k q_2, 2q_1q_2)$. This method is described, in much more generality (i.e., in terms of shared $p_i$ bits) in Faugère, Marinier, and Renault (see also May and Ritzenhofen, Sarkar-Maitra, Kurusawa-Ueda, and Nitaj-Ariffin).

Two recent papers make improvements to the above lattice-based method, and Theorem 1 of Lu-Peng-Zhang-Lin seems to imply that implicit factorization with balanced moduli is indeed possible. So the answer to your question would seem to be yes.