RSA can be pretty based
Files given:
In the key.pub file, one sees a lot of “A” in it, this implies that most of the binary digits of the public key is actually “0”, meaning that \(n\) has a low hamming weight. This suggests that its factors have low hamming weights as well and is extremely similar to a challenge in Google CTF 2020 - yafm. Experience playing CTF helps a lot!
The idea behind this is that we can brute force the factors mod \(2^i\) as we increase \(i\) and lift our solutions up. However this gives us many solutions in general hence we only take those with a very low hamming weight, in our case we chose 32768 as it seems decently big but the script will run in time for the CTF. With this we are only left with brute forcing and modified the script from this writeup to get our factorization.
The solution script can be found at solve.py
Flag:
WH2021{BASED_R5A_1N_BASE_64_Is_BASICALY_BASIC}