We have an oracle that takes a cipher text encrypted with the public key $(n,g)$ and gives us the least significant bit of the plain text

Thanks to the [Paillier Cryptosystem](https://en.wikipedia.org/wiki/Paillier_cryptosystem) we can send $c$ so that:
$$dec(c) = flag - k \mod n$$
or
$$dec(c) = flag \cdot k \mod n$$

Check out the full write up [https://theromanxpl0it.github.io/ctf_codeblue2017/paillier/](https://theromanxpl0it.github.io/ctf_codeblue2017/paillier/)

Original writeup (https://theromanxpl0it.github.io/ctf_codeblue2017/paillier/).