# 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.

• Found an implementation of Boneh Durfee attack Apr 30 '16 at 10:27
• What is your specific confusion? Where are you stuck? You say you want a small hint, but can you ask a more specific question about the first part you are confused about? Regarding your last sentence, what specifically don't you understand?
– D.W.
May 2 '16 at 11:02
• @D.W. I don't understand the shifting part (x-shift, y-shift) that has been mentioned in the paper and shifting is important. If I understand why shifting is important it will help me to understand the construction of lattice basis to be reduced by LLL. May 2 '16 at 15:18

## 1 Answer

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$.