[curves] libsecp256k1's novel(?) ECDSA verification optimization
Rene Struik
rstruik.ext at gmail.com
Wed Mar 23 06:01:35 PDT 2016
Hi Brian:
With ECDSA, one has R:=(1/s)(eG+rQ), where e:=h(m), and r= x(R) mod n.
If R=(X, Y, Z) in Jacobian coordinates, then x(R)=X/(Z^2), where
computations are over GFp.
One has x(R) Z^2 = X, which is equivalent to r Z^2 = X only if the
modular reduction mod n does not do anything. For secp256k1, one has
n<p, so for the tiny fraction of x(R)'s in the interval [n,p-1], this
yields the wrong result.
The equation is always correct, had ECDSA been defined with r=x(R),
i.e., without the mod n reduction step to compute r.
Please note that if x(R) in the interval [n,p-1], then r=x(R) mod n is
in the interval [0,p-n-1], so one could still apply the trick in the
vast majority of cases, by simply incorporating a test on whether r >
p-n-1 and applying the trick if so.
Best regards, Rene
On 3/23/2016 8:16 AM, Brian Smith wrote:
> Hi,
>
> [I am not sure if boring topics like ECDSA are appropriate for this
> list. I hope this is interesting enough.]
>
> ECDSA signature verification is quite expensive. A big part of why it
> is expensive is the two inversions--one mod q, one mod n--that are
> typically used.
>
> A while back I stumbled across an interesting optimization [1] in
> libsecp256k1. The optimization completely avoids the second inversion
> during verification.
>
> The comments in the code explain how, but here's a rough summary:
> Normally we convert the Jacobian coordinates (X, Y, Z) of the point
> multiplication result to affine (X, Y) so that the affine X coordinate
> can be compared to the signature's R component. The conversion to
> affine coordinates requires the inversion of Z. But, instead of doing
> that, we can simply multiply the signature's R component by Z**2 and
> then compare it with the *Jacobian* X coordinate, avoiding any inversion.
>
> I asked Greg Maxwell, the author of that code, about it and he didn't
> know of anybody else using this optimization.
>
> The optimization has two important properties:
> 1. It make verification notably (but not hugely) faster.
> 2. It reduces the amount of code required by an enjoyable amount, if
> one is writing prime- specific specialized inversion routines.
>
> Two questions:
>
> 1. Does anybody know of prior published software or papers documenting
> this?
>
> 2. Does anybody know why it would be a bad idea to use this technique?
> I.e. am I overlooking some reason why it doesn't actually work?
>
> [1]
> https://github.com/bitcoin/secp256k1/blob/269d4227038b188128353235a272a8f030c307b1/src/ecdsa_impl.h#L225-L253
> (shortened: https://git.io/vad3K)
>
> Thanks,
> Brian
> --
> https://briansmith.org/
>
>
>
> _______________________________________________
> 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/20160323/a15dd62d/attachment.html>
More information about the Curves
mailing list