0
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

Yes, pretty much the same groups usable for ECDSA are usable for Schnorr signature. That was in [Sc91] (see bibliography in this question):

It is possible to implement the above signature and authentication scheme using a finite group $G$ other than the subgroup $\mathbb Z_p^*$ of units in $\mathbb Z_p$ (..) Examples of suitable groups are e.g. class groups and elliptic curves $E(K)$ over a finite field $K$.

It looks like you invented yet another variant of the Schnorr signature algorithm for elliptic curves, not among the about 6 in this answer. Yours sends a group element rather than a hash as the first part of the signature (thus more directly matching the transformation to signature of the Schnorr indetification protocol, and allowing a more direct proof of security). This has a strong taste of EC-FSDSA (Elliptic Curve Full Schnorr Digital Signature Algorithm) of ISO/IEC 14888-3 (OID 1.0.14888.3.0.12), but:

  • For some reason you compute $H(m\|x_0)$ rather than $H(x_0\|y_0\|m)$ in said standard; hereafter I write $H(\dots)$. For an ideal hash and proofs in the ROM, hashing $m$ first or second is immaterial, and I can't decide if it makes any security difference for practical hashes. Not hashing $y_0$ might cost some security.
  • Your verification procedure omits to verify that $S_0$ is a point on the curve, which seems risky since you perform point addition on that. The standard mandates this check.
  • My understanding is that the standard does $Q=-a\times P$ (as suggested by Schnorr as soon a [Sc89]), so that verification can compute $s_2\times P+H(\dots)\times Q$ and compare it to $S_0$, with two advantages:
    • the computation of $s_2\times P+H(\dots)\times Q$ can use the simplest forms of Shamir's trick, or others
    • checking that $S_0$ is a point on the curve becomes redundant.

Note: for elliptic curves $y^2\equiv x^3–3x+b\pmod p$ at least (including NIST's FIPS 186-4 curves over prime fields), while you are at not hashing $y_0$ and using something non-standard, you could as well omit $y_0$ from the signature, with verification computing $s_2\times P+H(\dots)\times Q$ and comparing it's $x$ coordinate to $x_0$. That shortens the signature from $6b$ to $4b$ for $b$-bit security, and (for ideal hash) costs at most 1 bit of security (perhaps nothing), since $y$ can be found from $x$ within sign.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer! I have only one question left. Why should the EC-SDSA rather be implemented with $H(x_0||y_0||m)$ than $H(x_0||m)$? What is the profit of inlcuding the $y$-coordinate? (I do not have access to the ISO/IEC 14888-3 paper explaining the standards.) $\endgroup$ – Luca Jul 18 '17 at 21:00
  • 1
    $\begingroup$ @Luca: EC-SDSA (resp. EC-SDSA-opt and EC-FSDSA) use $H(x_0\|y_0\|m)$ (resp. $H(x_0\|m)$ and $x_0\|y_0$ ) as the first component of the signature. Sending the un-hashed $k×P$ (as EC-FSDSA and you do) allows a simpler proof, but eats more space if $y_0$ is included. I do not know a good reason to use $y_0$ in either EC-SDSA or EC-FSDSA, at least for NIST's FIPS 186-4 curves over prime fields, where for ideal hashes $y_0$ can demonstrably be replaced by a single bit, hence gives at most 1 bit of security. My understanding is that [NSW09] concurs that we can safely remove $y_0$ as in EC-SDSA-opt. $\endgroup$ – fgrieu Jul 18 '17 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.