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}

Original writeup (https://wrecktheline.com/writeups/imaginary-2021/#zkpod).