6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ @kelalaka Just $n_1$ and $n_2$ are known to us. $\endgroup$
    – Lisbeth
    Commented Jul 9 at 12:19
  • $\begingroup$ Could you provide us with the origin of this question? $\endgroup$
    – kelalaka
    Commented Jul 9 at 14:53
  • 1
    $\begingroup$ The specific case $a=2$ was considered here. $\endgroup$ Commented Jul 11 at 0:15

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If someone uses a sieve to pre-select the prime factors of a batch of RSA-moduli, (s)he could get the idea to pick more than one prime from the sieve. $\endgroup$
    – j.p.
    Commented Jul 10 at 20:14

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.