<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">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:<br>
</div>
<blockquote
cite="mid:CAFewVt7VZC6+KgDdteXHx6hcMVrhMx_48Xbi1Kwvw2FU00DkSw@mail.gmail.com"
type="cite">
<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 moz-do-not-send="true"
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 moz-do-not-send="true"
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 moz-do-not-send="true"
href="https://briansmith.org/"
target="_blank">https://briansmith.org/</a></div>
<div><br>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Curves mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a>
<a class="moz-txt-link-freetext" href="https://moderncrypto.org/mailman/listinfo/curves">https://moderncrypto.org/mailman/listinfo/curves</a>
</pre>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
email: <a class="moz-txt-link-abbreviated" href="mailto:rstruik.ext@gmail.com">rstruik.ext@gmail.com</a> | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363</pre>
</body>
</html>