tldr;
- flag is encrypted using a Goldwasser-Micali cryptosystem
- to decrypt, we need to factorise the given `n`
- we are given a `hint = int(D*sqrt(p) + D*sqrt(q))` where `D` is some known constant
- we can use `hint` to recover an approximation for `p` and `q`
- combining the upper bits of `p` and `q` with the fact that `n = pq`, we can use Coppersmith's theorem to recover `p` and `q` completely
- decrypt the ciphertext to get the flag!

[DUCTF GitHub](https://github.com/DownUnderCTF/Challenges_2020_public/tree/master/crypto/1337crypt)

[writeup](https://jsur.in/posts/2020-09-20-downunderctf-2020-writeups#1337crypt)

Original writeup (https://jsur.in/posts/2020-09-20-downunderctf-2020-writeups#1337crypt).