4
$\begingroup$

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?

$\endgroup$
  • 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$ – CodesInChaos Feb 14 '15 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$ – Robert NACIRI Feb 14 '15 at 8:48
  • 1
    $\begingroup$ @CodesInChaos Have any solution for this $p_1 - p_2 = 2$? $\endgroup$ – Lisbeth Feb 14 '15 at 19:18
  • $\begingroup$ How about this? $\endgroup$ – mikeazo Mar 16 '15 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 '15 at 10:52
1
$\begingroup$

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.

$\endgroup$
  • $\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 '15 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$ – Robert NACIRI Feb 14 '15 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$ – Robert NACIRI Feb 14 '15 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$ – Robert NACIRI Feb 14 '15 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 '15 at 6:45

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.