Category: Crypto Difficulty: Medium/Hard Author: Robin_Jadoul
Pointing at a butterfly Is this a zero knowledge proof of decryption?
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.
1024 - bitlen(flag)bits of $k$ (since
Hhashes to only 1024 bits) and mount a lattice attack with HNP (due to vishiswoz and $in)