[curves] libsecp256k1's novel(?) ECDSA verification optimization

[Brian Smith]

Gregory Maxwell <gmaxwell at gmail.com> wrote:
> Brian Smith <brian at briansmith.org> wrote:
>> [I am not sure if boring topics like ECDSA are appropriate for this list. I
>> hope this is interesting enough.]
>
> 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.

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`.

> 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.

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.

> 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.

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
-- 
https://briansmith.org/
-------------- next part --------------
# Test vectors for Gregory Maxwell's trick.

# The signature has r < q - n. This is the control case for the next
# test case; this signature is the same but the public key is
# different. Notice that both public keys work for the same signature!
# This test case will pass even if the implementation doesn't reduce
# the X coordinate of the multiplication result (mod n). s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-256
Digest = SHA256
Msg = ""
Q = 041548fc88953e06cd34d4b300804c5322cb48c24aaaa4d07a541b0f0ccfeedeb0ae4991b90519ea405588bdf699f5e6d0c6b2d5217a5c16e8371062737aa1dae1
Sig = 3006020106020104
Result = P (0 )

# The signature has r < q - n. s Since r < q - n, r + n < q. Notice
# that this signature is the same as the signature in the preceding
# test case, but the public key is different. That the signature
# passes for this case too is what's special about the case where
# r < q - n. If this test case fails, it is likely that the doesn't
# reduce the X coordinate of the multiplication result (mod n) or it
# is missing the second step of Gregory Maxwell's trick. s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-256
Digest = SHA256
Msg = ""
Q = 04ad8f60e4ec1ebdb6a260b559cb55b1e9d2c5ddd43a41a2d11b0741ef2567d84e166737664104ebbc337af3d861d3524cfbc761c12edae974a0759750c8324f9a
Sig = 3006020106020104
Result = P (0 )

# The signature has r > q - n. The signature is for the public key
# recovered from r. Since r > q - n, r + n > q. This is the control
# for the next test case; this signature is the same as the signature
# in the following test case but the public key is different. s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-256
Digest = SHA256
Msg = ""
Q = 0445bd879143a64af5746e2e82aa65fd2ea07bba4e35594095a981b59984dacb219d59697387ac721b1f1eccf4b11f43ddc39e8367147abab3084142ed3ea170e4
Sig = 301502104319055358e8617b0c46353d039cdaae020104
Result = P (0 )

# The signature has r > q - n. The signature is for the public key
# recovered from r + n (mod q). Since r > q - n, r + n > q and so
# r + n (mod q) < r because r + n (mod n) != r + n (mod q). Notice
# that this signature is the same as the signature in the preceding
# test case but the public key is different. Also, notice that the
# signature verification **fails** in this case, unlike the
# other related test cases. If this test case fails, it is likely that
# the implementation didn't guard the second case of Gregory Maxwell's
# trick on the condition r < q - n. s was selected arbitrarily as 4
# and then r was chosen to be the smallest value where the public key
# recovery from the signature worked.
Curve = P-256
Digest = SHA256
Msg = ""
Q = 040feb5df4cc78b35ec9c180cc0de5842f75f088b48456978ffa98e716d94883e1e6500b2a1f6c1d9d493428d7ae7d9a8a560fff30a3d14aa160be0c5e7edcd887
Sig = 301502104319055358e8617b0c46353d039cdaae020104
Result = F

# The signature has r < q - n. This is the control case for the next
# test case; this signature is the same but the public key is
# different. Notice that both public keys work for the same signature!
# This test case will pass even if the implementation doesn't reduce
# the X coordinate of the multiplication result (mod n). s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-384
Digest = SHA256
Msg = ""
Q = 0425e299eea9927b39fa92417705391bf17e8110b4615e9eb5da471b57be0c30e7d89dbdc3e5da4eae029b300344d3851548b59ed8be668813905105e673319d59d32f574e180568463c6186864888f6c0b67b304441f82aab031279e48f047c31
Sig = 3006020103020104
Result = P (0 )

# The signature has r < q - n. s Since r < q - n, r + n < q. Notice
# that this signature is the same as the signature in the preceding
# test case, but the public key is different. That the signature
# passes for this case too is what's special about the case where
# r < q - n. If this test case fails, it is likely that the doesn't
# reduce the X coordinate of the multiplication result (mod n) or it
# is missing the second step of Gregory Maxwell's trick. s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-384
Digest = SHA256
Msg = ""
Q = 04a328f65c22307188b4af65779c1d2ec821c6748c6bd8dc0e6a008135f048f832df501f7f3f79966b03d5bef2f187ec34d85f6a934af465656fb4eea8dd9176ab80fbb4a27a649f526a7dfe616091b78d293552bc093dfde9b31cae69d51d3afb
Sig = 3006020103020104
Result = P (0 )

# The signature has r > q - n. The signature is for the public key
# recovered from r. Since r > q - n, r + n > q. This is the control
# for the next test case; this signature is the same as the signature
# in the following test case but the public key is different. s was
# selected arbitrarily as 4 and then r was chosen to be the smallest
# value where the public key recovery from the signature worked.
Curve = P-384
Digest = SHA256
Msg = ""
Q = 04242e8585eaa7a28cc6062cab4c9c5fd536f46b17be1728288a2cda5951df4941aed1d712defda023d10aca1c5ee01443e8beacd821f7efa27847418ab95ce2c514b2b6b395ee73417c83dbcad631421f360d84d64658c98a62d685b220f5aad4
Sig = 301d0218389cb27e0bc8d21fa7e5f24cb74f58851313e696333ad68e020104
Result = P (0 )

# The signature has r > q - n. The signature is for the public key
# recovered from r + n (mod q). Since r > q - n, r + n > q and so
# r + n (mod q) < r because r + n (mod n) != r + n (mod q). Notice
# that this signature is the same as the signature in the preceding
# test case but the public key is different. Also, notice that the
# signature verification **fails** in this case, unlike the
# other related test cases. If this test case fails, it is likely that
# the implementation didn't guard the second case of Gregory Maxwell's
# trick on the condition r < q - n. s was selected arbitrarily as 4
# and then r was chosen to be the smallest value where the public key
# recovery from the signature worked.
Curve = P-384
Digest = SHA256
Msg = ""
Q = 04cdf865dd743fe1c23757ec5e65fd5e4038b472ded2af261e3d8343c595c8b69147df46379c7ca40e60e80170d34a1188dbb2b6f7d3934c23d2f78cfb0db3f3219959fad63c9b612ef2f20d679777b84192ce86e781c14b1bbb77eacd6e0520e2
Sig = 301d0218389cb27e0bc8d21fa7e5f24cb74f58851313e696333ad68e020104
Result = F