# Now We Can Play!! Writeup
### Harekaze 2019 - crypto 200
We must recover plaintext `m`, which is flag. We first analyze how ciphertext `c1` and `c2` were generated.
``` pythonx = randint(2, p)r = randint(2, p)h = pow(g, x, p)c1 = pow(g, r, p)c2 = m * pow(h, r, p) % p```
We know public key `p`, `g`, and `h`. By solving the equations, we get the following formula,
``` pythonc2 = m * pow(g, x * r, p) % p   = m * pow(pow(g, r, p), x, p) % p   = m * pow(c1, x, p) % p```
Now it is time for analyzing `decrypt()` function.
It returns `m_` which is generated by
``` pythonrand = randint(2 ** 16, 2 ** 17)m_ = pow(3, rand, p) * c2 * inverse(pow(c1, sk, p), p) % p```
Solve the equation again, having a feeling that the equation is very similar to the upper equation having `c1` and `c2`. Since `x == sk`,
``` pythonx = skc2 = m * pow(c1, sk, p) % pm = c2 * inverse(pow(c1, sk, p)) % pm_ = pow(3, rand, p) * m % pm = m_ * inverse(pow(3, rand, p)) % p```
Therefore, by bruteforcing to know the value of `rand`, we directly recover `m`! We only have to brute for maximally `2 ** 16` times, so it is possible. By sending a single request with `in_c1 = c1` and `in_c2 = c2`, we may successfully recover the flag `m`. We checked the candidates by using the fact that the flag must be printable.
By bruteforcing `rand` for about 1 or 2 seconds, we get the flag:
```HarekazeCTF{im_caught_in_a_dr3am_and_m7_dr3ams_c0m3_tru3}```
Full exploit code: [solve.py](solve.py)
Original problem: [problem.py](problem.py)