Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component $d$with a further relaxed condition. If $d$satisfies:

Then we can use Boneh-Durfee attack to retrive $d$

this, using a graphical directed point of view, can be seen as:

Consider for first, see that

As stated above, the RSA's totient function can be espressed as:

continuing with the equation, we see that

and if we decide to consider and , we will have:

At this point, finding is equivalent to find the 2 small solutions and to the congruence

now let and this will preserve the scomposed subtraction

consider (with any ), we deduct that must be really closed to because is in the same order of the length of (so ), we will get

Sage Implementation