<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: With Ed25519, the signature is (r,s), where R=sG + hQ, h=H(r,Q,m), and wher r is a compressed version of R (with y-coordinate of R showing in GFp). Thus, if one verifies such a signature (r,s) w.r.t. public key Q, one computes h=H(r,Q,m), R':=sG + hQ, and can do the check r ~ R' in GFp (without corner cases that arise in ECDSA because of Zp to Zn conversion). So, I do not see how one would end up having conditions that check depending on whether r< q- 8n, r<q-7n, .... in the EdDSA case. Doesn't the "projective/affine test backwards" test always work in GFp here? (see my March 23th note below). But, perhaps, I am missing something ... As final note, with ECDSA and EdDSA, one can also speed-up verification by massaging the equation R=sG + h Q and turning this into an equation of the type v R=s0 G0 + s1 G1 + u Q, where each scalar u, v, s0, s1 is half-size and performing a multiple-point multiplication (here, G0:=G is base point, G1:= tG, t=2^{128}, and (u,v) can be computed from h=u/v via the Extended Euclidean Algorithm). {Obviously, this does require some Zn arithmetic for EEA and point decompression for R, so the roughly 30% speed-up has some trade-offs}. Details are in an old SAC 2005 paper. Some verification in V2V networks can use this method (P1609.2). With the "bitcoin" curve secp256k1, one can use endomorphisms to achieve similar acceleration as in the SAC2005 paper, via the GLV method (this also results in half-size scalars). Best regards, Rene [excerpt email RS as of March 23, 2016, 9.01am EST] The equation is always correct, had ECDSA been defined with r=x(R), i.e., without the mod n reduction step to compute r. On 6/14/2016 5:49 PM, Brian Smith wrote: </div> <blockquote cite="mid:CAFewVt6hmd-Rcwis0Yb5cO2hWHV2sB3Pb5YqC6Xr4-naLVDNvw@mail.gmail.com" type="cite"> <pre wrap="">Gregory Maxwell <a class="moz-txt-link-rfc2396E" href="mailto:gmaxwell@gmail.com"><gmaxwell@gmail.com></a> wrote: </pre> <blockquote type="cite"> <pre wrap="">Brian Smith <a class="moz-txt-link-rfc2396E" href="mailto:brian@briansmith.org"><brian@briansmith.org></a> wrote: </pre> <blockquote type="cite"> <pre wrap="">[I am not sure if boring topics like ECDSA are appropriate for this list. I hope this is interesting enough.] </pre> </blockquote> <pre wrap=""> It's no less useful for Schnorr (just even more obvious there), and in that case it permits a verification to be implemented completely without any modular inversion. </pre> </blockquote> <pre wrap=""> Yes, that's a good point. I will be implementing it for EdDSA, specifically Ed25519, soon. Since Ed25519 has cofactor > 1, the trick must be generalized to try more than two multiples of `r`. </pre> <blockquote type="cite"> <pre wrap="">As noted by Rene Struik the implementation must check all conditions that result from modular reduction, and as noted by Ruggero SUSELLA, ours does. Libsecp256k1 also includes test vectors that try the conditions/decisions of these branches, so if any were omitted the tests would fail. I would encourage other implementers who adopted this optimization to also include specific tests for it passing and failing each branch-- to avoid a later developer optimizing away an 'impossible' case. Though these cases are 'rare', the triggering conditions can be generated by backwards computing public keys from constructed signatures where R.x is a very high value. </pre> </blockquote> <pre wrap=""> Good point. I already had to help another person fix their implementation. I have attached some test vectors to this message for ECDSA P-256 and P-384 that were based on what you suggested above: Choose an (r, s) where r is in the range we want to test, and then recover the public key from the signature. However, I wasn't able to generate test vectors that test the case where r == n this way, since `n` is not a perfect square. So, if anybody has test vectors for the r == n case, and/or r == n - 1 and r == n + 1, for P-256 and P-384 in particular, I would love to get them. </pre> <blockquote type="cite"> <pre wrap="">For ECDSA the approach is one that loses its utility with larger trace/co-factor; as there end up being many cases to check; so it may not be worthwhile for some curves. </pre> </blockquote> <pre wrap=""> Also, for Ed25519, your suggested method of generating test vectors doesn't work, because public keys can't be recovered from EdDSA signatures. So, I am hoping somebody can share test vectors for Ed25519 that cover all the cases: r < q - 8n, r < q - 7n, ... r < q - n, r == n, n < r < q, or suggest a realistic method for finding some. Thanks for sharing! Cheers, Brian </pre> <fieldset class="mimeAttachmentHeader"></fieldset> <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> <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>