<div dir="ltr"><div>Hi,</div><div><br></div><div>[I am not sure if boring topics like ECDSA are appropriate for this list. I hope this is interesting enough.]</div><div><br></div><div>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.</div><div><br></div><div>A while back I stumbled across an interesting optimization [1] in libsecp256k1. The optimization completely avoids the second inversion during verification.</div><div><br></div><div>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.</div><div><br></div><div>I asked Greg Maxwell, the author of that code, about it and he didn't know of anybody else using this optimization.</div><div><br></div><div>The optimization has two important properties:</div><div>1. It make verification notably (but not hugely) faster.</div><div>2. It reduces the amount of code required by an enjoyable amount, if one is writing prime- specific specialized inversion routines.</div><div><br></div><div>Two questions:</div><div><br></div><div>1. Does anybody know of prior published software or papers documenting this?</div><div><br></div><div>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?</div><div><br></div>[1] <a href="https://github.com/bitcoin/secp256k1/blob/269d4227038b188128353235a272a8f030c307b1/src/ecdsa_impl.h#L225-L253">https://github.com/bitcoin/secp256k1/blob/269d4227038b188128353235a272a8f030c307b1/src/ecdsa_impl.h#L225-L253</a> (shortened: <a href="https://git.io/vad3K">https://git.io/vad3K</a>)<div><div><div><br></div><div>Thanks,</div><div>Brian</div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><a href="https://briansmith.org/" target="_blank">https://briansmith.org/</a></div><div><br></div></div></div></div></div></div></div>
</div></div></div>