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?
$\begingroup$
$\endgroup$
6
-
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$– CodesInChaosCommented 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$– Robert NACIRICommented Feb 14, 2015 at 8:48
-
1$\begingroup$ @CodesInChaos Have any solution for this $p_1 - p_2 = 2$? $\endgroup$– LisbethCommented Feb 14, 2015 at 19:18
-
$\begingroup$ How about this? $\endgroup$– mikeazoCommented 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 ♦Commented Apr 15, 2015 at 10:52
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
7
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$– LisbethCommented 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$ Commented 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$ Commented 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$ Commented 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$– LisbethCommented Feb 15, 2015 at 6:45