8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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