Tags: coppersmith factoring goldwasser-micali
- 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!