1
$\begingroup$

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.

$\endgroup$

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.