Apologies for not providing the link to the SAC 2005 paper myself. Your
link is correct.
I do agree that testing corner cases to catch flaws has merit. (I just
did not see how the inverse of the mapping from Zp to Zn comes into play
with EdDSA.)
Best regards, Rene
On 6/14/2016 7:30 PM, Brian Smith wrote:
Rene Struik <rstruik....@gmail.com> wrote:
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 ...
I think the test vectors are still interesting because they would
catch the case where people are wrongly trying to use the trick by
also testing r + in for i > 1. For example, in the case of ECDSA, one
implementation already was already wrongly testing r + n == X (mod q)
even when r > q - n, which was just wrong. You can imagine how such
bugs could happen due to people trying to generalize the logic too
much. In fact, I think such bugs are likely.
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.
I believe you may be referring to
http://cacr.uwaterloo.ca/techreports/2005/cacr2005-28.pdf?
Thanks,
Brian
--
email: rstruik....@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
