Tags: okamoto-uchiyama crypto factoring 


- [Okamoto-Uchiyama cryptosystem](https://en.wikipedia.org/wiki/Okamoto%E2%80%93Uchiyama_cryptosystem) is being used
- The private information is the factorisation of `n`; if we have the prime factorisation, we can easily decrypt
- `q` is generated from `p`, and we can write `q = p^2 + 2^256 + delta`
- Bruteforce delta and solve for `p` by finding roots of the quartic `p^2 (p^2 + 2^256 + delta) - n`


Original writeup (https://jsur.in/posts/2020-08-09-poseidonctf-2020-writeups#discrete-log).