Tags: crypto
Rating:
# 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.
``` python
x = 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,
``` python
c2 = 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
``` python
rand = 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`,
``` python
x = sk
c2 = m * pow(c1, sk, p) % p
m = c2 * inverse(pow(c1, sk, p)) % p
m_ = pow(3, rand, p) * m % p
m = 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)
