Open hyunsikjeong opened 3 years ago
Here is 2 related CTF challenges: WMCTF 2020 babySum && Sum. The former is a instance of 120-n
low-density (d = 0.8
) subset-sum problem, and the latter is a 180-n
one.
You can find the challenges and writeup here. 😄
Some Notes:
120-n
instance, and hundreds of hours to solve the 180-n
one, by using lattice reduction. 180-n
one, by renting cloud computing servers, equipped with nearly a hundred of CPU cores, and running the BKZ algorithms for several hours.I am not a professor in this area and just made the two challenges for fun ðŸ˜, if you find any mistake, please feel free to contact me via soreatu@gmail.com
Thank you for sharing, @soreatu ! I love the idea of the challenge "Sum".
Breaking DSA with LCG nonces is a known application of LLL, and appeared in some CTFs DEFCON 2019 Quals: https://github.com/pcw109550/write-up/tree/master/2019/DEFCON/tania
Two Hidden Number Problems have appeared in DownUnderCTF, but both are relatively straightforward writeups: https://rkm0959.tistory.com/162
N1CTF 2019 : guess_ex - kinda like a hidden number problem https://github.com/Nu1LCTF/n1ctf-2019/tree/master/CRYPTO/guess_ex SECCON 2020 sharsable -lattice construction using number theory bounds https://rkm0959.tistory.com/165
If there're any related CTF challenges, feel free to left comments here.