Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component dwith a further relaxed condition. If dsatisfies:
d<N0.292
Then we can use Boneh-Durfee attack to retrive d
this, using a graphical directed point of view, can be seen as:
{E,n}Pd<N0.292{d}
Consider d<Nifor first, see that
1=ed+2kϕ(N)
As stated above, the RSA's totient function can be espressed as:
ϕ(N)=(p−1)(q−1)=N−q−p+1
continuing with the equation, we see that
1=ed+k(2N+1−2p+q)
and if we decide to consider x=2N+1and y=2p+q, we will have:
1=ed+k(x+y)
At this point, finding dis equivalent to find the 2 small solutions xand yto the congruence
f(x,y)≡k(x+y)≡1(mode)k(x+y)≡1(mode)
now let s=−2p+qand A=2N+1this will preserve the scomposed ϕ(N)subtraction
k(A+s)≡1(mode)
consider e=Nα(with any α), we deduct that αmust be really closed to 1because eis in the same order of the length of N(so e=N∼1−), we will get