Algorithm for Boneh and Durfee attack on RSA I am trying to understand various attacks on RSA and I believe that they only way to fully understand the algorithm is to implement it. I am trying to implement the code in this paper (pdf) (Private Key $d$ less than $N^{0.292}$) but after spending hours I am having problem writing the algorithm needed to implement the code. A small hint to help me implement the code would be appreciated.

I am familiar with LLL (lattice reduction) and how RSA works, so just small hint would be really helpful.

I understand that we want to solve the polynomial $f(x, y) = x(A + y) - 1 = 0 \ (mod \ e)$ s.t. $x = k$, $y = -p-q$ and $A = N+1$, but I don't understand the shifting part and construction of lattice basis to be used in LLL.
Our goal is to find a root $(x_0,y_0)$ in $\mathbb{Z}_e$ of the polynomial $f(x,y) = x(A+y)-1$. Finding roots of a polynomial in any $\mathbb{Z}_n$ isn't an easy job, in order to solve the problem Coppersmith had the idea to reduce to problem to finding a root $(x_0,y_0)$ over $\mathbb{Q}$ of some other polynomial $f'$ related to $f$.



About Coppersmith method

His technique relies on building a lattice $\mathcal{L}$ whose entries are coefficients of some polynomials (x and y shifts) having the same root $(x_0,y_0)$ as $f$. Thanks to this property, every linear combination of x and y shifts will be solved by $(x_0,y_0)$. Once $\mathcal{L}$ is built, it can be reduced using LLL algorithm (the same matrix is represented in a different basis, computationally easier to manage due to small coefficients) and from that get two polynomials $g_1,g_2$ (as linear combinations of $\mathcal{L}$ elements) such that $g_1(x_0,y_0) = g_2(x_0,y_0) = 0$. 



Why x and y shifts?

First of all, let's define what a shift is. Those are derived from different powers of $x$, $y$, $f$ and $e$. $g_{i,\phi}$ and $h_{j,\phi}$ are respectively $x$ and $y$ shifts:

$$g_{i,\phi}(x,y)=x^i f^{\phi} e^{m-\phi}$$ 
$$h_{j,\phi}(x,y)=y^j f^{\phi} e^{m-\phi}$$

Where $\phi \in (0,m)$, $i \in (0,m-\phi)$ and $j \in (0,t)$. Once $m$ is defined, it's easy to compute the set of shifts. Indeed, $m$ is the maximum degree of $x$ in shifts, whereas $t+m$ is the maximum degree of $y$. 

That's all we needed: a bunch of polynomials (up to a certain degree) having the same root as $f$.