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


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:

enter image description here

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:

enter image description here

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

  • $\begingroup$ 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$$ $\endgroup$ – gammatester Nov 18 '17 at 18:34
  • $\begingroup$ Hi, Thnx tof the tip. But how do you become: f(k,p+q)+1+k(p−1)(q−1)=−kn+kpq? $\endgroup$ – WinstonCherf Nov 18 '17 at 18:42
  • $\begingroup$ 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. $\endgroup$ – gammatester Nov 18 '17 at 18:49
  • $\begingroup$ 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 $\endgroup$ – WinstonCherf Nov 18 '17 at 19:34
  • $\begingroup$ 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$$ $\endgroup$ – gammatester Nov 18 '17 at 20:03

Your Answer

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

Browse other questions tagged or ask your own question.