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.


1 Answer 1


Update: For this particular problem, there is a simpler answer that does not require very fancy machinery. It is based on Section 3 of the withdrawn Lu-Peng-Zhang-Lin.

Let $p_1 = p_2 + 2$, be twin $n/2$-bit primes. Let $q_1$ and $q_2$ be random $n/2$-bit primes. Let $n_1 = p_1q_1$, and $n_2 = p_2q_2$.

Because we know the exact distance $p_1-p_2 = 2$ in this case, we have the relation $$ 2q_2 + n_2 \equiv 0 \pmod{p_1}\, $$ but moreover, this also holds modulo $p_1q_2$. It has as a small root $q_2$.

Now we can apply the Coppersmith theorem, and find a small root of $x + n_2/2 \bmod (n_1n_2)$ modulo the divisor $p_1q_2$ of $n_1n_2$: we have the divisor size $p_1q_2 \approx n_1n_2^{1/2}$ and the root size $q_2 \approx \left(n_1n_2\right)^{1/4} \le \left(n_1n_2\right)^{\frac{(1/2)^2}{1}}$. So this becomes a simple application of Coppersmith's theorem.

To solve this on exactly balanced primes still requires quite an effort, due to the lattice dimension and coefficient sizes involved and some bruteforce. So here is an example with some slack bits of unbalancedness added to make things easier to demonstrate on Sagemath. Below:

sage: set_verbose(2)
....: slack = 32
....: while True:
....: ^Ip2 = random_prime(2^(512+slack), lbound=2^(512+slack-1)+2^(512+slack-2), proof=False)
....: ^Iif is_pseudoprime(p2 + 2):
....: ^I^Ip1 = p2 + 2
....: ^I^Ibreak
....: q1 = random_prime(2^(512-slack), lbound=2^(512-slack-1)+2^(512-slack-2), proof=False)
....: q2 = random_prime(2^(512-slack), lbound=2^(512-slack-1)+2^(512-slack-2), proof=False)
....: n1 = p1*q1
....: n2 = p2*q2
....: P.<x> = Zmod(n1*n2)[]
....: f = x + inverse_mod(2, n1*n2)*n2 % (n1*n2)
....: f.small_roots(X=2^(512-slack), beta=0.499, epsilon=1/80)
verbose 2 (<module>) epsilon = 0.012500
verbose 2 (<module>) m = 20
verbose 2 (<module>) t = 20
verbose 2 (<module>) X = 3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290176
verbose 1 (<module>) LLL of 40x40 matrix (algorithm fpLLL:wrapper)
verbose 1 (<module>) LLL finished (time = 98.39880900000003)
sage: q2

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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