10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Found an implementation of Boneh Durfee attack $\endgroup$ – Reversal Apr 30 '16 at 10:27
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. May 2 '16 at 11:02
  • $\begingroup$ @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. $\endgroup$ – Node.JS May 2 '16 at 15:18
4
+75
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.