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)