diff options
Diffstat (limited to 'crypto/secp256k1/libsecp256k1/src/modules')
11 files changed, 1129 insertions, 0 deletions
diff --git a/crypto/secp256k1/libsecp256k1/src/modules/ecdh/Makefile.am.include b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/Makefile.am.include new file mode 100644 index 000000000..8ef3aff92 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/Makefile.am.include @@ -0,0 +1,9 @@ +include_HEADERS += include/secp256k1_ecdh.h +noinst_HEADERS += src/modules/ecdh/main_impl.h +noinst_HEADERS += src/modules/ecdh/tests_impl.h +if USE_BENCHMARK +noinst_PROGRAMS += bench_ecdh +bench_ecdh_SOURCES = src/bench_ecdh.c +bench_ecdh_LDADD = libsecp256k1.la $(SECP_LIBS) +bench_ecdh_LDFLAGS = -static +endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/ecdh/main_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/main_impl.h new file mode 100644 index 000000000..c23e4f82f --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/main_impl.h @@ -0,0 +1,54 @@ +/********************************************************************** + * Copyright (c) 2015 Andrew Poelstra * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#ifndef _SECP256K1_MODULE_ECDH_MAIN_ +#define _SECP256K1_MODULE_ECDH_MAIN_ + +#include "include/secp256k1_ecdh.h" +#include "ecmult_const_impl.h" + +int secp256k1_ecdh(const secp256k1_context* ctx, unsigned char *result, const secp256k1_pubkey *point, const unsigned char *scalar) { + int ret = 0; + int overflow = 0; + secp256k1_gej res; + secp256k1_ge pt; + secp256k1_scalar s; + ARG_CHECK(result != NULL); + ARG_CHECK(point != NULL); + ARG_CHECK(scalar != NULL); + (void)ctx; + + secp256k1_pubkey_load(ctx, &pt, point); + secp256k1_scalar_set_b32(&s, scalar, &overflow); + if (overflow || secp256k1_scalar_is_zero(&s)) { + ret = 0; + } else { + unsigned char x[32]; + unsigned char y[1]; + secp256k1_sha256_t sha; + + secp256k1_ecmult_const(&res, &pt, &s); + secp256k1_ge_set_gej(&pt, &res); + /* Compute a hash of the point in compressed form + * Note we cannot use secp256k1_eckey_pubkey_serialize here since it does not + * expect its output to be secret and has a timing sidechannel. */ + secp256k1_fe_normalize(&pt.x); + secp256k1_fe_normalize(&pt.y); + secp256k1_fe_get_b32(x, &pt.x); + y[0] = 0x02 | secp256k1_fe_is_odd(&pt.y); + + secp256k1_sha256_initialize(&sha); + secp256k1_sha256_write(&sha, y, sizeof(y)); + secp256k1_sha256_write(&sha, x, sizeof(x)); + secp256k1_sha256_finalize(&sha, result); + ret = 1; + } + + secp256k1_scalar_clear(&s); + return ret; +} + +#endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/ecdh/tests_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/tests_impl.h new file mode 100644 index 000000000..7badc9033 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/ecdh/tests_impl.h @@ -0,0 +1,75 @@ +/********************************************************************** + * Copyright (c) 2015 Andrew Poelstra * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#ifndef _SECP256K1_MODULE_ECDH_TESTS_ +#define _SECP256K1_MODULE_ECDH_TESTS_ + +void test_ecdh_generator_basepoint(void) { + unsigned char s_one[32] = { 0 }; + secp256k1_pubkey point[2]; + int i; + + s_one[31] = 1; + /* Check against pubkey creation when the basepoint is the generator */ + for (i = 0; i < 100; ++i) { + secp256k1_sha256_t sha; + unsigned char s_b32[32]; + unsigned char output_ecdh[32]; + unsigned char output_ser[32]; + unsigned char point_ser[33]; + size_t point_ser_len = sizeof(point_ser); + secp256k1_scalar s; + + random_scalar_order(&s); + secp256k1_scalar_get_b32(s_b32, &s); + + /* compute using ECDH function */ + CHECK(secp256k1_ec_pubkey_create(ctx, &point[0], s_one) == 1); + CHECK(secp256k1_ecdh(ctx, output_ecdh, &point[0], s_b32) == 1); + /* compute "explicitly" */ + CHECK(secp256k1_ec_pubkey_create(ctx, &point[1], s_b32) == 1); + CHECK(secp256k1_ec_pubkey_serialize(ctx, point_ser, &point_ser_len, &point[1], SECP256K1_EC_COMPRESSED) == 1); + CHECK(point_ser_len == sizeof(point_ser)); + secp256k1_sha256_initialize(&sha); + secp256k1_sha256_write(&sha, point_ser, point_ser_len); + secp256k1_sha256_finalize(&sha, output_ser); + /* compare */ + CHECK(memcmp(output_ecdh, output_ser, sizeof(output_ser)) == 0); + } +} + +void test_bad_scalar(void) { + unsigned char s_zero[32] = { 0 }; + unsigned char s_overflow[32] = { + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, + 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, + 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41 + }; + unsigned char s_rand[32] = { 0 }; + unsigned char output[32]; + secp256k1_scalar rand; + secp256k1_pubkey point; + + /* Create random point */ + random_scalar_order(&rand); + secp256k1_scalar_get_b32(s_rand, &rand); + CHECK(secp256k1_ec_pubkey_create(ctx, &point, s_rand) == 1); + + /* Try to multiply it by bad values */ + CHECK(secp256k1_ecdh(ctx, output, &point, s_zero) == 0); + CHECK(secp256k1_ecdh(ctx, output, &point, s_overflow) == 0); + /* ...and a good one */ + s_overflow[31] -= 1; + CHECK(secp256k1_ecdh(ctx, output, &point, s_overflow) == 1); +} + +void run_ecdh_tests(void) { + test_ecdh_generator_basepoint(); + test_bad_scalar(); +} + +#endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/recovery/Makefile.am.include b/crypto/secp256k1/libsecp256k1/src/modules/recovery/Makefile.am.include new file mode 100644 index 000000000..754469eeb --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/recovery/Makefile.am.include @@ -0,0 +1,9 @@ +include_HEADERS += include/secp256k1_recovery.h +noinst_HEADERS += src/modules/recovery/main_impl.h +noinst_HEADERS += src/modules/recovery/tests_impl.h +if USE_BENCHMARK +noinst_PROGRAMS += bench_recover +bench_recover_SOURCES = src/bench_recover.c +bench_recover_LDADD = libsecp256k1.la $(SECP_LIBS) +bench_recover_LDFLAGS = -static +endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/recovery/main_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/recovery/main_impl.h new file mode 100644 index 000000000..75b695894 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/recovery/main_impl.h @@ -0,0 +1,156 @@ +/********************************************************************** + * Copyright (c) 2013-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_RECOVERY_MAIN_ +#define _SECP256K1_MODULE_RECOVERY_MAIN_ + +#include "include/secp256k1_recovery.h" + +static void secp256k1_ecdsa_recoverable_signature_load(const secp256k1_context* ctx, secp256k1_scalar* r, secp256k1_scalar* s, int* recid, const secp256k1_ecdsa_recoverable_signature* sig) { + (void)ctx; + if (sizeof(secp256k1_scalar) == 32) { + /* When the secp256k1_scalar type is exactly 32 byte, use its + * representation inside secp256k1_ecdsa_signature, as conversion is very fast. + * Note that secp256k1_ecdsa_signature_save must use the same representation. */ + memcpy(r, &sig->data[0], 32); + memcpy(s, &sig->data[32], 32); + } else { + secp256k1_scalar_set_b32(r, &sig->data[0], NULL); + secp256k1_scalar_set_b32(s, &sig->data[32], NULL); + } + *recid = sig->data[64]; +} + +static void secp256k1_ecdsa_recoverable_signature_save(secp256k1_ecdsa_recoverable_signature* sig, const secp256k1_scalar* r, const secp256k1_scalar* s, int recid) { + if (sizeof(secp256k1_scalar) == 32) { + memcpy(&sig->data[0], r, 32); + memcpy(&sig->data[32], s, 32); + } else { + secp256k1_scalar_get_b32(&sig->data[0], r); + secp256k1_scalar_get_b32(&sig->data[32], s); + } + sig->data[64] = recid; +} + +int secp256k1_ecdsa_recoverable_signature_parse_compact(const secp256k1_context* ctx, secp256k1_ecdsa_recoverable_signature* sig, const unsigned char *input64, int recid) { + secp256k1_scalar r, s; + int ret = 1; + int overflow = 0; + + (void)ctx; + ARG_CHECK(sig != NULL); + ARG_CHECK(input64 != NULL); + ARG_CHECK(recid >= 0 && recid <= 3); + + secp256k1_scalar_set_b32(&r, &input64[0], &overflow); + ret &= !overflow; + secp256k1_scalar_set_b32(&s, &input64[32], &overflow); + ret &= !overflow; + if (ret) { + secp256k1_ecdsa_recoverable_signature_save(sig, &r, &s, recid); + } else { + memset(sig, 0, sizeof(*sig)); + } + return ret; +} + +int secp256k1_ecdsa_recoverable_signature_serialize_compact(const secp256k1_context* ctx, unsigned char *output64, int *recid, const secp256k1_ecdsa_recoverable_signature* sig) { + secp256k1_scalar r, s; + + (void)ctx; + ARG_CHECK(output64 != NULL); + ARG_CHECK(sig != NULL); + + secp256k1_ecdsa_recoverable_signature_load(ctx, &r, &s, recid, sig); + secp256k1_scalar_get_b32(&output64[0], &r); + secp256k1_scalar_get_b32(&output64[32], &s); + return 1; +} + +int secp256k1_ecdsa_recoverable_signature_convert(const secp256k1_context* ctx, secp256k1_ecdsa_signature* sig, const secp256k1_ecdsa_recoverable_signature* sigin) { + secp256k1_scalar r, s; + int recid; + + (void)ctx; + ARG_CHECK(sig != NULL); + ARG_CHECK(sigin != NULL); + + secp256k1_ecdsa_recoverable_signature_load(ctx, &r, &s, &recid, sigin); + secp256k1_ecdsa_signature_save(sig, &r, &s); + return 1; +} + +int secp256k1_ecdsa_sign_recoverable(const secp256k1_context* ctx, secp256k1_ecdsa_recoverable_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { + secp256k1_scalar r, s; + secp256k1_scalar sec, non, msg; + int recid; + int ret = 0; + int overflow = 0; + VERIFY_CHECK(ctx != NULL); + ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); + ARG_CHECK(msg32 != NULL); + ARG_CHECK(signature != NULL); + ARG_CHECK(seckey != NULL); + if (noncefp == NULL) { + noncefp = secp256k1_nonce_function_default; + } + + secp256k1_scalar_set_b32(&sec, seckey, &overflow); + /* Fail if the secret key is invalid. */ + if (!overflow && !secp256k1_scalar_is_zero(&sec)) { + unsigned int count = 0; + secp256k1_scalar_set_b32(&msg, msg32, NULL); + while (1) { + unsigned char nonce32[32]; + ret = noncefp(nonce32, seckey, msg32, NULL, (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_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid)) { + break; + } + } + count++; + } + secp256k1_scalar_clear(&msg); + secp256k1_scalar_clear(&non); + secp256k1_scalar_clear(&sec); + } + if (ret) { + secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid); + } else { + memset(signature, 0, sizeof(*signature)); + } + return ret; +} + +int secp256k1_ecdsa_recover(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const secp256k1_ecdsa_recoverable_signature *signature, const unsigned char *msg32) { + secp256k1_ge q; + secp256k1_scalar r, s; + secp256k1_scalar m; + int recid; + VERIFY_CHECK(ctx != NULL); + ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx)); + ARG_CHECK(msg32 != NULL); + ARG_CHECK(signature != NULL); + ARG_CHECK(pubkey != NULL); + + secp256k1_ecdsa_recoverable_signature_load(ctx, &r, &s, &recid, signature); + ARG_CHECK(recid >= 0 && recid < 4); + secp256k1_scalar_set_b32(&m, msg32, NULL); + if (secp256k1_ecdsa_sig_recover(&ctx->ecmult_ctx, &r, &s, &q, &m, recid)) { + secp256k1_pubkey_save(pubkey, &q); + return 1; + } else { + memset(pubkey, 0, sizeof(*pubkey)); + return 0; + } +} + +#endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/recovery/tests_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/recovery/tests_impl.h new file mode 100644 index 000000000..5a78fae92 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/recovery/tests_impl.h @@ -0,0 +1,249 @@ +/********************************************************************** + * Copyright (c) 2013-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_RECOVERY_TESTS_ +#define _SECP256K1_MODULE_RECOVERY_TESTS_ + +void test_ecdsa_recovery_end_to_end(void) { + unsigned char extra[32] = {0x00}; + unsigned char privkey[32]; + unsigned char message[32]; + secp256k1_ecdsa_signature signature[5]; + secp256k1_ecdsa_recoverable_signature rsignature[5]; + unsigned char sig[74]; + secp256k1_pubkey pubkey; + secp256k1_pubkey recpubkey; + int recid = 0; + + /* Generate a random key and message. */ + { + secp256k1_scalar msg, key; + random_scalar_order_test(&msg); + random_scalar_order_test(&key); + secp256k1_scalar_get_b32(privkey, &key); + secp256k1_scalar_get_b32(message, &msg); + } + + /* Construct and verify corresponding public key. */ + CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1); + CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1); + + /* Serialize/parse compact and verify/recover. */ + extra[0] = 0; + CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[0], message, privkey, NULL, NULL) == 1); + CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[4], message, privkey, NULL, NULL) == 1); + CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[1], message, privkey, NULL, extra) == 1); + extra[31] = 1; + CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[2], message, privkey, NULL, extra) == 1); + extra[31] = 0; + extra[0] = 1; + CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[3], message, privkey, NULL, extra) == 1); + CHECK(secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, sig, &recid, &rsignature[4]) == 1); + CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 1); + memset(&rsignature[4], 0, sizeof(rsignature[4])); + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1); + CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 1); + /* Parse compact (with recovery id) and recover. */ + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &recpubkey, &rsignature[4], message) == 1); + CHECK(memcmp(&pubkey, &recpubkey, sizeof(pubkey)) == 0); + /* Serialize/destroy/parse signature and verify again. */ + CHECK(secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, sig, &recid, &rsignature[4]) == 1); + sig[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255); + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1); + CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 0); + /* Recover again */ + CHECK(secp256k1_ecdsa_recover(ctx, &recpubkey, &rsignature[4], message) == 0 || + memcmp(&pubkey, &recpubkey, sizeof(pubkey)) != 0); +} + +/* Tests several edge cases. */ +void test_ecdsa_recovery_edge_cases(void) { + const unsigned char msg32[32] = { + 'T', 'h', 'i', 's', ' ', 'i', 's', ' ', + 'a', ' ', 'v', 'e', 'r', 'y', ' ', 's', + 'e', 'c', 'r', 'e', 't', ' ', 'm', 'e', + 's', 's', 'a', 'g', 'e', '.', '.', '.' + }; + const unsigned char sig64[64] = { + /* Generated by signing the above message with nonce 'This is the nonce we will use...' + * and secret key 0 (which is not valid), resulting in recid 0. */ + 0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8, + 0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96, + 0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63, + 0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32, + 0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E, + 0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD, + 0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86, + 0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57 + }; + secp256k1_pubkey pubkey; + /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */ + const unsigned char sigb64[64] = { + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, + }; + secp256k1_pubkey pubkeyb; + secp256k1_ecdsa_recoverable_signature rsig; + secp256k1_ecdsa_signature sig; + int recid; + + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 0)); + CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32)); + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 1)); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32)); + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 2)); + CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32)); + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 3)); + CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32)); + + for (recid = 0; recid < 4; recid++) { + int i; + int recid2; + /* (4,4) encoded in DER. */ + unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04}; + unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01}; + unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00}; + unsigned char sigbderalt1[39] = { + 0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04, + }; + unsigned char sigbderalt2[39] = { + 0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, + }; + unsigned char sigbderalt3[40] = { + 0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04, + }; + unsigned char sigbderalt4[40] = { + 0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, + }; + /* (order + r,4) encoded in DER. */ + unsigned char sigbderlong[40] = { + 0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC, + 0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E, + 0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04 + }; + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigb64, recid) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 1); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1); + for (recid2 = 0; recid2 < 4; recid2++) { + secp256k1_pubkey pubkey2b; + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigb64, recid2) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkey2b, &rsig, msg32) == 1); + /* Verifying with (order + r,4) should always fail. */ + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderlong, sizeof(sigbderlong)) == 0); + } + /* DER parsing tests. */ + /* Zero length r/s. */ + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder_zr, sizeof(sigcder_zr)) == 0); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder_zs, sizeof(sigcder_zs)) == 0); + /* Leading zeros. */ + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt1, sizeof(sigbderalt1)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt2, sizeof(sigbderalt2)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt3, sizeof(sigbderalt3)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt4, sizeof(sigbderalt4)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1); + sigbderalt3[4] = 1; + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt3, sizeof(sigbderalt3)) == 0); + sigbderalt4[7] = 1; + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt4, sizeof(sigbderalt4)) == 0); + /* Damage signature. */ + sigbder[7]++; + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0); + sigbder[7]--; + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, 6) == 0); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder) - 1) == 0); + for(i = 0; i < 8; i++) { + int c; + unsigned char orig = sigbder[i]; + /*Try every single-byte change.*/ + for (c = 0; c < 256; c++) { + if (c == orig ) { + continue; + } + sigbder[i] = c; + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 0 || secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0); + } + sigbder[i] = orig; + } + } + + /* Test r/s equal to zero */ + { + /* (1,1) encoded in DER. */ + unsigned char sigcder[8] = {0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01}; + unsigned char sigc64[64] = { + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, + }; + secp256k1_pubkey pubkeyc; + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyc, &rsig, msg32) == 1); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 1); + sigcder[4] = 0; + sigc64[31] = 0; + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 0); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 0); + sigcder[4] = 1; + sigcder[7] = 0; + sigc64[31] = 1; + sigc64[63] = 0; + CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1); + CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 0); + CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1); + CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 0); + } +} + +void run_recovery_tests(void) { + int i; + for (i = 0; i < 64*count; i++) { + test_ecdsa_recovery_end_to_end(); + } + test_ecdsa_recovery_edge_cases(); +} + +#endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/schnorr/Makefile.am.include b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/Makefile.am.include new file mode 100644 index 000000000..bad4cb7c5 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/Makefile.am.include @@ -0,0 +1,11 @@ +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) +bench_schnorr_verify_LDFLAGS = -static +endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/schnorr/main_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/main_impl.h new file mode 100644 index 000000000..c10fd259f --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/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, int 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/crypto/secp256k1/libsecp256k1/src/modules/schnorr/schnorr.h b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/schnorr.h new file mode 100644 index 000000000..d227433d4 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/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, int n, const unsigned char * const *sig64ins); + +#endif diff --git a/crypto/secp256k1/libsecp256k1/src/modules/schnorr/schnorr_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/schnorr_impl.h new file mode 100644 index 000000000..ed70390bb --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/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, int n, const unsigned char * const *sig64ins) { + secp256k1_scalar s = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + int 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/crypto/secp256k1/libsecp256k1/src/modules/schnorr/tests_impl.h b/crypto/secp256k1/libsecp256k1/src/modules/schnorr/tests_impl.h new file mode 100644 index 000000000..79737f748 --- /dev/null +++ b/crypto/secp256k1/libsecp256k1/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_rand32() % 64] += 1 + (secp256k1_rand32() % 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_rand32() % 64; + int mod = 1 + (secp256k1_rand32() % 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_rand32() % 2) ? (1 + (secp256k1_rand32() % 4)) : 0; + secp256k1_rand256_test(msg); + n = 2 + (secp256k1_rand32() % 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_rand32() % n][secp256k1_rand32() % 32] ^= 1 + (secp256k1_rand32() % 255); + } else if (damage == 2) { + sec[secp256k1_rand32() % n][secp256k1_rand32() % 32] ^= 1 + (secp256k1_rand32() % 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_rand32() % n][secp256k1_rand32() % 64] ^= 1 + (secp256k1_rand32() % 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_rand32() % 32] ^= 1 + (secp256k1_rand32() % 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 |