**Tags:** coppersmith factoring goldwasser-micali

Rating:

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://www.josephsurin.me/posts/2020-09-20-downunderctf-2020-writeups#1337crypt)

Original writeup (https://www.josephsurin.me/posts/2020-09-20-downunderctf-2020-writeups#1337crypt).