Hi Brian:
With Ed25519, the signature is (r,s), where R=sG + hQ, h=H(r,Q,m), and
wher r is a compressed version of R (with y-coordinate of R showing in GFp).
Thus, if one verifies such a signature (r,s) w.r.t. public key Q, one
computes h=H(r,Q,m), R':=sG + hQ, and can do the check r ~ R' in GFp
(without corner cases that arise in ECDSA because of Zp to Zn
conversion). So, I do not see how one would end up having conditions
that check depending on whether r< q- 8n, r<q-7n, .... in the EdDSA
case. Doesn't the "projective/affine test backwards" test always work in
GFp here? (see my March 23th note below). But, perhaps, I am missing
something ...
As final note, with ECDSA and EdDSA, one can also speed-up verification
by massaging the equation R=sG + h Q and turning this into an equation
of the type v R=s0 G0 + s1 G1 + u Q, where each scalar u, v, s0, s1 is
half-size and performing a multiple-point multiplication (here, G0:=G is
base point, G1:= tG, t=2^{128}, and (u,v) can be computed from h=u/v via
the Extended Euclidean Algorithm). {Obviously, this does require some Zn
arithmetic for EEA and point decompression for R, so the roughly 30%
speed-up has some trade-offs}. Details are in an old SAC 2005 paper.
Some verification in V2V networks can use this method (P1609.2). With
the "bitcoin" curve secp256k1, one can use endomorphisms to achieve
similar acceleration as in the SAC2005 paper, via the GLV method (this
also results in half-size scalars).
Best regards, Rene
[excerpt email RS as of March 23, 2016, 9.01am EST]
The equation is always correct, had ECDSA been defined with r=x(R),
i.e., without the mod n reduction step to compute r.
On 6/14/2016 5:49 PM, Brian Smith wrote:
Gregory Maxwell <gmaxw...@gmail.com> wrote:
Brian Smith <br...@briansmith.org> wrote:
[I am not sure if boring topics like ECDSA are appropriate for this list. I
hope this is interesting enough.]
It's no less useful for Schnorr (just even more obvious there), and in
that case it permits a verification to be implemented completely
without any modular inversion.
Yes, that's a good point. I will be implementing it for EdDSA,
specifically Ed25519, soon. Since Ed25519 has cofactor > 1, the trick
must be generalized to try more than two multiples of `r`.
As noted by Rene Struik the implementation must check all conditions
that result from modular reduction, and as noted by Ruggero SUSELLA,
ours does. Libsecp256k1 also includes test vectors that try the
conditions/decisions of these branches, so if any were omitted the
tests would fail. I would encourage other implementers who adopted
this optimization to also include specific tests for it passing and
failing each branch-- to avoid a later developer optimizing away an
'impossible' case. Though these cases are 'rare', the triggering
conditions can be generated by backwards computing public keys from
constructed signatures where R.x is a very high value.
Good point. I already had to help another person fix their implementation.
I have attached some test vectors to this message for ECDSA P-256 and
P-384 that were based on what you suggested above: Choose an (r, s)
where r is in the range we want to test, and then recover the public
key from the signature. However, I wasn't able to generate test
vectors that test the case where r == n this way, since `n` is not a
perfect square. So, if anybody has test vectors for the r == n case,
and/or r == n - 1 and r == n + 1, for P-256 and P-384 in particular, I
would love to get them.
For ECDSA the approach is one that loses its utility with larger
trace/co-factor; as there end up being many cases to check; so it may
not be worthwhile for some curves.
Also, for Ed25519, your suggested method of generating test vectors
doesn't work, because public keys can't be recovered from EdDSA
signatures. So, I am hoping somebody can share test vectors for
Ed25519 that cover all the cases: r < q - 8n, r < q - 7n, ... r < q -
n, r == n, n < r < q, or suggest a realistic method for finding some.
Thanks for sharing!
Cheers,
Brian
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
--
email: rstruik....@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
