aboutsummaryrefslogtreecommitdiff
path: root/src/secp256k1/src/modules/schnorr
diff options
context:
space:
mode:
Diffstat (limited to 'src/secp256k1/src/modules/schnorr')
-rw-r--r--src/secp256k1/src/modules/schnorr/Makefile.am.include10
-rw-r--r--src/secp256k1/src/modules/schnorr/main_impl.h164
-rw-r--r--src/secp256k1/src/modules/schnorr/schnorr.h20
-rw-r--r--src/secp256k1/src/modules/schnorr/schnorr_impl.h207
-rw-r--r--src/secp256k1/src/modules/schnorr/tests_impl.h175
5 files changed, 576 insertions, 0 deletions
diff --git a/src/secp256k1/src/modules/schnorr/Makefile.am.include b/src/secp256k1/src/modules/schnorr/Makefile.am.include
new file mode 100644
index 0000000000..b3bfa7d5cc
--- /dev/null
+++ b/src/secp256k1/src/modules/schnorr/Makefile.am.include
@@ -0,0 +1,10 @@
+include_HEADERS += include/secp256k1_schnorr.h
+noinst_HEADERS += src/modules/schnorr/main_impl.h
+noinst_HEADERS += src/modules/schnorr/schnorr.h
+noinst_HEADERS += src/modules/schnorr/schnorr_impl.h
+noinst_HEADERS += src/modules/schnorr/tests_impl.h
+if USE_BENCHMARK
+noinst_PROGRAMS += bench_schnorr_verify
+bench_schnorr_verify_SOURCES = src/bench_schnorr_verify.c
+bench_schnorr_verify_LDADD = libsecp256k1.la $(SECP_LIBS)
+endif
diff --git a/src/secp256k1/src/modules/schnorr/main_impl.h b/src/secp256k1/src/modules/schnorr/main_impl.h
new file mode 100644
index 0000000000..fa176a1767
--- /dev/null
+++ b/src/secp256k1/src/modules/schnorr/main_impl.h
@@ -0,0 +1,164 @@
+/**********************************************************************
+ * Copyright (c) 2014-2015 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef SECP256K1_MODULE_SCHNORR_MAIN
+#define SECP256K1_MODULE_SCHNORR_MAIN
+
+#include "include/secp256k1_schnorr.h"
+#include "modules/schnorr/schnorr_impl.h"
+
+static void secp256k1_schnorr_msghash_sha256(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32) {
+ secp256k1_sha256_t sha;
+ secp256k1_sha256_initialize(&sha);
+ secp256k1_sha256_write(&sha, r32, 32);
+ secp256k1_sha256_write(&sha, msg32, 32);
+ secp256k1_sha256_finalize(&sha, h32);
+}
+
+static const unsigned char secp256k1_schnorr_algo16[17] = "Schnorr+SHA256 ";
+
+int secp256k1_schnorr_sign(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) {
+ secp256k1_scalar sec, non;
+ int ret = 0;
+ int overflow = 0;
+ unsigned int count = 0;
+ VERIFY_CHECK(ctx != NULL);
+ ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
+ ARG_CHECK(msg32 != NULL);
+ ARG_CHECK(sig64 != NULL);
+ ARG_CHECK(seckey != NULL);
+ if (noncefp == NULL) {
+ noncefp = secp256k1_nonce_function_default;
+ }
+
+ secp256k1_scalar_set_b32(&sec, seckey, NULL);
+ while (1) {
+ unsigned char nonce32[32];
+ ret = noncefp(nonce32, msg32, seckey, secp256k1_schnorr_algo16, (void*)noncedata, count);
+ if (!ret) {
+ break;
+ }
+ secp256k1_scalar_set_b32(&non, nonce32, &overflow);
+ memset(nonce32, 0, 32);
+ if (!secp256k1_scalar_is_zero(&non) && !overflow) {
+ if (secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64, &sec, &non, NULL, secp256k1_schnorr_msghash_sha256, msg32)) {
+ break;
+ }
+ }
+ count++;
+ }
+ if (!ret) {
+ memset(sig64, 0, 64);
+ }
+ secp256k1_scalar_clear(&non);
+ secp256k1_scalar_clear(&sec);
+ return ret;
+}
+
+int secp256k1_schnorr_verify(const secp256k1_context* ctx, const unsigned char *sig64, const unsigned char *msg32, const secp256k1_pubkey *pubkey) {
+ secp256k1_ge q;
+ VERIFY_CHECK(ctx != NULL);
+ ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx));
+ ARG_CHECK(msg32 != NULL);
+ ARG_CHECK(sig64 != NULL);
+ ARG_CHECK(pubkey != NULL);
+
+ secp256k1_pubkey_load(ctx, &q, pubkey);
+ return secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64, &q, secp256k1_schnorr_msghash_sha256, msg32);
+}
+
+int secp256k1_schnorr_recover(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const unsigned char *sig64, const unsigned char *msg32) {
+ secp256k1_ge q;
+
+ VERIFY_CHECK(ctx != NULL);
+ ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx));
+ ARG_CHECK(msg32 != NULL);
+ ARG_CHECK(sig64 != NULL);
+ ARG_CHECK(pubkey != NULL);
+
+ if (secp256k1_schnorr_sig_recover(&ctx->ecmult_ctx, sig64, &q, secp256k1_schnorr_msghash_sha256, msg32)) {
+ secp256k1_pubkey_save(pubkey, &q);
+ return 1;
+ } else {
+ memset(pubkey, 0, sizeof(*pubkey));
+ return 0;
+ }
+}
+
+int secp256k1_schnorr_generate_nonce_pair(const secp256k1_context* ctx, secp256k1_pubkey *pubnonce, unsigned char *privnonce32, const unsigned char *sec32, const unsigned char *msg32, secp256k1_nonce_function noncefp, const void* noncedata) {
+ int count = 0;
+ int ret = 1;
+ secp256k1_gej Qj;
+ secp256k1_ge Q;
+ secp256k1_scalar sec;
+
+ VERIFY_CHECK(ctx != NULL);
+ ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
+ ARG_CHECK(msg32 != NULL);
+ ARG_CHECK(sec32 != NULL);
+ ARG_CHECK(pubnonce != NULL);
+ ARG_CHECK(privnonce32 != NULL);
+
+ if (noncefp == NULL) {
+ noncefp = secp256k1_nonce_function_default;
+ }
+
+ do {
+ int overflow;
+ ret = noncefp(privnonce32, sec32, msg32, secp256k1_schnorr_algo16, (void*)noncedata, count++);
+ if (!ret) {
+ break;
+ }
+ secp256k1_scalar_set_b32(&sec, privnonce32, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&sec)) {
+ continue;
+ }
+ secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &sec);
+ secp256k1_ge_set_gej(&Q, &Qj);
+
+ secp256k1_pubkey_save(pubnonce, &Q);
+ break;
+ } while(1);
+
+ secp256k1_scalar_clear(&sec);
+ if (!ret) {
+ memset(pubnonce, 0, sizeof(*pubnonce));
+ }
+ return ret;
+}
+
+int secp256k1_schnorr_partial_sign(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg32, const unsigned char *sec32, const secp256k1_pubkey *pubnonce_others, const unsigned char *secnonce32) {
+ int overflow = 0;
+ secp256k1_scalar sec, non;
+ secp256k1_ge pubnon;
+ VERIFY_CHECK(ctx != NULL);
+ ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
+ ARG_CHECK(msg32 != NULL);
+ ARG_CHECK(sig64 != NULL);
+ ARG_CHECK(sec32 != NULL);
+ ARG_CHECK(secnonce32 != NULL);
+ ARG_CHECK(pubnonce_others != NULL);
+
+ secp256k1_scalar_set_b32(&sec, sec32, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&sec)) {
+ return -1;
+ }
+ secp256k1_scalar_set_b32(&non, secnonce32, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&non)) {
+ return -1;
+ }
+ secp256k1_pubkey_load(ctx, &pubnon, pubnonce_others);
+ return secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64, &sec, &non, &pubnon, secp256k1_schnorr_msghash_sha256, msg32);
+}
+
+int secp256k1_schnorr_partial_combine(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char * const *sig64sin, size_t n) {
+ ARG_CHECK(sig64 != NULL);
+ ARG_CHECK(n >= 1);
+ ARG_CHECK(sig64sin != NULL);
+ return secp256k1_schnorr_sig_combine(sig64, n, sig64sin);
+}
+
+#endif
diff --git a/src/secp256k1/src/modules/schnorr/schnorr.h b/src/secp256k1/src/modules/schnorr/schnorr.h
new file mode 100644
index 0000000000..de18147bd5
--- /dev/null
+++ b/src/secp256k1/src/modules/schnorr/schnorr.h
@@ -0,0 +1,20 @@
+/***********************************************************************
+ * Copyright (c) 2014-2015 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php. *
+ ***********************************************************************/
+
+#ifndef _SECP256K1_MODULE_SCHNORR_H_
+#define _SECP256K1_MODULE_SCHNORR_H_
+
+#include "scalar.h"
+#include "group.h"
+
+typedef void (*secp256k1_schnorr_msghash)(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32);
+
+static int secp256k1_schnorr_sig_sign(const secp256k1_ecmult_gen_context* ctx, unsigned char *sig64, const secp256k1_scalar *key, const secp256k1_scalar *nonce, const secp256k1_ge *pubnonce, secp256k1_schnorr_msghash hash, const unsigned char *msg32);
+static int secp256k1_schnorr_sig_verify(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, const secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32);
+static int secp256k1_schnorr_sig_recover(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32);
+static int secp256k1_schnorr_sig_combine(unsigned char *sig64, size_t n, const unsigned char * const *sig64ins);
+
+#endif
diff --git a/src/secp256k1/src/modules/schnorr/schnorr_impl.h b/src/secp256k1/src/modules/schnorr/schnorr_impl.h
new file mode 100644
index 0000000000..e13ab6db7c
--- /dev/null
+++ b/src/secp256k1/src/modules/schnorr/schnorr_impl.h
@@ -0,0 +1,207 @@
+/***********************************************************************
+ * Copyright (c) 2014-2015 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php. *
+ ***********************************************************************/
+
+#ifndef _SECP256K1_SCHNORR_IMPL_H_
+#define _SECP256K1_SCHNORR_IMPL_H_
+
+#include <string.h>
+
+#include "schnorr.h"
+#include "num.h"
+#include "field.h"
+#include "group.h"
+#include "ecmult.h"
+#include "ecmult_gen.h"
+
+/**
+ * Custom Schnorr-based signature scheme. They support multiparty signing, public key
+ * recovery and batch validation.
+ *
+ * Rationale for verifying R's y coordinate:
+ * In order to support batch validation and public key recovery, the full R point must
+ * be known to verifiers, rather than just its x coordinate. In order to not risk
+ * being more strict in batch validation than normal validation, validators must be
+ * required to reject signatures with incorrect y coordinate. This is only possible
+ * by including a (relatively slow) field inverse, or a field square root. However,
+ * batch validation offers potentially much higher benefits than this cost.
+ *
+ * Rationale for having an implicit y coordinate oddness:
+ * If we commit to having the full R point known to verifiers, there are two mechanism.
+ * Either include its oddness in the signature, or give it an implicit fixed value.
+ * As the R y coordinate can be flipped by a simple negation of the nonce, we choose the
+ * latter, as it comes with nearly zero impact on signing or validation performance, and
+ * saves a byte in the signature.
+ *
+ * Signing:
+ * Inputs: 32-byte message m, 32-byte scalar key x (!=0), 32-byte scalar nonce k (!=0)
+ *
+ * Compute point R = k * G. Reject nonce if R's y coordinate is odd (or negate nonce).
+ * Compute 32-byte r, the serialization of R's x coordinate.
+ * Compute scalar h = Hash(r || m). Reject nonce if h == 0 or h >= order.
+ * Compute scalar s = k - h * x.
+ * The signature is (r, s).
+ *
+ *
+ * Verification:
+ * Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s)
+ *
+ * Signature is invalid if s >= order.
+ * Signature is invalid if r >= p.
+ * Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order.
+ * Option 1 (faster for single verification):
+ * Compute point R = h * Q + s * G. Signature is invalid if R is infinity or R's y coordinate is odd.
+ * Signature is valid if the serialization of R's x coordinate equals r.
+ * Option 2 (allows batch validation and pubkey recovery):
+ * Decompress x coordinate r into point R, with odd y coordinate. Fail if R is not on the curve.
+ * Signature is valid if R + h * Q + s * G == 0.
+ */
+
+static int secp256k1_schnorr_sig_sign(const secp256k1_ecmult_gen_context* ctx, unsigned char *sig64, const secp256k1_scalar *key, const secp256k1_scalar *nonce, const secp256k1_ge *pubnonce, secp256k1_schnorr_msghash hash, const unsigned char *msg32) {
+ secp256k1_gej Rj;
+ secp256k1_ge Ra;
+ unsigned char h32[32];
+ secp256k1_scalar h, s;
+ int overflow;
+ secp256k1_scalar n;
+
+ if (secp256k1_scalar_is_zero(key) || secp256k1_scalar_is_zero(nonce)) {
+ return 0;
+ }
+ n = *nonce;
+
+ secp256k1_ecmult_gen(ctx, &Rj, &n);
+ if (pubnonce != NULL) {
+ secp256k1_gej_add_ge(&Rj, &Rj, pubnonce);
+ }
+ secp256k1_ge_set_gej(&Ra, &Rj);
+ secp256k1_fe_normalize(&Ra.y);
+ if (secp256k1_fe_is_odd(&Ra.y)) {
+ /* R's y coordinate is odd, which is not allowed (see rationale above).
+ Force it to be even by negating the nonce. Note that this even works
+ for multiparty signing, as the R point is known to all participants,
+ which can all decide to flip the sign in unison, resulting in the
+ overall R point to be negated too. */
+ secp256k1_scalar_negate(&n, &n);
+ }
+ secp256k1_fe_normalize(&Ra.x);
+ secp256k1_fe_get_b32(sig64, &Ra.x);
+ hash(h32, sig64, msg32);
+ overflow = 0;
+ secp256k1_scalar_set_b32(&h, h32, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&h)) {
+ secp256k1_scalar_clear(&n);
+ return 0;
+ }
+ secp256k1_scalar_mul(&s, &h, key);
+ secp256k1_scalar_negate(&s, &s);
+ secp256k1_scalar_add(&s, &s, &n);
+ secp256k1_scalar_clear(&n);
+ secp256k1_scalar_get_b32(sig64 + 32, &s);
+ return 1;
+}
+
+static int secp256k1_schnorr_sig_verify(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, const secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32) {
+ secp256k1_gej Qj, Rj;
+ secp256k1_ge Ra;
+ secp256k1_fe Rx;
+ secp256k1_scalar h, s;
+ unsigned char hh[32];
+ int overflow;
+
+ if (secp256k1_ge_is_infinity(pubkey)) {
+ return 0;
+ }
+ hash(hh, sig64, msg32);
+ overflow = 0;
+ secp256k1_scalar_set_b32(&h, hh, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&h)) {
+ return 0;
+ }
+ overflow = 0;
+ secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow);
+ if (overflow) {
+ return 0;
+ }
+ if (!secp256k1_fe_set_b32(&Rx, sig64)) {
+ return 0;
+ }
+ secp256k1_gej_set_ge(&Qj, pubkey);
+ secp256k1_ecmult(ctx, &Rj, &Qj, &h, &s);
+ if (secp256k1_gej_is_infinity(&Rj)) {
+ return 0;
+ }
+ secp256k1_ge_set_gej_var(&Ra, &Rj);
+ secp256k1_fe_normalize_var(&Ra.y);
+ if (secp256k1_fe_is_odd(&Ra.y)) {
+ return 0;
+ }
+ return secp256k1_fe_equal_var(&Rx, &Ra.x);
+}
+
+static int secp256k1_schnorr_sig_recover(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32) {
+ secp256k1_gej Qj, Rj;
+ secp256k1_ge Ra;
+ secp256k1_fe Rx;
+ secp256k1_scalar h, s;
+ unsigned char hh[32];
+ int overflow;
+
+ hash(hh, sig64, msg32);
+ overflow = 0;
+ secp256k1_scalar_set_b32(&h, hh, &overflow);
+ if (overflow || secp256k1_scalar_is_zero(&h)) {
+ return 0;
+ }
+ overflow = 0;
+ secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow);
+ if (overflow) {
+ return 0;
+ }
+ if (!secp256k1_fe_set_b32(&Rx, sig64)) {
+ return 0;
+ }
+ if (!secp256k1_ge_set_xo_var(&Ra, &Rx, 0)) {
+ return 0;
+ }
+ secp256k1_gej_set_ge(&Rj, &Ra);
+ secp256k1_scalar_inverse_var(&h, &h);
+ secp256k1_scalar_negate(&s, &s);
+ secp256k1_scalar_mul(&s, &s, &h);
+ secp256k1_ecmult(ctx, &Qj, &Rj, &h, &s);
+ if (secp256k1_gej_is_infinity(&Qj)) {
+ return 0;
+ }
+ secp256k1_ge_set_gej(pubkey, &Qj);
+ return 1;
+}
+
+static int secp256k1_schnorr_sig_combine(unsigned char *sig64, size_t n, const unsigned char * const *sig64ins) {
+ secp256k1_scalar s = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
+ size_t i;
+ for (i = 0; i < n; i++) {
+ secp256k1_scalar si;
+ int overflow;
+ secp256k1_scalar_set_b32(&si, sig64ins[i] + 32, &overflow);
+ if (overflow) {
+ return -1;
+ }
+ if (i) {
+ if (memcmp(sig64ins[i - 1], sig64ins[i], 32) != 0) {
+ return -1;
+ }
+ }
+ secp256k1_scalar_add(&s, &s, &si);
+ }
+ if (secp256k1_scalar_is_zero(&s)) {
+ return 0;
+ }
+ memcpy(sig64, sig64ins[0], 32);
+ secp256k1_scalar_get_b32(sig64 + 32, &s);
+ secp256k1_scalar_clear(&s);
+ return 1;
+}
+
+#endif
diff --git a/src/secp256k1/src/modules/schnorr/tests_impl.h b/src/secp256k1/src/modules/schnorr/tests_impl.h
new file mode 100644
index 0000000000..5bd14a03e3
--- /dev/null
+++ b/src/secp256k1/src/modules/schnorr/tests_impl.h
@@ -0,0 +1,175 @@
+/**********************************************************************
+ * Copyright (c) 2014-2015 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef SECP256K1_MODULE_SCHNORR_TESTS
+#define SECP256K1_MODULE_SCHNORR_TESTS
+
+#include "include/secp256k1_schnorr.h"
+
+void test_schnorr_end_to_end(void) {
+ unsigned char privkey[32];
+ unsigned char message[32];
+ unsigned char schnorr_signature[64];
+ secp256k1_pubkey pubkey, recpubkey;
+
+ /* Generate a random key and message. */
+ {
+ secp256k1_scalar key;
+ random_scalar_order_test(&key);
+ secp256k1_scalar_get_b32(privkey, &key);
+ secp256k1_rand256_test(message);
+ }
+
+ /* Construct and verify corresponding public key. */
+ CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1);
+ CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1);
+
+ /* Schnorr sign. */
+ CHECK(secp256k1_schnorr_sign(ctx, schnorr_signature, message, privkey, NULL, NULL) == 1);
+ CHECK(secp256k1_schnorr_verify(ctx, schnorr_signature, message, &pubkey) == 1);
+ CHECK(secp256k1_schnorr_recover(ctx, &recpubkey, schnorr_signature, message) == 1);
+ CHECK(memcmp(&pubkey, &recpubkey, sizeof(pubkey)) == 0);
+ /* Destroy signature and verify again. */
+ schnorr_signature[secp256k1_rand_bits(6)] += 1 + secp256k1_rand_int(255);
+ CHECK(secp256k1_schnorr_verify(ctx, schnorr_signature, message, &pubkey) == 0);
+ CHECK(secp256k1_schnorr_recover(ctx, &recpubkey, schnorr_signature, message) != 1 ||
+ memcmp(&pubkey, &recpubkey, sizeof(pubkey)) != 0);
+}
+
+/** Horribly broken hash function. Do not use for anything but tests. */
+void test_schnorr_hash(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32) {
+ int i;
+ for (i = 0; i < 32; i++) {
+ h32[i] = r32[i] ^ msg32[i];
+ }
+}
+
+void test_schnorr_sign_verify(void) {
+ unsigned char msg32[32];
+ unsigned char sig64[3][64];
+ secp256k1_gej pubkeyj[3];
+ secp256k1_ge pubkey[3];
+ secp256k1_scalar nonce[3], key[3];
+ int i = 0;
+ int k;
+
+ secp256k1_rand256_test(msg32);
+
+ for (k = 0; k < 3; k++) {
+ random_scalar_order_test(&key[k]);
+
+ do {
+ random_scalar_order_test(&nonce[k]);
+ if (secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64[k], &key[k], &nonce[k], NULL, &test_schnorr_hash, msg32)) {
+ break;
+ }
+ } while(1);
+
+ secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pubkeyj[k], &key[k]);
+ secp256k1_ge_set_gej_var(&pubkey[k], &pubkeyj[k]);
+ CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64[k], &pubkey[k], &test_schnorr_hash, msg32));
+
+ for (i = 0; i < 4; i++) {
+ int pos = secp256k1_rand_bits(6);
+ int mod = 1 + secp256k1_rand_int(255);
+ sig64[k][pos] ^= mod;
+ CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64[k], &pubkey[k], &test_schnorr_hash, msg32) == 0);
+ sig64[k][pos] ^= mod;
+ }
+ }
+}
+
+void test_schnorr_threshold(void) {
+ unsigned char msg[32];
+ unsigned char sec[5][32];
+ secp256k1_pubkey pub[5];
+ unsigned char nonce[5][32];
+ secp256k1_pubkey pubnonce[5];
+ unsigned char sig[5][64];
+ const unsigned char* sigs[5];
+ unsigned char allsig[64];
+ const secp256k1_pubkey* pubs[5];
+ secp256k1_pubkey allpub;
+ int n, i;
+ int damage;
+ int ret = 0;
+
+ damage = secp256k1_rand_bits(1) ? (1 + secp256k1_rand_int(4)) : 0;
+ secp256k1_rand256_test(msg);
+ n = 2 + secp256k1_rand_int(4);
+ for (i = 0; i < n; i++) {
+ do {
+ secp256k1_rand256_test(sec[i]);
+ } while (!secp256k1_ec_seckey_verify(ctx, sec[i]));
+ CHECK(secp256k1_ec_pubkey_create(ctx, &pub[i], sec[i]));
+ CHECK(secp256k1_schnorr_generate_nonce_pair(ctx, &pubnonce[i], nonce[i], msg, sec[i], NULL, NULL));
+ pubs[i] = &pub[i];
+ }
+ if (damage == 1) {
+ nonce[secp256k1_rand_int(n)][secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255);
+ } else if (damage == 2) {
+ sec[secp256k1_rand_int(n)][secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255);
+ }
+ for (i = 0; i < n; i++) {
+ secp256k1_pubkey allpubnonce;
+ const secp256k1_pubkey *pubnonces[4];
+ int j;
+ for (j = 0; j < i; j++) {
+ pubnonces[j] = &pubnonce[j];
+ }
+ for (j = i + 1; j < n; j++) {
+ pubnonces[j - 1] = &pubnonce[j];
+ }
+ CHECK(secp256k1_ec_pubkey_combine(ctx, &allpubnonce, pubnonces, n - 1));
+ ret |= (secp256k1_schnorr_partial_sign(ctx, sig[i], msg, sec[i], &allpubnonce, nonce[i]) != 1) * 1;
+ sigs[i] = sig[i];
+ }
+ if (damage == 3) {
+ sig[secp256k1_rand_int(n)][secp256k1_rand_bits(6)] ^= 1 + secp256k1_rand_int(255);
+ }
+ ret |= (secp256k1_ec_pubkey_combine(ctx, &allpub, pubs, n) != 1) * 2;
+ if ((ret & 1) == 0) {
+ ret |= (secp256k1_schnorr_partial_combine(ctx, allsig, sigs, n) != 1) * 4;
+ }
+ if (damage == 4) {
+ allsig[secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255);
+ }
+ if ((ret & 7) == 0) {
+ ret |= (secp256k1_schnorr_verify(ctx, allsig, msg, &allpub) != 1) * 8;
+ }
+ CHECK((ret == 0) == (damage == 0));
+}
+
+void test_schnorr_recovery(void) {
+ unsigned char msg32[32];
+ unsigned char sig64[64];
+ secp256k1_ge Q;
+
+ secp256k1_rand256_test(msg32);
+ secp256k1_rand256_test(sig64);
+ secp256k1_rand256_test(sig64 + 32);
+ if (secp256k1_schnorr_sig_recover(&ctx->ecmult_ctx, sig64, &Q, &test_schnorr_hash, msg32) == 1) {
+ CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64, &Q, &test_schnorr_hash, msg32) == 1);
+ }
+}
+
+void run_schnorr_tests(void) {
+ int i;
+ for (i = 0; i < 32*count; i++) {
+ test_schnorr_end_to_end();
+ }
+ for (i = 0; i < 32 * count; i++) {
+ test_schnorr_sign_verify();
+ }
+ for (i = 0; i < 16 * count; i++) {
+ test_schnorr_recovery();
+ }
+ for (i = 0; i < 10 * count; i++) {
+ test_schnorr_threshold();
+ }
+}
+
+#endif