Tags: okamoto-uchiyama crypto factoring

Rating:

tldr;
- [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).