Rating:
[Link to original writeup](https://wrecktheline.com/writeups/imaginary-2021/#zkpod)
# ZKPoD (19 Solves, 400 points)
By Qyn
```
Pointing at a butterfly Is this a zero knowledge proof of decryption?
```
We're given an oracle which implements a combination of `DSA` and `RSA`. Initially, we're given the encrypted flag and we can provide encrypted data to the oracle which signs it for us, we can also note that we can maybe use a `chosen ciphertext` attack.
For the signing part, it generates a random integer `k` in range, `0, P-1`. It then calculates `r = g^k mod P` and `s = k - x * e (mod P - 1)`, where `e` is more or less random and we're given `r` and `s`.
We can notice that we can actually calculate:
```
rs = r^(-s)
rs = r^(-k + x * e)
rs = g^(k - k + x * e)
rs = g^(x * e)
```
Because `s` is done `mod P - 1`
_From here we could calculate `g^x`, but since `P - 1 % 2 == 0` and so `gcd(e, P-1)`, is most likely not `1`, we'd have to do 4 times as many requests._
Now we're going to apply the `RSA chosen ciphertext` attack. Suppose we send `ct * 2^e`, when this is decrypted, it will result in `pt * 2`. However, this is maybe done `mod N` if `pt * 2 > N`. We also send `ct` which is decrypted normally into `pt`, not done `mod N`. In the end, what we will receive is:
```
rs_1 = g^((2 * pt mod N) * e_1)
rs_2 = g^(pt * e_2)
```
To equalize we can calculate `rs_1 = rs_1^(e_2)` and `rs_2 = rs_2^(2 * e_1)`. Now we have the following two equations:
```
rs_1 = g^((2 * pt mod N) * e_1 * e_2)
rs_2 = g^(2 * pt * e_1 * e_2)
```
Now we can notice a difference if `2 * pt > N` since the exponent is done `mod phiN` and not `mod N`.
From here we can find the flag using a binary search, normally in RSA if `2 * pt > N`, then it will return an uneven number since `N` is odd, however, when `2 * pt < N`, it will return an even number because of the multiplication by `2`. We can also notice this difference in our algorithm if `rs_1 != rs_2`. We can repeat this with factors of `2`. Generally:
```py
if rs_1 == rs_2:
UB = (UB + LB) // 2
else:
LB = (UB + LB) // 2
```
And:
```
rs_1 = g^((2^i * pt mod N) * e_1 * e_2)
rs_2 = g^(2^i * pt * e_1 * e_2)
```
To speed up the search, we don't need to request `rs_1` and `rs_2` for every iteration, but rather set `rs_2 = rs_1` at the end of every iteration and do `rs_2 = rs_2^2`
And running the exploit will give us the flag:
`ictf{gr0up5_should_b3_pr1me_0rd3r_dummy}`
_Another method_
During the CTF, the flag didn't make much sense, but instead hinted towards `Pohlig-Hellman`.
However, `P - 1` isn't smooth enough to calculate `k`, but since it's partially smooth, we can calculate `k mod n` and from there we can calculate `x mod n`.
From a _partial_ `Pohlig-Hellman` algorithm (See `solve2.py` for the algorithm), we can derive `k mod 83675832665710`. From here we can solve for `x` in the equation for `s`:
```
s = k - x * e mod P_1
s + x * e = k mod P_1
x * e = k - s mod P_1
x = (k - s) * e^(-1) mod P_1
```
Where we can fill in for `k`:
```
x = ((k mod 83675832665710) - s) * e^(-1) mod P_1
P_2 = 83675832665710
x = (k - s) * e^(-1) mod P_2
```
And from here all the values are known and we can perform a the same binary search as in `method 1`, note that we can find the flag faster using this method, since we know `x mod P_2` and therefore we should be able to find `x` in 45 queries.
And also this will give the flag:
`ictf{gr0up5_should_b3_pr1me_0rd3r_dummy}`
