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

[Brian Smith]

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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160323/9b6e6b2b/attachment.html>