[curves] libsecp256k1's novel(?) ECDSA verification optimization

[Rene Struik]

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 <gmaxwell at gmail.com> wrote:
>> Brian Smith <brian at 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves


-- 
email: rstruik.ext at gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160614/14901ad8/attachment.html>