I have two 1024bit RSA modulus $N_1 = p_1q_1$ and $N_2 = p_2q_2$ such that $0 <|p_1 - p_2| < \ell$, and $\ell$ is at most 64bit integer. Can I factorise $N_1$ and $N_2$? What's the answer when $p_1$ and $p_2$ are same $\alpha$-bit primes?

  • 1
    $\begingroup$ if $p_1=p_2$ you can simply compute the greatest-common-divisor of $N_1$ and $N_2$ to factor them. $\endgroup$ Feb 14, 2015 at 8:20
  • $\begingroup$ @CodesInChaos Yes of course it's obvious. But We can imagine some approximation as like those of Coppersmith and developped later by D. Boneh and al. $\endgroup$ Feb 14, 2015 at 8:48
  • 1
    $\begingroup$ @CodesInChaos Have any solution for this $p_1 - p_2 = 2$? $\endgroup$
    – Lisbeth
    Feb 14, 2015 at 19:18
  • $\begingroup$ How about this? $\endgroup$
    – mikeazo
    Mar 16, 2015 at 12:38
  • 1
    $\begingroup$ @mikeazo: in the present question $0<|p_1-p_2|<\ell$, in the other question that you linked (transposing the notation to match that in the present question), we have $|p_1-q_1|<\ell$. $\;$ I have not understood the proposed attack, and fail to see one. $\;$ I second Lisbeth's approach to first try to solve the problem with $p_1-p_2=2$. $\endgroup$
    – fgrieu
    Apr 15, 2015 at 10:52

1 Answer 1


Outline of a elementary attack:

if $\mid p_i-q_i \leq 2^s$, we can write for each $p_i=a.2^s+\tau_i$, with $\tau_i \leq 2^s$, and we can imagine that if we determine the integer a, we can factor $N_i$ by a brute force attack. We know that $p_i$ have exactly the same bit size and if $N_i$ have exactly the same bit size (n=1024, 2048, ... s=64), the sizes of $q_i$ could differ by at most one.

Let $r=\frac{a.2^s+\tau_1}{a.2^s+\tau_2} \approx 1 + \frac{1}{a} \pm \epsilon$. And $\rho=\frac{N_1}{N_2} \approx (1 + \frac{1}{a} \pm f(\epsilon))\times \frac{q_1}{q_2}$ is a rational number which can be determined with a infinite precision.

Then by the examination of the bit of this ratio we can get information on the unknow number a, and hope to success in the factorisation Pb, in complexity less than the general know attacks.

Probably with the help of LLL algo we can enhance the attack.

  • $\begingroup$ It seems that you mean $|p_i - p_j| \le 2^s$, in this situation for $|p_1 - p_2| = 2^1$, $p_1 = a.2^s + \tau_1$ and $p_2 = a.2^s + \tau_2$ there is no solution for $a$. Same state for $|p_1 - p_2| = 2^2$. Why you say that there is such presentation for all $p_i$? I suppose that all $\tau_i$ are non-negative. $\endgroup$
    – Lisbeth
    Feb 14, 2015 at 19:16
  • $\begingroup$ @Lisbeth: This is your configuration. $p_1$ and $p_2$ have in common the n/2-s upper bits. For 1024, roughtly 512-64=448 the upper 448 bits of $p_1$ and $p_2$ are identical. $\endgroup$ Feb 14, 2015 at 20:05
  • $\begingroup$ @Lisbeth: I didn' see your last post. for s=1, you are in the case of twin primes. Try to do the same approximation to study if the problem has a solution. They have 510 bit in common. $\endgroup$ Feb 14, 2015 at 20:10
  • $\begingroup$ @Lisbeth: You can reverse the problem for testing purpose. Firstly generate two twin primes of 512 bits, and use them to build $N_1$ and $N_2$. Then you can test the validity of the above attack. Bye! $\endgroup$ Feb 14, 2015 at 20:21
  • $\begingroup$ Hey for twin primes: $p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006149569$ there is not $a$ such that $p = 2a + \tau_1$ and $p + 2 = 2a + \tau_2$, is there? $\endgroup$
    – Lisbeth
    Feb 15, 2015 at 6:45

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.