This challenge was solved by and the write up was written by one of my teammates, NGG.

There was a message encrypted with something between RSA and Rabin encryption schemes.

We factorized n with yafu.

e doesn’t have a modular inverse because it’s even, so first we RSA-decrypted with its “odd part”.

RSA-decrypting with e/32 gave that

Decrypting it with Rabin 5 times in a row gave several possibilities for m % n.

m % n is one of:

There was an assert in the encryption code that said the length of the flag is 50 (which means 400 bits), but these numbers were around 310 bits only.

We needed to find a multiple of n to add to m%n so that m will be 400 bits, and hex-decoding it gives ‘hitcon{…}’.

We had lower and upper limits because of the needed string’s beginning, we had to brute-force between those values and check if it only contains ascii characters and it ends with ‘}’.

It was too slow, but we could speed up the process by finding one possible multiplier such that it ends with ‘}’, and then try every 256th multipliers only (because those are the ones that start with ‘}’)

Here is the full python code that does the part after decrypting with RSA.

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