This can be done by a simple backtrack algorithm, we try to guess the digits of both primes starting from the outermost.

KT’s note: we found out that they were emirps by factorizing some small public moduluses with Yafu. And we had to factorize only one public key as the cipher text was 129 bytes, but only 1028 bits (started with 08 which is ~4 bits) and the smallest public key which was larger than 1028 bits was the n in the python code (it is ~1029 bits btw).

Last weekend I played on the Google CTF 2018 Quals which was one of the best CTFs I played recently. They separated the easy challenges i...… Continue reading