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

[Rene Struik]

Apologies for not providing the link to the SAC 2005 paper myself. Your 
link is correct.

I do agree that testing corner cases to catch flaws has merit. (I just 
did not see how the inverse of the mapping from Zp to Zn comes into play 
with EdDSA.)

Best regards, Rene

On 6/14/2016 7:30 PM, Brian Smith wrote:
> 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


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