# Boneh and Durfee attack on RSA

I am a maths teacher and I'm trying to understand the Boneh and Durfee attack on RSA. I am not very familiar with cryptography. I found a dutch scripting about it.

I know that:

$e*d\equiv1+k*\phi(n)$

$\phi(n)=n+1-(p+q)$

I become the function $f(x,y)=xy-(n+1)x-1$, but next I do not understand why you know that $f(k, p+q)\equiv0\,(mod\,e)?$

Further, they choose modulus $M=e^2$ and choose some polynomials of which we know for sure that $(x,y)=(k,p+q)$ is a root of $f(x,y)\,(mod\,e^2)$.

These polynomials are:

How can I see that $(x,y)=(k,p+q)$ is a root of all of these polynomials?

And then, they go on using a table hat contains the coëfficiënts of the polynomials:

I do not understand the meaning of the columns. For example the columns of $g_{0,1}$.

• Hint for the first question: Assuming $n=pq, \;\phi(n)=(p-1)(q-1)$ you get $$f(k,p+q)+1+k(p-1)(q-1)=-kn+kpq=k(pq-n)=0,$$ $$f(k,p+q)= -(1+k(p-1)(q-1))=-ed$$ – gammatester Nov 18 '17 at 18:34
• Hi, Thnx tof the tip. But how do you become: f(k,p+q)+1+k(p−1)(q−1)=−kn+kpq? – WinstonCherf Nov 18 '17 at 18:42
• Just expand the two terms $$f(k,p+q) =k (p + q) - (n + 1) k - 1 = k p + k q - k n - k - 1$$ $$1+k(p-1)(q-1) =1 + kpq - kp - kq + k$$ Now add the right hand sides and cancel. – gammatester Nov 18 '17 at 18:49
• Very sorry, I just made lots of calculations but I still don't understand it. I do not become the answer of my question one. I don't understand the steps: f(k,p+q)+1+k(p−1)(q−1)=−kn+kpq=k(pq−n)=0 and f(k,p+q)=−(1+k(p−1)(q−1))=−ed – WinstonCherf Nov 18 '17 at 19:34
• Adding the two expanded equations gives: $$f(k,p+q) +1+k(p-1)(q-1)\\ = kp + kq - kn - k - 1 + 1 + kpq - kp - kq + k \\= (kp - kp) + (kq - kq) - (k - k) - (1 -1) + kpq - kn\\ = k(pq-n) = 0$$ $$f(k,p+q) = - (1+k(p-1)(q-1)) = -(1 +k\phi(n)) = -ed$$ and therefore $$f(k,p+q) \equiv -ed \equiv 0 \pmod e$$ – gammatester Nov 18 '17 at 20:03