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)

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