## #ZKPoD

**Category:** Crypto
**Difficulty:** Medium/Hard
**Author:** Robin_Jadoul

### #Description

*Pointing at a butterfly* Is this a zero knowledge proof of decryption?

### #Distribution

### #Deploy notes

Needs `flag.txt`

, `zkpod.py`

and `private.txt`

### #Solution

The protocol provides an RSA-encrypted version of the flag, and offers to take any ciphertext, decrypt it and sign a fixed message with it as private key, by computing a Schnorr signature.
The signature consists of $(r, s)$ with $r = g^k \pmod P$ and $s = k - m\cdot H(r || M)$, where $m$ is the decrypted message, $M$ is the fixed signature message and $k$ is a uniform random number in the range $[0, P - 1)$.
With the Legendre symbol, we can deduce the parity of $k$.
When $E = H(r || M)$ is not divisible by 2, the product $m\cdot E$ is only even when $m$ is.
Combining these two observations allows us to deduce the parity of $m$ from the parities of $s$ and $k$, exactly when $E$ is odd, and so 50% of the time.
If $E$ is even, we simply try the same RSA ciphertext again to try again.

From this, we can implement a standard LSB oracle attack on RSA to recover the flag.

#### #Some other solutions, found by players:

- Binary search $a$ such that $ax = N$ thanks to being able to distinguish $a < N < p - 1$ (due to A~Z)
- Extended version of the LSB oracle with partial Pohlig-Hellman (due to NeketmanX)
- Recover
`1024 - bitlen(flag)`

bits of $k$ (since `H`

hashes to only 1024 bits) and mount a lattice attack with HNP (due to vishiswoz and $in)
- Get $g^x$ and $g^{x/2 \mod N}$ to recover a single bit at a time jby checking $g^x \overset{?}{=} \left(g^{x/2 \mod N}\right)^2 \mod p$ (due to rbtree)