[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:
```pyif rs_1 == rs_2:    UB = (UB + LB) // 2else:    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_1s + x * e = k mod P_1x * e = k - s mod P_1x = (k - s) * e^(-1) mod P_1```
Where we can fill in for `k`:
```x = ((k mod 83675832665710) - s) * e^(-1) mod P_1P_2 = 83675832665710x = (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}`