<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style></style></head><body bgcolor=white lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>Hello Rene,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>Please note that in the code they are checking the *<b>two</b>* conditions (using your notation with r already mod n):<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>(r * Z^2 mod p == x(R) || (r + n < p && (r + n) * Z^2 mod p == x(R))<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>B.t.w. I never saw this trick.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>Best Regards,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'>Ruggero<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#002052'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0mm 0mm 0mm'><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'> Curves [mailto:curves-bounces@moderncrypto.org] <b>On Behalf Of </b>Rene Struik<br><b>Sent:</b> Wednesday, March 23, 2016 2:02 PM<br><b>To:</b> Brian Smith<br><b>Cc:</b> curves@moderncrypto.org<br><b>Subject:</b> Re: [curves] libsecp256k1's novel(?) ECDSA verification optimization<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>Hi Brian:<br><br>With ECDSA, one has R:=(1/s)(eG+rQ), where e:=h(m), and r= x(R) mod n.<br><br>If R=(X, Y, Z) in Jacobian coordinates, then x(R)=X/(Z^2), where computations are over GFp.<br><br>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.<br><br>The equation is always correct, had ECDSA been defined with r=x(R), i.e., without the mod n reduction step to compute r.<br><br>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.<br><br>Best regards, Rene<br><br><br>On 3/23/2016 8:16 AM, Brian Smith wrote:<o:p></o:p></p></div><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><div><div><p class=MsoNormal>Hi,<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>[I am not sure if boring topics like ECDSA are appropriate for this list. I hope this is interesting enough.]<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>A while back I stumbled across an interesting optimization [1] in libsecp256k1. The optimization completely avoids the second inversion during verification.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I asked Greg Maxwell, the author of that code, about it and he didn't know of anybody else using this optimization.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>The optimization has two important properties:<o:p></o:p></p></div><div><p class=MsoNormal>1. It make verification notably (but not hugely) faster.<o:p></o:p></p></div><div><p class=MsoNormal>2. It reduces the amount of code required by an enjoyable amount, if one is writing prime- specific specialized inversion routines.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Two questions:<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>1. Does anybody know of prior published software or papers documenting this?<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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?<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><p class=MsoNormal>[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>) <o:p></o:p></p><div><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Thanks,<o:p></o:p></p></div><div><p class=MsoNormal>Brian<o:p></o:p></p></div><p class=MsoNormal>-- <o:p></o:p></p><div><div><div><div><div><div><div><p class=MsoNormal><a href="https://briansmith.org/" target="_blank">https://briansmith.org/</a><o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div></div></div></div></div></div></div></div></div></div><p class=MsoNormal><br><br><br><o:p></o:p></p><pre>_______________________________________________<o:p></o:p></pre><pre>Curves mailing list<o:p></o:p></pre><pre><a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a><o:p></o:p></pre><pre><a href="https://moderncrypto.org/mailman/listinfo/curves">https://moderncrypto.org/mailman/listinfo/curves</a><o:p></o:p></pre></blockquote><p class=MsoNormal><br><br><br><o:p></o:p></p><pre>-- <o:p></o:p></pre><pre>email: <a href="mailto:rstruik.ext@gmail.com">rstruik.ext@gmail.com</a> | Skype: rstruik<o:p></o:p></pre><pre>cell: +1 (647) 867-5658 | US: +1 (415) 690-7363<o:p></o:p></pre></div></body></html>