I tried to rewrite the Schnorr signature algorithm for elliptic curves but I wanted to be sure to have not done any errors. So I would be very happy if someone could look over this algorithm and tell me if I have done anything wrong, or not precise enough:
Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ (first question, is it here as in the ECDSA, that either $q=p$ an odd prime or $q=2^m$?) with parameters such that $E$ is a cryptographically safe curve.
Key Generation:
Choose $P\in E(\mathbb{F}_q)$ of prime order $l$, where $l$ is a large prime.
Choose $1 < a < l$ random and calculate $Q = a*P$. Then the public information is $E, \mathbb{F}_q, Q, P$ and the private signature key is $a$.
Signature Scheme:
- Choose a random $1 \leq k < l$
- Compute $S_0 = kP = (x_0,y_0)$
- Compute $s_1 = H(m||x_0)$, where $H$ is a hash function, $x_0$ is the integer value of $x_0$ and $m$ is the message.
- Compute $s_2 \equiv k + a*s_1 \text{ (mod }l)$
The digital signature is $(S_0,s_2)$ and Alice sends $(m, (S_0,s_2))$ to Bob.
Verification
Bob verifies if $s_2*P=S_0+H(m||x_0)*Q$.
This works since: $$s_2*P=S_0+H(m||x_0)*Q$$ $$\Leftrightarrow s_2*P-H(m||x_0)*Q = S_0$$ $$\Leftrightarrow (k+a*s_1)-H(m||x_0)*a*P = S_0$$ $$\Leftrightarrow kP + a*H(m||x_0)*P-a*H(m||x_0)P=S_0=k*P$$