search

ValarDragon / CTF-Crypto

Contains tools for solving RSA and other crypto problems in CTFs.
GNU General Public License v3.0
315 stars 68 forks source link

RSA tools #1

Open nguyen-tuonghuy opened 5 years ago

nguyen-tuonghuy commented 5 years ago

Hi,

I was looking at implementing the recovery of private key knowing the n/4 last bits and I saw it was on your TODO list.

Do you have any examples where it has been done by anyone yet ? It looks like there are many articles/surveys about that technique, but no practical implémentation yet... Thanks !

ValarDragon commented 5 years ago

The n/4 last bits attack requires an implementation of bivariate coppersmith. The only bivariate coppersmith implementation I know of is: https://github.com/mimoo/RSA-and-LLL-attacks, so perhaps you can adapt that?

I've also seen CTF teams use the n/4 attack in writeups, just haven't seen an implementation of it.

nguyen-tuonghuy commented 5 years ago

Ok,thank you for the answer.

I'll dig into the other repository as well. I also found out Sage was using a method called small_roots and it may be related to the coppersmith method.

ValarDragon commented 5 years ago

Small roots is univariate coppersmith, its actually used within the library already!