Attacking RSA with lattice reduction techniques (LLL)

This video is an explanation of Coppersmith's attack on RSA, which was later simplified by Howgrave-Graham, and the later attack by Boneh and Durfee, simplified as well by Herrmann and May. Both use LLL, the lattice reduction algorithm of Lenstra Lenstra Lovasz.
You can find the code on github here: github.com/mimoo/RSA-and-LLL-...
You can find a survey here: github.com/mimoo/RSA-and-LLL-...
You can find my blog here: www.cryptologie.net

[@zeroknowledge163]

If you have some cryptography/number theory background, IMO really good presentations that are very clear are the best way to get an introduction to applications like this. This presentation was really good and was very clear!

[@MaxJusticz]

Really exceptionally good video!

[@KemonoFren]

Great video!

[@siddhantsaurabh6098]

Why isn't boneh_durfee working for N = 187 i.e. 11*17, e = 107, delta = 0.26, m = 4. d should be 3 which is less than 187*0.26. Can you tell me what's wrong. What parameters i need to tweak to get the correct d?

[@hellmanh80]

Nice video! At 4:09, why the contiguous are does not cover the full plane, since the vectors are not colinear?

[@DavidWongTianyu]

yep, that's a mistake of mine! It should fill the whole plane.

[@safaeel6231]

hello i try to execut implementations of attacks on RSA through LLL reductions but i found this problem python coppersmith.py File "coppersmith.py", line 164 P. = PolynomialRing(ZmodN)#, implementation='NTL') ^ SyntaxError: invalid syntax can you help me

[@DavidWongTianyu]

+Safae El Atla you need Sage to execute it! Not python

[@SayoojSamuel]

This code is for Sage Script. Try running coppersmith.sage after installing Sage first

[@ziadchaoui5965]

Is it possible that there is small mistake in the definition of the polynomials gi,j (around minute 12). Shouldn't the index i range from 1 to m instead of 0 to m-1 ?

[@DavidWongTianyu]

+Ziad Chaoui if you go til' m, you lose f(x) => you lose x_0 as a root of your polynomial

[@ziadchaoui5965]

+David Wong but then how do you get the terms with N^m ? in the matrix ? ( great video btw )

[@DavidWongTianyu]

+Ziad Chaoui you do not want the term N^m in your polynomials! because it is equal to 0 modulo N^m. Where did you get the impression that you needed it inside your lattice?

[@ziadchaoui5965]

+David Wong Aren't the entries of the matrix on the next slide the factors of the different monomials that make up the polynomial? Or did I misunderstand something? For example where does the first entry in the matrix, "N^m" come from?

[@DavidWongTianyu]

+Ziad Chaoui uggg you're right, this has been a long time. Does the missing power comes from the function f?