Munch out the bits!

CODEGATE2020{5e7c462214d48ea48045add289f70b0619a0552bdd4201d8c20cedbfd9ce43cd}

Deploy chall.py and output which is in binary_flag directory.

If you want to generate different output, simply run the below command in prob_src directory(obviously replace the output file :D).

python3 chall.py > output

Two stages:

• Stage 1
  • Solve the hidden number problem by knowing the bit length of hidden numbers(exposed as output)
  • Solve four times to recover four bit chunks of RSA prime p.
• Stage 2
  • Apply generalized coppersmith attack. See the entire paper here.

I gave bitlength of hidden four chunks. Also, I gave 200 / 4 = 50 queries(which exposes information of each chunks) to solve the hidden number problem. I tested that 50 queries are enough to fully recover each chunks.

Now the chunks are prepared to recover entire RSA prime p. Recover p and decrypt ciphertext to get flag.

• https://balsn.tw/ctf_writeup/20200208-codegatectf2020quals/#munch
• https://github.com/0ops/ctfs-2020/tree/master/codegate-quals/Crypto/MUNCH
• https://gist.github.com/hellman/019de1367f39ba73583d55aaddcbc1f8