[curves] libsecp256k1's novel(?) ECDSA verification optimization
brian at briansmith.org
Wed Mar 23 05:16:03 PDT 2016
[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
A while back I stumbled across an interesting optimization  in
libsecp256k1. The optimization completely avoids the second inversion
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.
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?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Curves