Find unknown primes from two RSA modulus

Question

Suppose that $𝑝$, $𝑞$, and $𝑟$ are $512$-bit primes and for some integer $𝑎 < 10^5$, $𝑝 + 𝑎$ is also prime. We know the moduli $𝑛_1 = 𝑝 × 𝑞$ and $𝑛_2 = (𝑝 + 𝑎) × 𝑟$. Can we recover the primes $p$, $𝑞$, and $𝑟$ from this information?

Answer 1

This can be solved by carrying out exhaustive search on $a$ (the search space is only around $2^{15}$ after all) and applying the bivariate Coppersmith theorem for each candidate value of $a$. As a reminder, the theorem says the following:

Let $P(x,y)$ be an irreducible polynomial in two variables over $\mathbb{Z}$, of maximum degree $\delta$ in each variable independently, and $X,Y\leq 1$ be some bounds on the desired solutions $x_0, y_0$. Define $\tilde{P}(x,y) = P(xX,yY)$ and let $W$ be the supremum of the absolute values of the coefficients of $\tilde{P}$. Under the condition that $XY \leq W^{2/(3\delta)}$, one can find all integer pairs $(x_0,y_0)$ with $P(x_0,y_0) = 0$, $|x0| \leq X$ and $|y_0| \leq Y$ in time polynomial in $\log W$ and $2^\delta$.

In the case of this question, I take $P(x,y) = axy - N_2 x + N_1 y$, which is a polynomial of degree $\delta=1$ independently in $x$ and $y$. I claim that $(x_0,y_0)=(q,r)$ is a small solution. Indeed, $P(x_0,y_0) = aqr - N_2 q + N_1 r = aqr - (p+a)qr + pqr = 0$. Moreover, if I set $X=Y=2^{512}$, $W=\max(aXY, N_2 X, N_1 Y)\approx 2^{1536}$, and therefore the condition $XY\leq W^{2/3}$ is satisfied, so Coppersmith gives an efficient algorithm to find $q,r$, which obviously solves the problem.

Where does the question come from, by the way? I haven't seen it addressed directly in a cursory literature review, so if it is related to some sort of realistic scenario (some kind of fault attack?), it might be interesting to write up.