zer0pts CTF 2021
crypto
You should beat yoshiking at the rock-paper-scissors over 100 times without defeat. He decides his hand and give us its commitment before you input your hand. The commitment is encrypted by ElGamal encryption scheme.
It has better to focus on that the plaintext-space is quite small: 1 or 2 or 3. If we could see such like that the yoshiking's hand is even or not, or yoshiking's hand is quadratic residue or not.
The commitment is . When we assume is quadratic residue, is quadratic residue when is quadratic residue and is quadratic non-residue when is quadratic non-residue.
1 is always quadratic residue. Weather 2, 3 are quadratic residue or not is decided by . For example, if we find a good such that are quadratic non-residue, we can distinguish yoshiking's hand is 1 or otherwise by his commitment.
Thus, we can choose our hand adaptively in response to yoshiking's hand. Then we don't lose against yoshiking.