I am trying to understand various attacks on RSA and I believe that the only way to fully understand an algorithm is to implement it. I am trying to implement the code in this paper: Dan Boneh and Gleen Durfee, Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$, in proceedings of Eurocrypt 1999. 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\pmod N$, with $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, and finding $x$ and $y$ to recover the private key.


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.