tests: add ECDSA verify case where r + n overflows p #1948

Currently no test checks that ECDSA verify rejects a signature where r + n ≥ p and (r + n) mod p equals x(R), so the following mutant lives:

diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
index 5963877..5301eaa 100644
--- a/src/ecdsa_impl.h
+++ b/src/ecdsa_impl.h
@@ -258,10 +258,6 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_scalar *sigr, const secp25
         /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
         return 1;
     }
-    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
-        /* xr + n >= p, so we can skip testing the second case. */
-        return 0;
-    }
     secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
         /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */

This adds a case with r = p - n + 1, so that (r + n) mod p = 1, and a pubkey chosen so that x(R) = 1, covering this gap.

ACK mod nit

This adds a case with r = p - n + 1, so that (r + n) mod p = 1, and a pubkey chosen so that x(R) = 1, covering this gap.

I think it would be nice to add comments for csr and pubkey that explain how they were chosen.

You may also want to take a look at #1949 if you're interested.

And one more thing: If Such a test case would also be a great addition to the Wycheproof test vector database (which is also used by other projects) if you're willing to contribute there.

See https://github.com/C2SP/wycheproof/blob/main/testvectors_v1/ecdsa_secp256k1_sha256_bitcoin_test.json for the variant of ECDSA that we use (and we run these vectors as part of our tests), but I think a r + n > p case is a generic for ECDSA.

Thanks @real-or-random for the review! Forced push b125005e5f42a18f381d8dca6cc0dc7cddb1953a explaining how pubkey and csr values were chosen.

You may also want to take a look at #1949 if you're interested.

Cool! I'll give it a look.

And one more thing: If Such a test case would also be a great addition to the Wycheproof test vector database (which is also used by other projects) if you're willing to contribute there.

See https://github.com/C2SP/wycheproof/blob/main/testvectors_v1/ecdsa_secp256k1_sha256_bitcoin_test.json for the variant of ECDSA that we use (and we run these vectors as part of our tests), but I think a r + n > p case is a generic for ECDSA.

The more coverage the better :), I'll open a PR there with an r + n > p case.

ACK b125005e5f42a18f381d8dca6cc0dc7cddb1953a

Sorry for the additional nit: Can you also swap the declarations of pubkey and csr. Otherwise the reader has still clue what's going on when encountering the definition of pubkey first. Also, consider adding something like "scalar r as chars" to csr to make clear that this is the value r.

Thanks for the reviews! Forced push fc88acc3e2e2cbba7ee202634eb73d5d21694126 addressing #1948 (comment)

utACK fc88acc3e2e2cbba7ee202634eb73d5d21694126

re-ACK fc88acc3e2e2cbba7ee202634eb73d5d21694126

Thanks!