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 [email protected] https://moderncrypto.org/mailman/listinfo/curves
