Hello Rene, Please note that in the code they are checking the *two* conditions (using your notation with r already mod n):
(r * Z^2 mod p == x(R) || (r + n < p && (r + n) * Z^2 mod p == x(R)) This should work for all cases where n<p. It will work also when p>n but in this case the first condition is enough. B.t.w. I never saw this trick. Best Regards, Ruggero From: Curves [mailto:[email protected]] On Behalf Of Rene Struik Sent: Wednesday, March 23, 2016 2:02 PM To: Brian Smith Cc: [email protected] Subject: Re: [curves] libsecp256k1's novel(?) ECDSA verification optimization 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 [email protected]<mailto:[email protected]> https://moderncrypto.org/mailman/listinfo/curves -- email: [email protected]<mailto:[email protected]> | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
