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/)