[curves] libsecp256k1's novel(?) ECDSA verification optimization
Rene Struik
rstruik.ext at gmail.com
Tue Jun 14 17:11:36 PDT 2016
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
More information about the Curves
mailing list