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

[Brian Smith]

Rene Struik <rstruik.ext at gmail.com> wrote:
> 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 ...

I think the test vectors are still interesting because they would
catch the case where people are wrongly trying to use the trick by
also testing r + in for i > 1. For example, in the case of ECDSA, one
implementation already was already wrongly testing r + n == X (mod q)
even when r > q - n, which was just wrong. You can imagine how such
bugs could happen due to people trying to generalize the logic too
much. In fact, I think such bugs are likely.

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

I believe you may be referring to
http://cacr.uwaterloo.ca/techreports/2005/cacr2005-28.pdf?

Thanks,
Brian