From c0da4f60e2145a9838c0c5d0a02592faf16d2d8d Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 4 Sep 2023 12:51:20 -0400 Subject: Squashed 'src/secp256k1/' changes from c545fdc374..199d27cea3 199d27cea3 Merge bitcoin-core/secp256k1#1415: release: Prepare for 0.4.0 16339804c9 release: Prepare for 0.4.0 d9a85065a9 changelog: Catch up in preparation of release 0b4640aedd Merge bitcoin-core/secp256k1#1413: ci: Add `release` job 8659a01714 ci: Add `release` job f9b38894ba ci: Update `actions/checkout` version 727bec5bc2 Merge bitcoin-core/secp256k1#1414: ci/gha: Add ARM64 QEMU jobs for clang and clang-snapshot 2635068abf ci/gha: Let MSan continue checking after errors in all jobs e78c7b68eb ci/Dockerfile: Reduce size of Docker image further 2f0d3bbffb ci/Dockerfile: Warn if `ulimit -n` is too high when running Docker 4b8a647ad3 ci/gha: Add ARM64 QEMU jobs for clang and clang-snapshot 6ebe7d2bb3 ci/Dockerfile: Always use versioned clang packages 65c79fe2d0 Merge bitcoin-core/secp256k1#1412: ci: Switch macOS from Ventura to Monterey and add Valgrind c223d7e33d ci: Switch macOS from Ventura to Monterey and add Valgrind ea26b71c3a Merge bitcoin-core/secp256k1#1411: ci: Make repetitive command the default one cce0456304 ci: Make repetitive command the default one 317a4c48f0 ci: Move `git config ...` to `run-in-docker-action` 4d7fe60905 Merge bitcoin-core/secp256k1#1409: ci: Move remained task from Cirrus to GitHub Actions 676ed8f9cf ci: Move "C++ (public headers)" from Cirrus to GitHub Actions 61fc3a2dc8 ci: Move "C++ -fpermissive..." from Cirrus to GitHub Actions d51fb0a533 ci: Move "MSan" from Cirrus to GitHub Actions c22ac27529 ci: Move sanitizers task from Cirrus to GitHub Actions 26a989924b Merge bitcoin-core/secp256k1#1410: ci: Use concurrency for pull requests only ee1be62d84 ci: Use concurrency for pull requests only 6ee14550c8 Merge bitcoin-core/secp256k1#1406: ci, gha: Move more non-x86_64 tasks from Cirrus CI to GitHub Actions fc3dea29ea ci: Move "ppc64le: Linux..." from Cirrus to GitHub Actions 7782dc8276 ci: Move "ARM64: Linux..." from Cirrus to GitHub Actions 0a16de671c ci: Move "ARM32: Linux..." from Cirrus to GitHub Actions ea33914e00 ci: Move "s390x (big-endian): Linux..." from Cirrus to GitHub Actions 880be8af99 ci: Move "i686: Linux (Debian stable)" from Cirrus to GiHub Actions 2e6cf9bae5 Merge bitcoin-core/secp256k1#1396: ci, gha: Add "x86_64: Linux (Debian stable)" GitHub Actions job 5373693e45 Merge bitcoin-core/secp256k1#1405: ci: Drop no longer needed workaround ef9fe959de ci: Drop no longer needed workaround e10878f58e ci, gha: Drop `driver-opts.network` input for `setup-buildx-action` 4ad4914bd1 ci, gha: Add `retry_builder` Docker image builder 6617a620d9 ci: Remove "x86_64: Linux (Debian stable)" task from Cirrus CI 03c9e6508c ci, gha: Add "x86_64: Linux (Debian stable)" GitHub Actions job ad3e65d9fe ci: Remove GCC build files and sage to reduce size of Docker image 6b9507adf6 Merge bitcoin-core/secp256k1#1398: ci, gha: Add Windows jobs based on Linux image 87d35f30c0 ci: Rename `cirrus.sh` to more general `ci.sh` d6281dd008 ci: Remove Windows tasks from Cirrus CI 2b6f9cd546 ci, gha: Add Windows jobs based on Linux image 48b1d939b5 Merge bitcoin-core/secp256k1#1403: ci, gha: Ensure only a single workflow processes `github.ref` at a time 0ba2b94551 Merge bitcoin-core/secp256k1#1373: Add invariant checking for scalars 060e32cb60 Merge bitcoin-core/secp256k1#1401: ci, gha: Run all MSVC tests on Windows natively de657c2044 Merge bitcoin-core/secp256k1#1062: Removes `_fe_equal_var`, and unwanted `_fe_normalize_weak` calls (in tests) bcffeb14bc Merge bitcoin-core/secp256k1#1404: ci: Remove "arm64: macOS Ventura" task from Cirrus CI c2f6435802 ci: Add comment about switching macOS to M1 on GHA later 4a24fae0bc ci: Remove "arm64: macOS Ventura" task from Cirrus CI b0886fd35c ci, gha: Ensure only a single workflow processes `github.ref` at a time 3d05c86d63 Merge bitcoin-core/secp256k1#1394: ci, gha: Run "x86_64: macOS Ventura" job on GitHub Actions d78bec7001 ci: Remove Windows MSVC tasks from Cirrus CI 3545dc2b9b ci, gha: Run all MSVC tests on Windows natively 5d8fa825e2 Merge bitcoin-core/secp256k1#1274: test: Silent noisy clang warnings about Valgrind code on macOS x86_64 8e54a346d2 ci, gha: Run "x86_64: macOS Ventura" job on GitHub Actions b327abfcea Merge bitcoin-core/secp256k1#1402: ci: Use Homebrew's gcc in native macOS task d62db57427 ci: Use Homebrew's gcc in native macOS task 54058d16fe field: remove `secp256k1_fe_equal_var` bb4efd6404 tests: remove unwanted `secp256k1_fe_normalize_weak` call eedd781085 Merge bitcoin-core/secp256k1#1348: tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) b2f6712dd3 Merge bitcoin-core/secp256k1#1400: ctimetests: Use new SECP256K1_CHECKMEM macros also for ellswift 9c91ea41b1 ci: Enable ellswift module where it's missing db32a24761 ctimetests: Use new SECP256K1_CHECKMEM macros also for ellswift ce765a5b8e Merge bitcoin-core/secp256k1#1399: ci, gha: Run "SageMath prover" job on GitHub Actions 8408dfdc4c Revert "ci: Run sage prover on CI" c8d9914fb1 ci, gha: Run "SageMath prover" job on GitHub Actions 8d2960c8e2 Merge bitcoin-core/secp256k1#1397: ci: Remove "Windows (VS 2022)" task from Cirrus CI f1774e5ec4 ci, gha: Make MSVC job presentation more explicit 5ee039bb58 ci: Remove "Windows (VS 2022)" task from Cirrus CI 96294c00fb Merge bitcoin-core/secp256k1#1389: ci: Run "Windows (VS 2022)" job on GitHub Actions a2f7ccdecc ci: Run "Windows (VS 2022)" job on GitHub Actions 374e2b54e2 Merge bitcoin-core/secp256k1#1290: cmake: Set `ENVIRONMENT` property for examples on Windows 1b13415df9 Merge bitcoin-core/secp256k1#1391: refactor: take use of `secp256k1_scalar_{zero,one}` constants (part 2) a1bd4971d6 refactor: take use of `secp256k1_scalar_{zero,one}` constants (part 2) b7c685e74a Save _normalize_weak calls in group add methods c83afa66e0 Tighten group magnitude limits 26392da2fb Merge bitcoin-core/secp256k1#1386: ci: print $ELLSWIFT in cirrus.sh d23da6d557 use secp256k1_scalar_verify checks 4692478853 ci: print $ELLSWIFT in cirrus.sh c7d0454932 add verification for scalars c734c64278 Merge bitcoin-core/secp256k1#1384: build: enable ellswift module via SECP_CONFIG_DEFINES ad152151b0 update max scalar in scalar_cmov_test and fix schnorrsig_verify exhaustive test 78ca880788 build: enable ellswift module via SECP_CONFIG_DEFINES 0e00fc7d10 Merge bitcoin-core/secp256k1#1383: util: remove unused checked_realloc b097a466c1 util: remove unused checked_realloc 2bd5f3e618 Merge bitcoin-core/secp256k1#1382: refactor: Drop unused cast 4f8c5bd761 refactor: Drop unused cast 173e8d061a Implement current magnitude assumptions 49afd2f5d8 Take use of _fe_verify_magnitude in field_impl.h 4e9661fc42 Add _fe_verify_magnitude (no-op unless VERIFY is enabled) 690b0fc05a add missing group element invariant checks 175db31149 ci: Drop no longer needed `PATH` variable update on Windows 116d2ab3df cmake: Set `ENVIRONMENT` property for examples on Windows cef373997c cmake, refactor: Use helper function instead of interface library 747ada3587 test: Silent noisy clang warnings about Valgrind code on macOS x86_64 git-subtree-dir: src/secp256k1 git-subtree-split: 199d27cea32203b224b208627533c2e813cd3b21 --- src/bench_ecmult.c | 3 +- src/checkmem.h | 7 ++ src/ctime_tests.c | 20 +-- src/field.h | 9 +- src/field_impl.h | 42 +++---- src/group.h | 8 ++ src/group_impl.h | 165 +++++++++++++++++-------- src/hash_impl.h | 2 +- src/modules/extrakeys/tests_exhaustive_impl.h | 2 +- src/modules/schnorrsig/main_impl.h | 2 +- src/modules/schnorrsig/tests_exhaustive_impl.h | 10 +- src/scalar.h | 3 + src/scalar_4x64_impl.h | 79 ++++++++++-- src/scalar_8x32_impl.h | 80 ++++++++++-- src/scalar_impl.h | 19 +++ src/scalar_low_impl.h | 70 ++++++++++- src/tests.c | 157 ++++++++++++----------- src/tests_exhaustive.c | 20 +-- src/util.h | 8 -- 19 files changed, 501 insertions(+), 205 deletions(-) (limited to 'src') diff --git a/src/bench_ecmult.c b/src/bench_ecmult.c index 8818aa81b5..7dc52ad87b 100644 --- a/src/bench_ecmult.c +++ b/src/bench_ecmult.c @@ -244,7 +244,6 @@ static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) { static void run_ecmult_multi_bench(bench_data* data, size_t count, int includes_g, int num_iters) { char str[32]; - static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); size_t iters = 1 + num_iters / count; size_t iter; @@ -262,7 +261,7 @@ static void run_ecmult_multi_bench(bench_data* data, size_t count, int includes_ secp256k1_scalar_add(&total, &total, &tmp); } secp256k1_scalar_negate(&total, &total); - secp256k1_ecmult(&data->expected_output[iter], NULL, &zero, &total); + secp256k1_ecmult(&data->expected_output[iter], NULL, &secp256k1_scalar_zero, &total); } /* Run the benchmark. */ diff --git a/src/checkmem.h b/src/checkmem.h index 571e4cc389..f2169decfc 100644 --- a/src/checkmem.h +++ b/src/checkmem.h @@ -58,7 +58,14 @@ #if !defined SECP256K1_CHECKMEM_ENABLED # if defined VALGRIND # include +# if defined(__clang__) && defined(__APPLE__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wreserved-identifier" +# endif # include +# if defined(__clang__) && defined(__APPLE__) +# pragma clang diagnostic pop +# endif # define SECP256K1_CHECKMEM_ENABLED 1 # define SECP256K1_CHECKMEM_UNDEFINE(p, len) VALGRIND_MAKE_MEM_UNDEFINED((p), (len)) # define SECP256K1_CHECKMEM_DEFINE(p, len) VALGRIND_MAKE_MEM_DEFINED((p), (len)) diff --git a/src/ctime_tests.c b/src/ctime_tests.c index af7891a91c..a384e83152 100644 --- a/src/ctime_tests.c +++ b/src/ctime_tests.c @@ -181,27 +181,27 @@ static void run_tests(secp256k1_context *ctx, unsigned char *key) { #endif #ifdef ENABLE_MODULE_ELLSWIFT - VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + SECP256K1_CHECKMEM_UNDEFINE(key, 32); ret = secp256k1_ellswift_create(ctx, ellswift, key, NULL); - VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret)); CHECK(ret == 1); - VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + SECP256K1_CHECKMEM_UNDEFINE(key, 32); ret = secp256k1_ellswift_create(ctx, ellswift, key, ellswift); - VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret)); CHECK(ret == 1); for (i = 0; i < 2; i++) { - VALGRIND_MAKE_MEM_UNDEFINED(key, 32); - VALGRIND_MAKE_MEM_DEFINED(&ellswift, sizeof(ellswift)); + SECP256K1_CHECKMEM_UNDEFINE(key, 32); + SECP256K1_CHECKMEM_DEFINE(&ellswift, sizeof(ellswift)); ret = secp256k1_ellswift_xdh(ctx, msg, ellswift, ellswift, key, i, secp256k1_ellswift_xdh_hash_function_bip324, NULL); - VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret)); CHECK(ret == 1); - VALGRIND_MAKE_MEM_UNDEFINED(key, 32); - VALGRIND_MAKE_MEM_DEFINED(&ellswift, sizeof(ellswift)); + SECP256K1_CHECKMEM_UNDEFINE(key, 32); + SECP256K1_CHECKMEM_DEFINE(&ellswift, sizeof(ellswift)); ret = secp256k1_ellswift_xdh(ctx, msg, ellswift, ellswift, key, i, secp256k1_ellswift_xdh_hash_function_prefix, (void *)prefix); - VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret)); CHECK(ret == 1); } diff --git a/src/field.h b/src/field.h index bb99f948ef..ccd228e1ae 100644 --- a/src/field.h +++ b/src/field.h @@ -176,12 +176,6 @@ static int secp256k1_fe_is_odd(const secp256k1_fe *a); */ static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b); -/** Determine whether two field elements are equal, without constant-time guarantee. - * - * Identical in behavior to secp256k1_fe_equal, but not constant time in either a or b. - */ -static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b); - /** Compare the values represented by 2 field elements, without constant-time guarantee. * * On input, a and b must be valid normalized field elements. @@ -352,4 +346,7 @@ static int secp256k1_fe_is_square_var(const secp256k1_fe *a); /** Check invariants on a field element (no-op unless VERIFY is enabled). */ static void secp256k1_fe_verify(const secp256k1_fe *a); +/** Check that magnitude of a is at most m (no-op unless VERIFY is enabled). */ +static void secp256k1_fe_verify_magnitude(const secp256k1_fe *a, int m); + #endif /* SECP256K1_FIELD_H */ diff --git a/src/field_impl.h b/src/field_impl.h index 7f18ebdc94..80d34b9ef2 100644 --- a/src/field_impl.h +++ b/src/field_impl.h @@ -23,27 +23,14 @@ SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe *a, const secp #ifdef VERIFY secp256k1_fe_verify(a); secp256k1_fe_verify(b); - VERIFY_CHECK(a->magnitude <= 1); - VERIFY_CHECK(b->magnitude <= 31); + secp256k1_fe_verify_magnitude(a, 1); + secp256k1_fe_verify_magnitude(b, 31); #endif secp256k1_fe_negate(&na, a, 1); secp256k1_fe_add(&na, b); return secp256k1_fe_normalizes_to_zero(&na); } -SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b) { - secp256k1_fe na; -#ifdef VERIFY - secp256k1_fe_verify(a); - secp256k1_fe_verify(b); - VERIFY_CHECK(a->magnitude <= 1); - VERIFY_CHECK(b->magnitude <= 31); -#endif - secp256k1_fe_negate(&na, a, 1); - secp256k1_fe_add(&na, b); - return secp256k1_fe_normalizes_to_zero_var(&na); -} - static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k1_fe * SECP256K1_RESTRICT a) { /** Given that p is congruent to 3 mod 4, we can compute the square root of * a mod p as the (p+1)/4'th power of a. @@ -60,7 +47,7 @@ static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k #ifdef VERIFY VERIFY_CHECK(r != a); secp256k1_fe_verify(a); - VERIFY_CHECK(a->magnitude <= 8); + secp256k1_fe_verify_magnitude(a, 8); #endif /** The binary representation of (p + 1)/4 has 3 blocks of 1s, with lengths in @@ -151,7 +138,7 @@ static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k if (!ret) { secp256k1_fe_negate(&t1, &t1, 1); secp256k1_fe_normalize_var(&t1); - VERIFY_CHECK(secp256k1_fe_equal_var(&t1, a)); + VERIFY_CHECK(secp256k1_fe_equal(&t1, a)); } #endif return ret; @@ -159,19 +146,26 @@ static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k #ifndef VERIFY static void secp256k1_fe_verify(const secp256k1_fe *a) { (void)a; } +static void secp256k1_fe_verify_magnitude(const secp256k1_fe *a, int m) { (void)a; (void)m; } #else static void secp256k1_fe_impl_verify(const secp256k1_fe *a); static void secp256k1_fe_verify(const secp256k1_fe *a) { /* Magnitude between 0 and 32. */ - VERIFY_CHECK((a->magnitude >= 0) && (a->magnitude <= 32)); + secp256k1_fe_verify_magnitude(a, 32); /* Normalized is 0 or 1. */ VERIFY_CHECK((a->normalized == 0) || (a->normalized == 1)); /* If normalized, magnitude must be 0 or 1. */ - if (a->normalized) VERIFY_CHECK(a->magnitude <= 1); + if (a->normalized) secp256k1_fe_verify_magnitude(a, 1); /* Invoke implementation-specific checks. */ secp256k1_fe_impl_verify(a); } +static void secp256k1_fe_verify_magnitude(const secp256k1_fe *a, int m) { + VERIFY_CHECK(m >= 0); + VERIFY_CHECK(m <= 32); + VERIFY_CHECK(a->magnitude <= m); +} + static void secp256k1_fe_impl_normalize(secp256k1_fe *r); SECP256K1_INLINE static void secp256k1_fe_normalize(secp256k1_fe *r) { secp256k1_fe_verify(r); @@ -293,7 +287,7 @@ static void secp256k1_fe_impl_negate_unchecked(secp256k1_fe *r, const secp256k1_ SECP256K1_INLINE static void secp256k1_fe_negate_unchecked(secp256k1_fe *r, const secp256k1_fe *a, int m) { secp256k1_fe_verify(a); VERIFY_CHECK(m >= 0 && m <= 31); - VERIFY_CHECK(a->magnitude <= m); + secp256k1_fe_verify_magnitude(a, m); secp256k1_fe_impl_negate_unchecked(r, a, m); r->magnitude = m + 1; r->normalized = 0; @@ -326,8 +320,8 @@ static void secp256k1_fe_impl_mul(secp256k1_fe *r, const secp256k1_fe *a, const SECP256K1_INLINE static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b) { secp256k1_fe_verify(a); secp256k1_fe_verify(b); - VERIFY_CHECK(a->magnitude <= 8); - VERIFY_CHECK(b->magnitude <= 8); + secp256k1_fe_verify_magnitude(a, 8); + secp256k1_fe_verify_magnitude(b, 8); VERIFY_CHECK(r != b); VERIFY_CHECK(a != b); secp256k1_fe_impl_mul(r, a, b); @@ -339,7 +333,7 @@ SECP256K1_INLINE static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_f static void secp256k1_fe_impl_sqr(secp256k1_fe *r, const secp256k1_fe *a); SECP256K1_INLINE static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) { secp256k1_fe_verify(a); - VERIFY_CHECK(a->magnitude <= 8); + secp256k1_fe_verify_magnitude(a, 8); secp256k1_fe_impl_sqr(r, a); r->magnitude = 1; r->normalized = 0; @@ -418,7 +412,7 @@ SECP256K1_INLINE static void secp256k1_fe_get_bounds(secp256k1_fe* r, int m) { static void secp256k1_fe_impl_half(secp256k1_fe *r); SECP256K1_INLINE static void secp256k1_fe_half(secp256k1_fe *r) { secp256k1_fe_verify(r); - VERIFY_CHECK(r->magnitude < 32); + secp256k1_fe_verify_magnitude(r, 31); secp256k1_fe_impl_half(r); r->magnitude = (r->magnitude >> 1) + 1; r->normalized = 0; diff --git a/src/group.h b/src/group.h index 1cc6137161..86eb9e1f82 100644 --- a/src/group.h +++ b/src/group.h @@ -44,6 +44,14 @@ typedef struct { #define SECP256K1_GE_STORAGE_CONST_GET(t) SECP256K1_FE_STORAGE_CONST_GET(t.x), SECP256K1_FE_STORAGE_CONST_GET(t.y) +/** Maximum allowed magnitudes for group element coordinates + * in affine (x, y) and jacobian (x, y, z) representation. */ +#define SECP256K1_GE_X_MAGNITUDE_MAX 4 +#define SECP256K1_GE_Y_MAGNITUDE_MAX 3 +#define SECP256K1_GEJ_X_MAGNITUDE_MAX 4 +#define SECP256K1_GEJ_Y_MAGNITUDE_MAX 4 +#define SECP256K1_GEJ_Z_MAGNITUDE_MAX 1 + /** Set a group element equal to the point with given X and Y coordinates */ static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y); diff --git a/src/group_impl.h b/src/group_impl.h index ffdfeaa10a..b9542ce8ae 100644 --- a/src/group_impl.h +++ b/src/group_impl.h @@ -77,6 +77,8 @@ static void secp256k1_ge_verify(const secp256k1_ge *a) { #ifdef VERIFY secp256k1_fe_verify(&a->x); secp256k1_fe_verify(&a->y); + secp256k1_fe_verify_magnitude(&a->x, SECP256K1_GE_X_MAGNITUDE_MAX); + secp256k1_fe_verify_magnitude(&a->y, SECP256K1_GE_Y_MAGNITUDE_MAX); VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); #endif (void)a; @@ -87,6 +89,9 @@ static void secp256k1_gej_verify(const secp256k1_gej *a) { secp256k1_fe_verify(&a->x); secp256k1_fe_verify(&a->y); secp256k1_fe_verify(&a->z); + secp256k1_fe_verify_magnitude(&a->x, SECP256K1_GEJ_X_MAGNITUDE_MAX); + secp256k1_fe_verify_magnitude(&a->y, SECP256K1_GEJ_Y_MAGNITUDE_MAX); + secp256k1_fe_verify_magnitude(&a->z, SECP256K1_GEJ_Z_MAGNITUDE_MAX); VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); #endif (void)a; @@ -99,11 +104,13 @@ static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, c secp256k1_gej_verify(a); secp256k1_fe_verify(zi); VERIFY_CHECK(!a->infinity); + secp256k1_fe_sqr(&zi2, zi); secp256k1_fe_mul(&zi3, &zi2, zi); secp256k1_fe_mul(&r->x, &a->x, &zi2); secp256k1_fe_mul(&r->y, &a->y, &zi3); r->infinity = a->infinity; + secp256k1_ge_verify(r); } @@ -114,39 +121,47 @@ static void secp256k1_ge_set_ge_zinv(secp256k1_ge *r, const secp256k1_ge *a, con secp256k1_ge_verify(a); secp256k1_fe_verify(zi); VERIFY_CHECK(!a->infinity); + secp256k1_fe_sqr(&zi2, zi); secp256k1_fe_mul(&zi3, &zi2, zi); secp256k1_fe_mul(&r->x, &a->x, &zi2); secp256k1_fe_mul(&r->y, &a->y, &zi3); r->infinity = a->infinity; + secp256k1_ge_verify(r); } static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) { secp256k1_fe_verify(x); secp256k1_fe_verify(y); + r->infinity = 0; r->x = *x; r->y = *y; + secp256k1_ge_verify(r); } static int secp256k1_ge_is_infinity(const secp256k1_ge *a) { secp256k1_ge_verify(a); + return a->infinity; } static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) { secp256k1_ge_verify(a); + *r = *a; secp256k1_fe_normalize_weak(&r->y); secp256k1_fe_negate(&r->y, &r->y, 1); + secp256k1_ge_verify(r); } static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a) { secp256k1_fe z2, z3; secp256k1_gej_verify(a); + r->infinity = a->infinity; secp256k1_fe_inv(&a->z, &a->z); secp256k1_fe_sqr(&z2, &a->z); @@ -156,12 +171,15 @@ static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a) { secp256k1_fe_set_int(&a->z, 1); r->x = a->x; r->y = a->y; + + secp256k1_gej_verify(a); secp256k1_ge_verify(r); } static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a) { secp256k1_fe z2, z3; secp256k1_gej_verify(a); + if (secp256k1_gej_is_infinity(a)) { secp256k1_ge_set_infinity(r); return; @@ -174,6 +192,8 @@ static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a) { secp256k1_fe_mul(&a->y, &a->y, &z3); secp256k1_fe_set_int(&a->z, 1); secp256k1_ge_set_xy(r, &a->x, &a->y); + + secp256k1_gej_verify(a); secp256k1_ge_verify(r); } @@ -181,9 +201,13 @@ static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a secp256k1_fe u; size_t i; size_t last_i = SIZE_MAX; - +#ifdef VERIFY for (i = 0; i < len; i++) { secp256k1_gej_verify(&a[i]); + } +#endif + + for (i = 0; i < len; i++) { if (a[i].infinity) { secp256k1_ge_set_infinity(&r[i]); } else { @@ -217,36 +241,46 @@ static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a if (!a[i].infinity) { secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x); } + } + +#ifdef VERIFY + for (i = 0; i < len; i++) { secp256k1_ge_verify(&r[i]); } +#endif } static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr) { - size_t i = len - 1; + size_t i; secp256k1_fe zs; - - if (len > 0) { - /* Verify inputs a[len-1] and zr[len-1]. */ +#ifdef VERIFY + for (i = 0; i < len; i++) { secp256k1_ge_verify(&a[i]); secp256k1_fe_verify(&zr[i]); + } +#endif + + if (len > 0) { + i = len - 1; /* Ensure all y values are in weak normal form for fast negation of points */ secp256k1_fe_normalize_weak(&a[i].y); zs = zr[i]; /* Work our way backwards, using the z-ratios to scale the x/y values. */ while (i > 0) { - /* Verify all inputs a[i] and zr[i]. */ - secp256k1_fe_verify(&zr[i]); - secp256k1_ge_verify(&a[i]); if (i != len - 1) { secp256k1_fe_mul(&zs, &zs, &zr[i]); } i--; secp256k1_ge_set_ge_zinv(&a[i], &a[i], &zs); - /* Verify the output a[i]. */ - secp256k1_ge_verify(&a[i]); } } + +#ifdef VERIFY + for (i = 0; i < len; i++) { + secp256k1_ge_verify(&a[i]); + } +#endif } static void secp256k1_gej_set_infinity(secp256k1_gej *r) { @@ -254,6 +288,7 @@ static void secp256k1_gej_set_infinity(secp256k1_gej *r) { secp256k1_fe_clear(&r->x); secp256k1_fe_clear(&r->y); secp256k1_fe_clear(&r->z); + secp256k1_gej_verify(r); } @@ -261,6 +296,7 @@ static void secp256k1_ge_set_infinity(secp256k1_ge *r) { r->infinity = 1; secp256k1_fe_clear(&r->x); secp256k1_fe_clear(&r->y); + secp256k1_ge_verify(r); } @@ -269,18 +305,23 @@ static void secp256k1_gej_clear(secp256k1_gej *r) { secp256k1_fe_clear(&r->x); secp256k1_fe_clear(&r->y); secp256k1_fe_clear(&r->z); + + secp256k1_gej_verify(r); } static void secp256k1_ge_clear(secp256k1_ge *r) { r->infinity = 0; secp256k1_fe_clear(&r->x); secp256k1_fe_clear(&r->y); + + secp256k1_ge_verify(r); } static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) { secp256k1_fe x2, x3; int ret; secp256k1_fe_verify(x); + r->x = *x; secp256k1_fe_sqr(&x2, x); secp256k1_fe_mul(&x3, x, &x2); @@ -291,16 +332,19 @@ static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int o if (secp256k1_fe_is_odd(&r->y) != odd) { secp256k1_fe_negate(&r->y, &r->y, 1); } + secp256k1_ge_verify(r); return ret; } static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a) { secp256k1_ge_verify(a); + r->infinity = a->infinity; r->x = a->x; r->y = a->y; secp256k1_fe_set_int(&r->z, 1); + secp256k1_gej_verify(r); } @@ -308,6 +352,7 @@ static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b) secp256k1_gej tmp; secp256k1_gej_verify(b); secp256k1_gej_verify(a); + secp256k1_gej_neg(&tmp, a); secp256k1_gej_add_var(&tmp, &tmp, b, NULL); return secp256k1_gej_is_infinity(&tmp); @@ -315,37 +360,39 @@ static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b) static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) { secp256k1_fe r; - -#ifdef VERIFY secp256k1_fe_verify(x); - VERIFY_CHECK(a->x.magnitude <= 31); secp256k1_gej_verify(a); +#ifdef VERIFY VERIFY_CHECK(!a->infinity); #endif secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x); - return secp256k1_fe_equal_var(&r, &a->x); + return secp256k1_fe_equal(&r, &a->x); } static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) { secp256k1_gej_verify(a); + r->infinity = a->infinity; r->x = a->x; r->y = a->y; r->z = a->z; secp256k1_fe_normalize_weak(&r->y); secp256k1_fe_negate(&r->y, &r->y, 1); + secp256k1_gej_verify(r); } static int secp256k1_gej_is_infinity(const secp256k1_gej *a) { secp256k1_gej_verify(a); + return a->infinity; } static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) { secp256k1_fe y2, x3; secp256k1_ge_verify(a); + if (a->infinity) { return 0; } @@ -353,14 +400,14 @@ static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) { secp256k1_fe_sqr(&y2, &a->y); secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); secp256k1_fe_add_int(&x3, SECP256K1_B); - return secp256k1_fe_equal_var(&y2, &x3); + return secp256k1_fe_equal(&y2, &x3); } static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a) { /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */ secp256k1_fe l, s, t; - secp256k1_gej_verify(a); + r->infinity = a->infinity; /* Formula used: @@ -387,10 +434,13 @@ static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp25 secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */ secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */ secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */ + secp256k1_gej_verify(r); } static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { + secp256k1_gej_verify(a); + /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. @@ -401,7 +451,6 @@ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, s * the infinity flag even though the point doubles to infinity, and the result * point will be gibberish (z = 0 but infinity = 0). */ - secp256k1_gej_verify(a); if (a->infinity) { secp256k1_gej_set_infinity(r); if (rzr != NULL) { @@ -416,15 +465,16 @@ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, s } secp256k1_gej_double(r, a); + secp256k1_gej_verify(r); } static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) { /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t; - secp256k1_gej_verify(a); secp256k1_gej_verify(b); + if (a->infinity) { VERIFY_CHECK(rzr == NULL); *r = *b; @@ -479,14 +529,16 @@ static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, cons secp256k1_fe_mul(&r->y, &t, &i); secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_add(&r->y, &h3); + secp256k1_gej_verify(r); } static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr) { - /* 8 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */ + /* Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ secp256k1_fe z12, u1, u2, s1, s2, h, i, h2, h3, t; secp256k1_gej_verify(a); secp256k1_ge_verify(b); + if (a->infinity) { VERIFY_CHECK(rzr == NULL); secp256k1_gej_set_ge(r, b); @@ -501,11 +553,11 @@ static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, c } secp256k1_fe_sqr(&z12, &a->z); - u1 = a->x; secp256k1_fe_normalize_weak(&u1); + u1 = a->x; secp256k1_fe_mul(&u2, &b->x, &z12); - s1 = a->y; secp256k1_fe_normalize_weak(&s1); + s1 = a->y; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z); - secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); + secp256k1_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); secp256k1_fe_add(&h, &u2); secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1); if (secp256k1_fe_normalizes_to_zero_var(&h)) { if (secp256k1_fe_normalizes_to_zero_var(&i)) { @@ -539,16 +591,18 @@ static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, c secp256k1_fe_mul(&r->y, &t, &i); secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_add(&r->y, &h3); + secp256k1_gej_verify(r); if (rzr != NULL) secp256k1_fe_verify(rzr); } static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) { - /* 9 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */ + /* Operations: 9 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t; - + secp256k1_gej_verify(a); secp256k1_ge_verify(b); secp256k1_fe_verify(bzinv); + if (a->infinity) { secp256k1_fe bzinv2, bzinv3; r->infinity = b->infinity; @@ -557,6 +611,7 @@ static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe_mul(&r->x, &b->x, &bzinv2); secp256k1_fe_mul(&r->y, &b->y, &bzinv3); secp256k1_fe_set_int(&r->z, 1); + secp256k1_gej_verify(r); return; } if (b->infinity) { @@ -575,11 +630,11 @@ static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe_mul(&az, &a->z, bzinv); secp256k1_fe_sqr(&z12, &az); - u1 = a->x; secp256k1_fe_normalize_weak(&u1); + u1 = a->x; secp256k1_fe_mul(&u2, &b->x, &z12); - s1 = a->y; secp256k1_fe_normalize_weak(&s1); + s1 = a->y; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az); - secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); + secp256k1_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); secp256k1_fe_add(&h, &u2); secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1); if (secp256k1_fe_normalizes_to_zero_var(&h)) { if (secp256k1_fe_normalizes_to_zero_var(&i)) { @@ -607,19 +662,19 @@ static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe_mul(&r->y, &t, &i); secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_add(&r->y, &h3); + secp256k1_gej_verify(r); } static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) { - /* Operations: 7 mul, 5 sqr, 24 add/cmov/half/mul_int/negate/normalize_weak/normalizes_to_zero */ + /* Operations: 7 mul, 5 sqr, 21 add/cmov/half/mul_int/negate/normalizes_to_zero */ secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr; secp256k1_fe m_alt, rr_alt; int degenerate; secp256k1_gej_verify(a); secp256k1_ge_verify(b); VERIFY_CHECK(!b->infinity); - VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); /* In: * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. @@ -672,17 +727,17 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const */ secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */ - u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */ + u1 = a->x; /* u1 = U1 = X1*Z2^2 (GEJ_X_M) */ secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */ - s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */ + s1 = a->y; /* s1 = S1 = Y1*Z2^3 (GEJ_Y_M) */ secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */ secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */ - t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */ - m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */ + t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (GEJ_X_M+1) */ + m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (GEJ_Y_M+1) */ secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */ - secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */ - secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */ - secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */ + secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 (2) */ + secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (1) */ + secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (2) */ /* If lambda = R/M = R/0 we have a problem (except in the "trivial" * case that Z = z1z2 = 0, and this is special-cased later on). */ degenerate = secp256k1_fe_normalizes_to_zero(&m); @@ -692,24 +747,25 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2), * so we set R/M equal to this. */ rr_alt = s1; - secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */ - secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */ + secp256k1_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3 - Y2*Z1^3 (GEJ_Y_M*2) */ + secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 (GEJ_X_M+2) */ - secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); - secp256k1_fe_cmov(&m_alt, &m, !degenerate); + secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (GEJ_Y_M*2) */ + secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (GEJ_X_M+2) */ /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0. * From here on out Ralt and Malt represent the numerator * and denominator of lambda; R and M represent the explicit * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */ secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */ - secp256k1_fe_negate(&q, &t, 2); /* q = -T (3) */ + secp256k1_fe_negate(&q, &t, + SECP256K1_GEJ_X_MAGNITUDE_MAX + 1); /* q = -T (GEJ_X_M+2) */ secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */ /* These two lines use the observation that either M == Malt or M == 0, * so M^3 * Malt is either Malt^4 (which is computed by squaring), or * zero (which is "computed" by cmov). So the cost is one squaring * versus two multiplications. */ - secp256k1_fe_sqr(&n, &n); - secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */ + secp256k1_fe_sqr(&n, &n); /* n = Malt^4 (1) */ + secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (GEJ_Y_M+1) */ secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */ secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */ secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */ @@ -717,9 +773,10 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */ secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */ secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */ - secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */ - secp256k1_fe_negate(&r->y, &t, 3); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (4) */ - secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */ + secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (GEJ_Y_M+2) */ + secp256k1_fe_negate(&r->y, &t, + SECP256K1_GEJ_Y_MAGNITUDE_MAX + 2); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (GEJ_Y_M+3) */ + secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 ((GEJ_Y_M+3)/2 + 1) */ /* In case a->infinity == 1, replace r with (b->x, b->y, 1). */ secp256k1_fe_cmov(&r->x, &b->x, a->infinity); @@ -743,6 +800,7 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const * We have degenerate = false, r->z = (y1 + y2) * Z. * Then r->infinity = ((y1 + y2)Z == 0) = (y1 == -y2) = false. */ r->infinity = secp256k1_fe_normalizes_to_zero(&r->z); + secp256k1_gej_verify(r); } @@ -754,11 +812,13 @@ static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s) { #ifdef VERIFY VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(s)); #endif + secp256k1_fe_sqr(&zz, s); secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */ secp256k1_fe_mul(&r->y, &r->y, &zz); secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */ secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */ + secp256k1_gej_verify(r); } @@ -766,6 +826,7 @@ static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge secp256k1_fe x, y; secp256k1_ge_verify(a); VERIFY_CHECK(!a->infinity); + x = a->x; secp256k1_fe_normalize(&x); y = a->y; @@ -778,17 +839,19 @@ static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storag secp256k1_fe_from_storage(&r->x, &a->x); secp256k1_fe_from_storage(&r->y, &a->y); r->infinity = 0; + secp256k1_ge_verify(r); } static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag) { secp256k1_gej_verify(r); secp256k1_gej_verify(a); + secp256k1_fe_cmov(&r->x, &a->x, flag); secp256k1_fe_cmov(&r->y, &a->y, flag); secp256k1_fe_cmov(&r->z, &a->z, flag); - r->infinity ^= (r->infinity ^ a->infinity) & flag; + secp256k1_gej_verify(r); } @@ -798,9 +861,11 @@ static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, } static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a) { - *r = *a; secp256k1_ge_verify(a); + + *r = *a; secp256k1_fe_mul(&r->x, &r->x, &secp256k1_const_beta); + secp256k1_ge_verify(r); } @@ -808,8 +873,8 @@ static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge* ge) { #ifdef EXHAUSTIVE_TEST_ORDER secp256k1_gej out; int i; - secp256k1_ge_verify(ge); + /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */ secp256k1_gej_set_infinity(&out); for (i = 0; i < 32; ++i) { @@ -820,6 +885,8 @@ static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge* ge) { } return secp256k1_gej_is_infinity(&out); #else + secp256k1_ge_verify(ge); + (void)ge; /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */ return 1; diff --git a/src/hash_impl.h b/src/hash_impl.h index 0991fe7838..89f75ace74 100644 --- a/src/hash_impl.h +++ b/src/hash_impl.h @@ -138,7 +138,7 @@ static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char * } if (len) { /* Fill the buffer with what remains. */ - memcpy(((unsigned char*)hash->buf) + bufsize, data, len); + memcpy(hash->buf + bufsize, data, len); } } diff --git a/src/modules/extrakeys/tests_exhaustive_impl.h b/src/modules/extrakeys/tests_exhaustive_impl.h index d3d817a131..645bae2d47 100644 --- a/src/modules/extrakeys/tests_exhaustive_impl.h +++ b/src/modules/extrakeys/tests_exhaustive_impl.h @@ -48,7 +48,7 @@ static void test_exhaustive_extrakeys(const secp256k1_context *ctx, const secp25 /* Compare the xonly_pubkey bytes against the precomputed group. */ secp256k1_fe_set_b32_mod(&fe, xonly_pubkey_bytes[i - 1]); - CHECK(secp256k1_fe_equal_var(&fe, &group[i].x)); + CHECK(secp256k1_fe_equal(&fe, &group[i].x)); /* Check the parity against the precomputed group. */ fe = group[i].y; diff --git a/src/modules/schnorrsig/main_impl.h b/src/modules/schnorrsig/main_impl.h index 4e7b45a045..26727e4651 100644 --- a/src/modules/schnorrsig/main_impl.h +++ b/src/modules/schnorrsig/main_impl.h @@ -261,7 +261,7 @@ int secp256k1_schnorrsig_verify(const secp256k1_context* ctx, const unsigned cha secp256k1_fe_normalize_var(&r.y); return !secp256k1_fe_is_odd(&r.y) && - secp256k1_fe_equal_var(&rx, &r.x); + secp256k1_fe_equal(&rx, &r.x); } #endif diff --git a/src/modules/schnorrsig/tests_exhaustive_impl.h b/src/modules/schnorrsig/tests_exhaustive_impl.h index 55f9028a63..bc31d81107 100644 --- a/src/modules/schnorrsig/tests_exhaustive_impl.h +++ b/src/modules/schnorrsig/tests_exhaustive_impl.h @@ -110,15 +110,15 @@ static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, cons if (!e_done[e]) { /* Iterate over the possible valid last 32 bytes in the signature. 0..order=that s value; order+1=random bytes */ - int count_valid = 0, s; + int count_valid = 0; + unsigned int s; for (s = 0; s <= EXHAUSTIVE_TEST_ORDER + 1; ++s) { int expect_valid, valid; if (s <= EXHAUSTIVE_TEST_ORDER) { - secp256k1_scalar s_s; - secp256k1_scalar_set_int(&s_s, s); - secp256k1_scalar_get_b32(sig64 + 32, &s_s); + memset(sig64 + 32, 0, 32); + secp256k1_write_be32(sig64 + 60, s); expect_valid = actual_k != -1 && s != EXHAUSTIVE_TEST_ORDER && - (s_s == (actual_k + actual_d * e) % EXHAUSTIVE_TEST_ORDER); + (s == (actual_k + actual_d * e) % EXHAUSTIVE_TEST_ORDER); } else { secp256k1_testrand256(sig64 + 32); expect_valid = 0; diff --git a/src/scalar.h b/src/scalar.h index 63c0d646a3..4b3c2998bb 100644 --- a/src/scalar.h +++ b/src/scalar.h @@ -99,4 +99,7 @@ static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_ /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag); +/** Check invariants on a scalar (no-op unless VERIFY is enabled). */ +static void secp256k1_scalar_verify(const secp256k1_scalar *r); + #endif /* SECP256K1_SCALAR_H */ diff --git a/src/scalar_4x64_impl.h b/src/scalar_4x64_impl.h index 1d14740577..715cc12ee5 100644 --- a/src/scalar_4x64_impl.h +++ b/src/scalar_4x64_impl.h @@ -41,16 +41,22 @@ SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsig r->d[1] = 0; r->d[2] = 0; r->d[3] = 0; + + secp256k1_scalar_verify(r); } SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); VERIFY_CHECK((offset + count - 1) >> 6 == offset >> 6); + return (a->d[offset >> 6] >> (offset & 0x3F)) & ((((uint64_t)1) << count) - 1); } SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); VERIFY_CHECK(count < 32); VERIFY_CHECK(offset + count <= 256); + if ((offset + count - 1) >> 6 == offset >> 6) { return secp256k1_scalar_get_bits(a, offset, count); } else { @@ -74,6 +80,7 @@ SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scal SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow) { secp256k1_uint128 t; VERIFY_CHECK(overflow <= 1); + secp256k1_u128_from_u64(&t, r->d[0]); secp256k1_u128_accum_u64(&t, overflow * SECP256K1_N_C_0); r->d[0] = secp256k1_u128_to_u64(&t); secp256k1_u128_rshift(&t, 64); @@ -85,12 +92,17 @@ SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigne r->d[2] = secp256k1_u128_to_u64(&t); secp256k1_u128_rshift(&t, 64); secp256k1_u128_accum_u64(&t, r->d[3]); r->d[3] = secp256k1_u128_to_u64(&t); + + secp256k1_scalar_verify(r); return overflow; } static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { int overflow; secp256k1_uint128 t; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + secp256k1_u128_from_u64(&t, a->d[0]); secp256k1_u128_accum_u64(&t, b->d[0]); r->d[0] = secp256k1_u128_to_u64(&t); secp256k1_u128_rshift(&t, 64); @@ -106,13 +118,17 @@ static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, overflow = secp256k1_u128_to_u64(&t) + secp256k1_scalar_check_overflow(r); VERIFY_CHECK(overflow == 0 || overflow == 1); secp256k1_scalar_reduce(r, overflow); + + secp256k1_scalar_verify(r); return overflow; } static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) { secp256k1_uint128 t; volatile int vflag = flag; + secp256k1_scalar_verify(r); VERIFY_CHECK(bit < 256); + bit += ((uint32_t) vflag - 1) & 0x100; /* forcing (bit >> 6) > 3 makes this a noop */ secp256k1_u128_from_u64(&t, r->d[0]); secp256k1_u128_accum_u64(&t, ((uint64_t)((bit >> 6) == 0)) << (bit & 0x3F)); @@ -126,6 +142,8 @@ static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int secp256k1_u128_accum_u64(&t, r->d[3]); secp256k1_u128_accum_u64(&t, ((uint64_t)((bit >> 6) == 3)) << (bit & 0x3F)); r->d[3] = secp256k1_u128_to_u64(&t); + + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(secp256k1_u128_hi_u64(&t) == 0); #endif @@ -141,9 +159,13 @@ static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b if (overflow) { *overflow = over; } + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) { + secp256k1_scalar_verify(a); + secp256k1_write_be64(&bin[0], a->d[3]); secp256k1_write_be64(&bin[8], a->d[2]); secp256k1_write_be64(&bin[16], a->d[1]); @@ -151,12 +173,16 @@ static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* } SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return (a->d[0] | a->d[1] | a->d[2] | a->d[3]) == 0; } static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) { uint64_t nonzero = 0xFFFFFFFFFFFFFFFFULL * (secp256k1_scalar_is_zero(a) == 0); secp256k1_uint128 t; + secp256k1_scalar_verify(a); + secp256k1_u128_from_u64(&t, ~a->d[0]); secp256k1_u128_accum_u64(&t, SECP256K1_N_0 + 1); r->d[0] = secp256k1_u128_to_u64(&t) & nonzero; secp256k1_u128_rshift(&t, 64); @@ -169,15 +195,21 @@ static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar secp256k1_u128_accum_u64(&t, ~a->d[3]); secp256k1_u128_accum_u64(&t, SECP256K1_N_3); r->d[3] = secp256k1_u128_to_u64(&t) & nonzero; + + secp256k1_scalar_verify(r); } SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return ((a->d[0] ^ 1) | a->d[1] | a->d[2] | a->d[3]) == 0; } static int secp256k1_scalar_is_high(const secp256k1_scalar *a) { int yes = 0; int no = 0; + secp256k1_scalar_verify(a); + no |= (a->d[3] < SECP256K1_N_H_3); yes |= (a->d[3] > SECP256K1_N_H_3) & ~no; no |= (a->d[2] < SECP256K1_N_H_2) & ~yes; /* No need for a > check. */ @@ -194,6 +226,8 @@ static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { uint64_t mask = -vflag; uint64_t nonzero = (secp256k1_scalar_is_zero(r) != 0) - 1; secp256k1_uint128 t; + secp256k1_scalar_verify(r); + secp256k1_u128_from_u64(&t, r->d[0] ^ mask); secp256k1_u128_accum_u64(&t, (SECP256K1_N_0 + 1) & mask); r->d[0] = secp256k1_u128_to_u64(&t) & nonzero; secp256k1_u128_rshift(&t, 64); @@ -206,6 +240,8 @@ static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { secp256k1_u128_accum_u64(&t, r->d[3] ^ mask); secp256k1_u128_accum_u64(&t, SECP256K1_N_3 & mask); r->d[3] = secp256k1_u128_to_u64(&t) & nonzero; + + secp256k1_scalar_verify(r); return 2 * (mask == 0) - 1; } @@ -764,23 +800,34 @@ static void secp256k1_scalar_mul_512(uint64_t l[8], const secp256k1_scalar *a, c static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { uint64_t l[8]; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + secp256k1_scalar_mul_512(l, a, b); secp256k1_scalar_reduce_512(r, l); + + secp256k1_scalar_verify(r); } static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) { int ret; + secp256k1_scalar_verify(r); VERIFY_CHECK(n > 0); VERIFY_CHECK(n < 16); + ret = r->d[0] & ((1 << n) - 1); r->d[0] = (r->d[0] >> n) + (r->d[1] << (64 - n)); r->d[1] = (r->d[1] >> n) + (r->d[2] << (64 - n)); r->d[2] = (r->d[2] >> n) + (r->d[3] << (64 - n)); r->d[3] = (r->d[3] >> n); + + secp256k1_scalar_verify(r); return ret; } static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k) { + secp256k1_scalar_verify(k); + r1->d[0] = k->d[0]; r1->d[1] = k->d[1]; r1->d[2] = 0; @@ -789,9 +836,15 @@ static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r r2->d[1] = k->d[3]; r2->d[2] = 0; r2->d[3] = 0; + + secp256k1_scalar_verify(r1); + secp256k1_scalar_verify(r2); } SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) { + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + return ((a->d[0] ^ b->d[0]) | (a->d[1] ^ b->d[1]) | (a->d[2] ^ b->d[2]) | (a->d[3] ^ b->d[3])) == 0; } @@ -800,7 +853,10 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, unsigned int shiftlimbs; unsigned int shiftlow; unsigned int shifthigh; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); VERIFY_CHECK(shift >= 256); + secp256k1_scalar_mul_512(l, a, b); shiftlimbs = shift >> 6; shiftlow = shift & 0x3F; @@ -810,18 +866,24 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, r->d[2] = shift < 384 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0; r->d[3] = shift < 320 ? (l[3 + shiftlimbs] >> shiftlow) : 0; secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1); + + secp256k1_scalar_verify(r); } static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { uint64_t mask0, mask1; volatile int vflag = flag; + secp256k1_scalar_verify(a); SECP256K1_CHECKMEM_CHECK_VERIFY(r->d, sizeof(r->d)); + mask0 = vflag + ~((uint64_t)0); mask1 = ~mask0; r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1); r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1); r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1); r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1); + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_from_signed62(secp256k1_scalar *r, const secp256k1_modinv64_signed62 *a) { @@ -841,18 +903,13 @@ static void secp256k1_scalar_from_signed62(secp256k1_scalar *r, const secp256k1_ r->d[2] = a2 >> 4 | a3 << 58; r->d[3] = a3 >> 6 | a4 << 56; -#ifdef VERIFY - VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); -#endif + secp256k1_scalar_verify(r); } static void secp256k1_scalar_to_signed62(secp256k1_modinv64_signed62 *r, const secp256k1_scalar *a) { const uint64_t M62 = UINT64_MAX >> 2; const uint64_t a0 = a->d[0], a1 = a->d[1], a2 = a->d[2], a3 = a->d[3]; - -#ifdef VERIFY - VERIFY_CHECK(secp256k1_scalar_check_overflow(a) == 0); -#endif + secp256k1_scalar_verify(a); r->v[0] = a0 & M62; r->v[1] = (a0 >> 62 | a1 << 2) & M62; @@ -871,10 +928,13 @@ static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar #ifdef VERIFY int zero_in = secp256k1_scalar_is_zero(x); #endif + secp256k1_scalar_verify(x); + secp256k1_scalar_to_signed62(&s, x); secp256k1_modinv64(&s, &secp256k1_const_modinfo_scalar); secp256k1_scalar_from_signed62(r, &s); + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in); #endif @@ -885,16 +945,21 @@ static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_sc #ifdef VERIFY int zero_in = secp256k1_scalar_is_zero(x); #endif + secp256k1_scalar_verify(x); + secp256k1_scalar_to_signed62(&s, x); secp256k1_modinv64_var(&s, &secp256k1_const_modinfo_scalar); secp256k1_scalar_from_signed62(r, &s); + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in); #endif } SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return !(a->d[0] & 1); } diff --git a/src/scalar_8x32_impl.h b/src/scalar_8x32_impl.h index 80ef3ef248..5ca1342273 100644 --- a/src/scalar_8x32_impl.h +++ b/src/scalar_8x32_impl.h @@ -58,16 +58,22 @@ SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsig r->d[5] = 0; r->d[6] = 0; r->d[7] = 0; + + secp256k1_scalar_verify(r); } SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); VERIFY_CHECK((offset + count - 1) >> 5 == offset >> 5); + return (a->d[offset >> 5] >> (offset & 0x1F)) & ((1 << count) - 1); } SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); VERIFY_CHECK(count < 32); VERIFY_CHECK(offset + count <= 256); + if ((offset + count - 1) >> 5 == offset >> 5) { return secp256k1_scalar_get_bits(a, offset, count); } else { @@ -97,6 +103,7 @@ SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scal SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, uint32_t overflow) { uint64_t t; VERIFY_CHECK(overflow <= 1); + t = (uint64_t)r->d[0] + overflow * SECP256K1_N_C_0; r->d[0] = t & 0xFFFFFFFFUL; t >>= 32; t += (uint64_t)r->d[1] + overflow * SECP256K1_N_C_1; @@ -113,12 +120,17 @@ SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, uint32_ r->d[6] = t & 0xFFFFFFFFUL; t >>= 32; t += (uint64_t)r->d[7]; r->d[7] = t & 0xFFFFFFFFUL; + + secp256k1_scalar_verify(r); return overflow; } static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { int overflow; uint64_t t = (uint64_t)a->d[0] + b->d[0]; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + r->d[0] = t & 0xFFFFFFFFULL; t >>= 32; t += (uint64_t)a->d[1] + b->d[1]; r->d[1] = t & 0xFFFFFFFFULL; t >>= 32; @@ -137,13 +149,17 @@ static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, overflow = t + secp256k1_scalar_check_overflow(r); VERIFY_CHECK(overflow == 0 || overflow == 1); secp256k1_scalar_reduce(r, overflow); + + secp256k1_scalar_verify(r); return overflow; } static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) { uint64_t t; volatile int vflag = flag; + secp256k1_scalar_verify(r); VERIFY_CHECK(bit < 256); + bit += ((uint32_t) vflag - 1) & 0x100; /* forcing (bit >> 5) > 7 makes this a noop */ t = (uint64_t)r->d[0] + (((uint32_t)((bit >> 5) == 0)) << (bit & 0x1F)); r->d[0] = t & 0xFFFFFFFFULL; t >>= 32; @@ -161,9 +177,10 @@ static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int r->d[6] = t & 0xFFFFFFFFULL; t >>= 32; t += (uint64_t)r->d[7] + (((uint32_t)((bit >> 5) == 7)) << (bit & 0x1F)); r->d[7] = t & 0xFFFFFFFFULL; + + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK((t >> 32) == 0); - VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); #endif } @@ -181,9 +198,13 @@ static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b if (overflow) { *overflow = over; } + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) { + secp256k1_scalar_verify(a); + secp256k1_write_be32(&bin[0], a->d[7]); secp256k1_write_be32(&bin[4], a->d[6]); secp256k1_write_be32(&bin[8], a->d[5]); @@ -195,12 +216,16 @@ static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* } SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return (a->d[0] | a->d[1] | a->d[2] | a->d[3] | a->d[4] | a->d[5] | a->d[6] | a->d[7]) == 0; } static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) { uint32_t nonzero = 0xFFFFFFFFUL * (secp256k1_scalar_is_zero(a) == 0); uint64_t t = (uint64_t)(~a->d[0]) + SECP256K1_N_0 + 1; + secp256k1_scalar_verify(a); + r->d[0] = t & nonzero; t >>= 32; t += (uint64_t)(~a->d[1]) + SECP256K1_N_1; r->d[1] = t & nonzero; t >>= 32; @@ -216,15 +241,21 @@ static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar r->d[6] = t & nonzero; t >>= 32; t += (uint64_t)(~a->d[7]) + SECP256K1_N_7; r->d[7] = t & nonzero; + + secp256k1_scalar_verify(r); } SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return ((a->d[0] ^ 1) | a->d[1] | a->d[2] | a->d[3] | a->d[4] | a->d[5] | a->d[6] | a->d[7]) == 0; } static int secp256k1_scalar_is_high(const secp256k1_scalar *a) { int yes = 0; int no = 0; + secp256k1_scalar_verify(a); + no |= (a->d[7] < SECP256K1_N_H_7); yes |= (a->d[7] > SECP256K1_N_H_7) & ~no; no |= (a->d[6] < SECP256K1_N_H_6) & ~yes; /* No need for a > check. */ @@ -247,6 +278,8 @@ static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { uint32_t mask = -vflag; uint32_t nonzero = 0xFFFFFFFFUL * (secp256k1_scalar_is_zero(r) == 0); uint64_t t = (uint64_t)(r->d[0] ^ mask) + ((SECP256K1_N_0 + 1) & mask); + secp256k1_scalar_verify(r); + r->d[0] = t & nonzero; t >>= 32; t += (uint64_t)(r->d[1] ^ mask) + (SECP256K1_N_1 & mask); r->d[1] = t & nonzero; t >>= 32; @@ -262,6 +295,8 @@ static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { r->d[6] = t & nonzero; t >>= 32; t += (uint64_t)(r->d[7] ^ mask) + (SECP256K1_N_7 & mask); r->d[7] = t & nonzero; + + secp256k1_scalar_verify(r); return 2 * (mask == 0) - 1; } @@ -569,14 +604,21 @@ static void secp256k1_scalar_mul_512(uint32_t *l, const secp256k1_scalar *a, con static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { uint32_t l[16]; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + secp256k1_scalar_mul_512(l, a, b); secp256k1_scalar_reduce_512(r, l); + + secp256k1_scalar_verify(r); } static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) { int ret; + secp256k1_scalar_verify(r); VERIFY_CHECK(n > 0); VERIFY_CHECK(n < 16); + ret = r->d[0] & ((1 << n) - 1); r->d[0] = (r->d[0] >> n) + (r->d[1] << (32 - n)); r->d[1] = (r->d[1] >> n) + (r->d[2] << (32 - n)); @@ -586,10 +628,14 @@ static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) { r->d[5] = (r->d[5] >> n) + (r->d[6] << (32 - n)); r->d[6] = (r->d[6] >> n) + (r->d[7] << (32 - n)); r->d[7] = (r->d[7] >> n); + + secp256k1_scalar_verify(r); return ret; } static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k) { + secp256k1_scalar_verify(k); + r1->d[0] = k->d[0]; r1->d[1] = k->d[1]; r1->d[2] = k->d[2]; @@ -606,9 +652,15 @@ static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r r2->d[5] = 0; r2->d[6] = 0; r2->d[7] = 0; + + secp256k1_scalar_verify(r1); + secp256k1_scalar_verify(r2); } SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) { + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + return ((a->d[0] ^ b->d[0]) | (a->d[1] ^ b->d[1]) | (a->d[2] ^ b->d[2]) | (a->d[3] ^ b->d[3]) | (a->d[4] ^ b->d[4]) | (a->d[5] ^ b->d[5]) | (a->d[6] ^ b->d[6]) | (a->d[7] ^ b->d[7])) == 0; } @@ -617,7 +669,10 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, unsigned int shiftlimbs; unsigned int shiftlow; unsigned int shifthigh; + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); VERIFY_CHECK(shift >= 256); + secp256k1_scalar_mul_512(l, a, b); shiftlimbs = shift >> 5; shiftlow = shift & 0x1F; @@ -631,12 +686,16 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, r->d[6] = shift < 320 ? (l[6 + shiftlimbs] >> shiftlow | (shift < 288 && shiftlow ? (l[7 + shiftlimbs] << shifthigh) : 0)) : 0; r->d[7] = shift < 288 ? (l[7 + shiftlimbs] >> shiftlow) : 0; secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1); + + secp256k1_scalar_verify(r); } static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { uint32_t mask0, mask1; volatile int vflag = flag; + secp256k1_scalar_verify(a); SECP256K1_CHECKMEM_CHECK_VERIFY(r->d, sizeof(r->d)); + mask0 = vflag + ~((uint32_t)0); mask1 = ~mask0; r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1); @@ -647,6 +706,8 @@ static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const se r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1); r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1); r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1); + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_from_signed30(secp256k1_scalar *r, const secp256k1_modinv32_signed30 *a) { @@ -675,19 +736,14 @@ static void secp256k1_scalar_from_signed30(secp256k1_scalar *r, const secp256k1_ r->d[6] = a6 >> 12 | a7 << 18; r->d[7] = a7 >> 14 | a8 << 16; -#ifdef VERIFY - VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); -#endif + secp256k1_scalar_verify(r); } static void secp256k1_scalar_to_signed30(secp256k1_modinv32_signed30 *r, const secp256k1_scalar *a) { const uint32_t M30 = UINT32_MAX >> 2; const uint32_t a0 = a->d[0], a1 = a->d[1], a2 = a->d[2], a3 = a->d[3], a4 = a->d[4], a5 = a->d[5], a6 = a->d[6], a7 = a->d[7]; - -#ifdef VERIFY - VERIFY_CHECK(secp256k1_scalar_check_overflow(a) == 0); -#endif + secp256k1_scalar_verify(a); r->v[0] = a0 & M30; r->v[1] = (a0 >> 30 | a1 << 2) & M30; @@ -710,10 +766,13 @@ static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar #ifdef VERIFY int zero_in = secp256k1_scalar_is_zero(x); #endif + secp256k1_scalar_verify(x); + secp256k1_scalar_to_signed30(&s, x); secp256k1_modinv32(&s, &secp256k1_const_modinfo_scalar); secp256k1_scalar_from_signed30(r, &s); + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in); #endif @@ -724,16 +783,21 @@ static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_sc #ifdef VERIFY int zero_in = secp256k1_scalar_is_zero(x); #endif + secp256k1_scalar_verify(x); + secp256k1_scalar_to_signed30(&s, x); secp256k1_modinv32_var(&s, &secp256k1_const_modinfo_scalar); secp256k1_scalar_from_signed30(r, &s); + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in); #endif } SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return !(a->d[0] & 1); } diff --git a/src/scalar_impl.h b/src/scalar_impl.h index bed7f95fcb..3eca23b4f9 100644 --- a/src/scalar_impl.h +++ b/src/scalar_impl.h @@ -30,9 +30,19 @@ static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin) { int overflow; secp256k1_scalar_set_b32(r, bin, &overflow); + + secp256k1_scalar_verify(r); return (!overflow) & (!secp256k1_scalar_is_zero(r)); } +static void secp256k1_scalar_verify(const secp256k1_scalar *r) { +#ifdef VERIFY + VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); +#endif + + (void)r; +} + #if defined(EXHAUSTIVE_TEST_ORDER) /* Begin of section generated by sage/gen_exhaustive_groups.sage. */ # if EXHAUSTIVE_TEST_ORDER == 7 @@ -53,11 +63,16 @@ static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned c * (arbitrarily) set r2 = k + 5 (mod n) and r1 = k - r2 * lambda (mod n). */ static void secp256k1_scalar_split_lambda(secp256k1_scalar * SECP256K1_RESTRICT r1, secp256k1_scalar * SECP256K1_RESTRICT r2, const secp256k1_scalar * SECP256K1_RESTRICT k) { + secp256k1_scalar_verify(k); VERIFY_CHECK(r1 != k); VERIFY_CHECK(r2 != k); VERIFY_CHECK(r1 != r2); + *r2 = (*k + 5) % EXHAUSTIVE_TEST_ORDER; *r1 = (*k + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER; + + secp256k1_scalar_verify(r1); + secp256k1_scalar_verify(r2); } #else /** @@ -140,9 +155,11 @@ static void secp256k1_scalar_split_lambda(secp256k1_scalar * SECP256K1_RESTRICT 0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C4UL, 0x221208ACUL, 0x9DF506C6UL, 0x1571B4AEUL, 0x8AC47F71UL ); + secp256k1_scalar_verify(k); VERIFY_CHECK(r1 != k); VERIFY_CHECK(r2 != k); VERIFY_CHECK(r1 != r2); + /* these _var calls are constant time since the shift amount is constant */ secp256k1_scalar_mul_shift_var(&c1, k, &g1, 384); secp256k1_scalar_mul_shift_var(&c2, k, &g2, 384); @@ -153,6 +170,8 @@ static void secp256k1_scalar_split_lambda(secp256k1_scalar * SECP256K1_RESTRICT secp256k1_scalar_negate(r1, r1); secp256k1_scalar_add(r1, r1, k); + secp256k1_scalar_verify(r1); + secp256k1_scalar_verify(r2); #ifdef VERIFY secp256k1_scalar_split_lambda_verify(r1, r2, k); #endif diff --git a/src/scalar_low_impl.h b/src/scalar_low_impl.h index 428a5deb33..e2356a5be1 100644 --- a/src/scalar_low_impl.h +++ b/src/scalar_low_impl.h @@ -14,13 +14,22 @@ #include SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return !(*a & 1); } SECP256K1_INLINE static void secp256k1_scalar_clear(secp256k1_scalar *r) { *r = 0; } -SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) { *r = v; } + +SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) { + *r = v % EXHAUSTIVE_TEST_ORDER; + + secp256k1_scalar_verify(r); +} SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); + if (offset < 32) return ((*a >> offset) & ((((uint32_t)1) << count) - 1)); else @@ -28,24 +37,34 @@ SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_s } SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + secp256k1_scalar_verify(a); + return secp256k1_scalar_get_bits(a, offset, count); } SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) { return *a >= EXHAUSTIVE_TEST_ORDER; } static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + *r = (*a + *b) % EXHAUSTIVE_TEST_ORDER; + + secp256k1_scalar_verify(r); return *r < *b; } static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) { + secp256k1_scalar_verify(r); + if (flag && bit < 32) *r += ((uint32_t)1 << bit); + + secp256k1_scalar_verify(r); #ifdef VERIFY VERIFY_CHECK(bit < 32); /* Verify that adding (1 << bit) will not overflow any in-range scalar *r by overflowing the underlying uint32_t. */ VERIFY_CHECK(((uint32_t)1 << bit) - 1 <= UINT32_MAX - EXHAUSTIVE_TEST_ORDER); - VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); #endif } @@ -61,82 +80,129 @@ static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b } } if (overflow) *overflow = over; + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) { + secp256k1_scalar_verify(a); + memset(bin, 0, 32); bin[28] = *a >> 24; bin[29] = *a >> 16; bin[30] = *a >> 8; bin[31] = *a; } SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return *a == 0; } static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + if (*a == 0) { *r = 0; } else { *r = EXHAUSTIVE_TEST_ORDER - *a; } + + secp256k1_scalar_verify(r); } SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return *a == 1; } static int secp256k1_scalar_is_high(const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + return *a > EXHAUSTIVE_TEST_ORDER / 2; } static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { + secp256k1_scalar_verify(r); + if (flag) secp256k1_scalar_negate(r, r); + + secp256k1_scalar_verify(r); return flag ? -1 : 1; } static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + *r = (*a * *b) % EXHAUSTIVE_TEST_ORDER; + + secp256k1_scalar_verify(r); } static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) { int ret; + secp256k1_scalar_verify(r); VERIFY_CHECK(n > 0); VERIFY_CHECK(n < 16); + ret = *r & ((1 << n) - 1); *r >>= n; + + secp256k1_scalar_verify(r); return ret; } static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { + secp256k1_scalar_verify(a); + *r1 = *a; *r2 = 0; + + secp256k1_scalar_verify(r1); + secp256k1_scalar_verify(r2); } SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) { + secp256k1_scalar_verify(a); + secp256k1_scalar_verify(b); + return *a == *b; } static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { uint32_t mask0, mask1; volatile int vflag = flag; + secp256k1_scalar_verify(a); SECP256K1_CHECKMEM_CHECK_VERIFY(r, sizeof(*r)); + mask0 = vflag + ~((uint32_t)0); mask1 = ~mask0; *r = (*r & mask0) | (*a & mask1); + + secp256k1_scalar_verify(r); } static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) { int i; *r = 0; + secp256k1_scalar_verify(x); + for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) if ((i * *x) % EXHAUSTIVE_TEST_ORDER == 1) *r = i; + + secp256k1_scalar_verify(r); /* If this VERIFY_CHECK triggers we were given a noninvertible scalar (and thus * have a composite group order; fix it in exhaustive_tests.c). */ VERIFY_CHECK(*r != 0); } static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) { + secp256k1_scalar_verify(x); + secp256k1_scalar_inverse(r, x); + + secp256k1_scalar_verify(r); } #endif /* SECP256K1_SCALAR_REPR_IMPL_H */ diff --git a/src/tests.c b/src/tests.c index 920d31b481..d3959406c7 100644 --- a/src/tests.c +++ b/src/tests.c @@ -89,9 +89,9 @@ static void uncounting_illegal_callback_fn(const char* str, void* data) { (*p)--; } -static void random_field_element_magnitude(secp256k1_fe *fe) { +static void random_field_element_magnitude(secp256k1_fe *fe, int m) { secp256k1_fe zero; - int n = secp256k1_testrand_int(9); + int n = secp256k1_testrand_int(m + 1); secp256k1_fe_normalize(fe); if (n == 0) { return; @@ -121,6 +121,30 @@ static void random_fe_non_zero_test(secp256k1_fe *fe) { } while(secp256k1_fe_is_zero(fe)); } +static void random_fe_magnitude(secp256k1_fe *fe) { + random_field_element_magnitude(fe, 8); +} + +static void random_ge_x_magnitude(secp256k1_ge *ge) { + random_field_element_magnitude(&ge->x, SECP256K1_GE_X_MAGNITUDE_MAX); +} + +static void random_ge_y_magnitude(secp256k1_ge *ge) { + random_field_element_magnitude(&ge->y, SECP256K1_GE_Y_MAGNITUDE_MAX); +} + +static void random_gej_x_magnitude(secp256k1_gej *gej) { + random_field_element_magnitude(&gej->x, SECP256K1_GEJ_X_MAGNITUDE_MAX); +} + +static void random_gej_y_magnitude(secp256k1_gej *gej) { + random_field_element_magnitude(&gej->y, SECP256K1_GEJ_Y_MAGNITUDE_MAX); +} + +static void random_gej_z_magnitude(secp256k1_gej *gej) { + random_field_element_magnitude(&gej->z, SECP256K1_GEJ_Z_MAGNITUDE_MAX); +} + static void random_group_element_test(secp256k1_ge *ge) { secp256k1_fe fe; do { @@ -2967,8 +2991,7 @@ static int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) { secp256k1_fe an = *a; secp256k1_fe bn = *b; secp256k1_fe_normalize_weak(&an); - secp256k1_fe_normalize_var(&bn); - return secp256k1_fe_equal_var(&an, &bn); + return secp256k1_fe_equal(&an, &bn); } static void run_field_convert(void) { @@ -2991,9 +3014,9 @@ static void run_field_convert(void) { secp256k1_fe_storage fes2; /* Check conversions to fe. */ CHECK(secp256k1_fe_set_b32_limit(&fe2, b32)); - CHECK(secp256k1_fe_equal_var(&fe, &fe2)); + CHECK(secp256k1_fe_equal(&fe, &fe2)); secp256k1_fe_from_storage(&fe2, &fes); - CHECK(secp256k1_fe_equal_var(&fe, &fe2)); + CHECK(secp256k1_fe_equal(&fe, &fe2)); /* Check conversion from fe. */ secp256k1_fe_get_b32(b322, &fe); CHECK(secp256k1_memcmp_var(b322, b32, 32) == 0); @@ -3150,7 +3173,7 @@ static void run_field_misc(void) { CHECK(check_fe_equal(&q, &z)); /* Test the fe equality and comparison operations. */ CHECK(secp256k1_fe_cmp_var(&x, &x) == 0); - CHECK(secp256k1_fe_equal_var(&x, &x)); + CHECK(secp256k1_fe_equal(&x, &x)); z = x; secp256k1_fe_add(&z,&y); /* Test fe conditional move; z is not normalized here. */ @@ -3175,7 +3198,7 @@ static void run_field_misc(void) { q = z; secp256k1_fe_normalize_var(&x); secp256k1_fe_normalize_var(&z); - CHECK(!secp256k1_fe_equal_var(&x, &z)); + CHECK(!secp256k1_fe_equal(&x, &z)); secp256k1_fe_normalize_var(&q); secp256k1_fe_cmov(&q, &z, (i&1)); #ifdef VERIFY @@ -3279,13 +3302,13 @@ static void run_fe_mul(void) { for (i = 0; i < 100 * COUNT; ++i) { secp256k1_fe a, b, c, d; random_fe(&a); - random_field_element_magnitude(&a); + random_fe_magnitude(&a); random_fe(&b); - random_field_element_magnitude(&b); + random_fe_magnitude(&b); random_fe_test(&c); - random_field_element_magnitude(&c); + random_fe_magnitude(&c); random_fe_test(&d); - random_field_element_magnitude(&d); + random_fe_magnitude(&d); test_fe_mul(&a, &a, 1); test_fe_mul(&c, &c, 1); test_fe_mul(&a, &b, 0); @@ -3680,8 +3703,8 @@ static void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) { if (a->infinity) { return; } - CHECK(secp256k1_fe_equal_var(&a->x, &b->x)); - CHECK(secp256k1_fe_equal_var(&a->y, &b->y)); + CHECK(secp256k1_fe_equal(&a->x, &b->x)); + CHECK(secp256k1_fe_equal(&a->y, &b->y)); } /* This compares jacobian points including their Z, not just their geometric meaning. */ @@ -3716,11 +3739,11 @@ static void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) { /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */ secp256k1_fe_sqr(&z2s, &b->z); secp256k1_fe_mul(&u1, &a->x, &z2s); - u2 = b->x; secp256k1_fe_normalize_weak(&u2); + u2 = b->x; secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z); - s2 = b->y; secp256k1_fe_normalize_weak(&s2); - CHECK(secp256k1_fe_equal_var(&u1, &u2)); - CHECK(secp256k1_fe_equal_var(&s1, &s2)); + s2 = b->y; + CHECK(secp256k1_fe_equal(&u1, &u2)); + CHECK(secp256k1_fe_equal(&s1, &s2)); } static void test_ge(void) { @@ -3759,17 +3782,17 @@ static void test_ge(void) { secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]); random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]); for (j = 0; j < 4; j++) { - random_field_element_magnitude(&ge[1 + j + 4 * i].x); - random_field_element_magnitude(&ge[1 + j + 4 * i].y); - random_field_element_magnitude(&gej[1 + j + 4 * i].x); - random_field_element_magnitude(&gej[1 + j + 4 * i].y); - random_field_element_magnitude(&gej[1 + j + 4 * i].z); + random_ge_x_magnitude(&ge[1 + j + 4 * i]); + random_ge_y_magnitude(&ge[1 + j + 4 * i]); + random_gej_x_magnitude(&gej[1 + j + 4 * i]); + random_gej_y_magnitude(&gej[1 + j + 4 * i]); + random_gej_z_magnitude(&gej[1 + j + 4 * i]); } } /* Generate random zf, and zfi2 = 1/zf^2, zfi3 = 1/zf^3 */ random_fe_non_zero_test(&zf); - random_field_element_magnitude(&zf); + random_fe_magnitude(&zf); secp256k1_fe_inv_var(&zfi3, &zf); secp256k1_fe_sqr(&zfi2, &zfi3); secp256k1_fe_mul(&zfi3, &zfi3, &zfi2); @@ -3788,7 +3811,7 @@ static void test_ge(void) { /* Check Z ratio. */ if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&refj)) { secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z); - CHECK(secp256k1_fe_equal_var(&zrz, &refj.z)); + CHECK(secp256k1_fe_equal(&zrz, &refj.z)); } secp256k1_ge_set_gej_var(&ref, &refj); @@ -3797,7 +3820,7 @@ static void test_ge(void) { ge_equals_gej(&ref, &resj); if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&resj)) { secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z); - CHECK(secp256k1_fe_equal_var(&zrz, &resj.z)); + CHECK(secp256k1_fe_equal(&zrz, &resj.z)); } /* Test gej + ge (var, with additional Z factor). */ @@ -3805,8 +3828,8 @@ static void test_ge(void) { secp256k1_ge ge2_zfi = ge[i2]; /* the second term with x and y rescaled for z = 1/zf */ secp256k1_fe_mul(&ge2_zfi.x, &ge2_zfi.x, &zfi2); secp256k1_fe_mul(&ge2_zfi.y, &ge2_zfi.y, &zfi3); - random_field_element_magnitude(&ge2_zfi.x); - random_field_element_magnitude(&ge2_zfi.y); + random_ge_x_magnitude(&ge2_zfi); + random_ge_y_magnitude(&ge2_zfi); secp256k1_gej_add_zinv_var(&resj, &gej[i1], &ge2_zfi, &zf); ge_equals_gej(&ref, &resj); } @@ -3826,7 +3849,7 @@ static void test_ge(void) { ge_equals_gej(&ref, &resj); /* Check Z ratio. */ secp256k1_fe_mul(&zr2, &zr2, &gej[i1].z); - CHECK(secp256k1_fe_equal_var(&zr2, &resj.z)); + CHECK(secp256k1_fe_equal(&zr2, &resj.z)); /* Normal doubling. */ secp256k1_gej_double_var(&resj, &gej[i2], NULL); ge_equals_gej(&ref, &resj); @@ -3909,7 +3932,7 @@ static void test_ge(void) { ret_set_xo = secp256k1_ge_set_xo_var(&q, &r, 0); CHECK(ret_on_curve == ret_frac_on_curve); CHECK(ret_on_curve == ret_set_xo); - if (ret_set_xo) CHECK(secp256k1_fe_equal_var(&r, &q.x)); + if (ret_set_xo) CHECK(secp256k1_fe_equal(&r, &q.x)); } /* Test batch gej -> ge conversion with many infinities. */ @@ -4092,7 +4115,7 @@ static void run_gej(void) { } static void test_ec_combine(void) { - secp256k1_scalar sum = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + secp256k1_scalar sum = secp256k1_scalar_zero; secp256k1_pubkey data[6]; const secp256k1_pubkey* d[6]; secp256k1_pubkey sd; @@ -4149,8 +4172,8 @@ static void test_group_decompress(const secp256k1_fe* x) { CHECK(!ge_odd.infinity); /* Check that the x coordinates check out. */ - CHECK(secp256k1_fe_equal_var(&ge_even.x, x)); - CHECK(secp256k1_fe_equal_var(&ge_odd.x, x)); + CHECK(secp256k1_fe_equal(&ge_even.x, x)); + CHECK(secp256k1_fe_equal(&ge_odd.x, x)); /* Check odd/even Y in ge_odd, ge_even. */ CHECK(secp256k1_fe_is_odd(&ge_odd.y)); @@ -4202,18 +4225,18 @@ static void test_pre_g_table(const secp256k1_ge_storage * pre_g, size_t n) { secp256k1_ge_from_storage(&q, &pre_g[i]); CHECK(secp256k1_ge_is_valid_var(&q)); - secp256k1_fe_negate(&dqx, &q.x, 1); secp256k1_fe_add(&dqx, &gg.x); secp256k1_fe_normalize_weak(&dqx); - dqy = q.y; secp256k1_fe_add(&dqy, &gg.y); secp256k1_fe_normalize_weak(&dqy); + secp256k1_fe_negate(&dqx, &q.x, 1); secp256k1_fe_add(&dqx, &gg.x); + dqy = q.y; secp256k1_fe_add(&dqy, &gg.y); /* Check that -q is not equal to gg */ CHECK(!secp256k1_fe_normalizes_to_zero_var(&dqx) || !secp256k1_fe_normalizes_to_zero_var(&dqy)); /* Check that -q is not equal to p */ - CHECK(!secp256k1_fe_equal_var(&dpx, &dqx) || !secp256k1_fe_equal_var(&dpy, &dqy)); + CHECK(!secp256k1_fe_equal(&dpx, &dqx) || !secp256k1_fe_equal(&dpy, &dqy)); /* Check that p, -q and gg are colinear */ secp256k1_fe_mul(&dpx, &dpx, &dqy); secp256k1_fe_mul(&dpy, &dpy, &dqx); - CHECK(secp256k1_fe_equal_var(&dpx, &dpy)); + CHECK(secp256k1_fe_equal(&dpx, &dpy)); p = q; } @@ -4264,8 +4287,8 @@ static void run_ecmult_chain(void) { static const secp256k1_scalar xf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x1337); static const secp256k1_scalar gf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x7113); /* accumulators with the resulting coefficients to A and G */ - secp256k1_scalar ae = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); - secp256k1_scalar ge = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + secp256k1_scalar ae = secp256k1_scalar_one; + secp256k1_scalar ge = secp256k1_scalar_zero; /* actual points */ secp256k1_gej x; secp256k1_gej x2; @@ -4306,8 +4329,6 @@ static void test_point_times_order(const secp256k1_gej *point) { /* X * (point + G) + (order-X) * (pointer + G) = 0 */ secp256k1_scalar x; secp256k1_scalar nx; - secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); - secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); secp256k1_gej res1, res2; secp256k1_ge res3; unsigned char pub[65]; @@ -4325,13 +4346,13 @@ static void test_point_times_order(const secp256k1_gej *point) { psize = 65; CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0); /* check zero/one edge cases */ - secp256k1_ecmult(&res1, point, &zero, &zero); + secp256k1_ecmult(&res1, point, &secp256k1_scalar_zero, &secp256k1_scalar_zero); secp256k1_ge_set_gej(&res3, &res1); CHECK(secp256k1_ge_is_infinity(&res3)); - secp256k1_ecmult(&res1, point, &one, &zero); + secp256k1_ecmult(&res1, point, &secp256k1_scalar_one, &secp256k1_scalar_zero); secp256k1_ge_set_gej(&res3, &res1); ge_equals_gej(&res3, point); - secp256k1_ecmult(&res1, point, &zero, &one); + secp256k1_ecmult(&res1, point, &secp256k1_scalar_zero, &secp256k1_scalar_one); secp256k1_ge_set_gej(&res3, &res1); ge_equals_ge(&res3, &secp256k1_ge_const_g); } @@ -4371,7 +4392,6 @@ static void test_ecmult_target(const secp256k1_scalar* target, int mode) { secp256k1_scalar n1, n2; secp256k1_ge p; secp256k1_gej pj, p1j, p2j, ptj; - static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); /* Generate random n1,n2 such that n1+n2 = -target. */ random_scalar_order_test(&n1); @@ -4390,9 +4410,9 @@ static void test_ecmult_target(const secp256k1_scalar* target, int mode) { secp256k1_ecmult_gen(&CTX->ecmult_gen_ctx, &p2j, &n2); secp256k1_ecmult_gen(&CTX->ecmult_gen_ctx, &ptj, target); } else if (mode == 1) { - secp256k1_ecmult(&p1j, &pj, &n1, &zero); - secp256k1_ecmult(&p2j, &pj, &n2, &zero); - secp256k1_ecmult(&ptj, &pj, target, &zero); + secp256k1_ecmult(&p1j, &pj, &n1, &secp256k1_scalar_zero); + secp256k1_ecmult(&p2j, &pj, &n2, &secp256k1_scalar_zero); + secp256k1_ecmult(&ptj, &pj, target, &secp256k1_scalar_zero); } else { secp256k1_ecmult_const(&p1j, &p, &n1); secp256k1_ecmult_const(&p2j, &p, &n2); @@ -4435,7 +4455,7 @@ static void run_point_times_order(void) { secp256k1_fe_sqr(&x, &x); } secp256k1_fe_normalize_var(&x); - CHECK(secp256k1_fe_equal_var(&x, &xr)); + CHECK(secp256k1_fe_equal(&x, &xr)); } static void ecmult_const_random_mult(void) { @@ -4487,19 +4507,17 @@ static void ecmult_const_commutativity(void) { } static void ecmult_const_mult_zero_one(void) { - secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); - secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); secp256k1_scalar negone; secp256k1_gej res1; secp256k1_ge res2; secp256k1_ge point; - secp256k1_scalar_negate(&negone, &one); + secp256k1_scalar_negate(&negone, &secp256k1_scalar_one); random_group_element_test(&point); - secp256k1_ecmult_const(&res1, &point, &zero); + secp256k1_ecmult_const(&res1, &point, &secp256k1_scalar_zero); secp256k1_ge_set_gej(&res2, &res1); CHECK(secp256k1_ge_is_infinity(&res2)); - secp256k1_ecmult_const(&res1, &point, &one); + secp256k1_ecmult_const(&res1, &point, &secp256k1_scalar_one); secp256k1_ge_set_gej(&res2, &res1); ge_equals_ge(&res2, &point); secp256k1_ecmult_const(&res1, &point, &negone); @@ -4854,7 +4872,7 @@ static int test_ecmult_multi_random(secp256k1_scratch *scratch) { * scalars[0..filled-1] and gejs[0..filled-1] are the scalars and points * which form its normal inputs. */ int filled = 0; - secp256k1_scalar g_scalar = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + secp256k1_scalar g_scalar = secp256k1_scalar_zero; secp256k1_scalar scalars[128]; secp256k1_gej gejs[128]; /* The expected result, and the computed result. */ @@ -5465,16 +5483,15 @@ static void test_ecmult_accumulate(secp256k1_sha256* acc, const secp256k1_scalar /* Compute x*G in 6 different ways, serialize it uncompressed, and feed it into acc. */ secp256k1_gej rj1, rj2, rj3, rj4, rj5, rj6, gj, infj; secp256k1_ge r; - const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); unsigned char bytes[65]; size_t size = 65; secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); secp256k1_gej_set_infinity(&infj); secp256k1_ecmult_gen(&CTX->ecmult_gen_ctx, &rj1, x); - secp256k1_ecmult(&rj2, &gj, x, &zero); - secp256k1_ecmult(&rj3, &infj, &zero, x); + secp256k1_ecmult(&rj2, &gj, x, &secp256k1_scalar_zero); + secp256k1_ecmult(&rj3, &infj, &secp256k1_scalar_zero, x); secp256k1_ecmult_multi_var(NULL, scratch, &rj4, x, NULL, NULL, 0); - secp256k1_ecmult_multi_var(NULL, scratch, &rj5, &zero, test_ecmult_accumulate_cb, (void*)x, 1); + secp256k1_ecmult_multi_var(NULL, scratch, &rj5, &secp256k1_scalar_zero, test_ecmult_accumulate_cb, (void*)x, 1); secp256k1_ecmult_const(&rj6, &secp256k1_ge_const_g, x); secp256k1_ge_set_gej_var(&r, &rj1); ge_equals_gej(&r, &rj2); @@ -7599,33 +7616,31 @@ static void fe_storage_cmov_test(void) { } static void scalar_cmov_test(void) { - static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); - static const secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); static const secp256k1_scalar max = SECP256K1_SCALAR_CONST( - 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, - 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, + 0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364140UL ); secp256k1_scalar r = max; - secp256k1_scalar a = zero; + secp256k1_scalar a = secp256k1_scalar_zero; secp256k1_scalar_cmov(&r, &a, 0); CHECK(secp256k1_memcmp_var(&r, &max, sizeof(r)) == 0); - r = zero; a = max; + r = secp256k1_scalar_zero; a = max; secp256k1_scalar_cmov(&r, &a, 1); CHECK(secp256k1_memcmp_var(&r, &max, sizeof(r)) == 0); - a = zero; + a = secp256k1_scalar_zero; secp256k1_scalar_cmov(&r, &a, 1); - CHECK(secp256k1_memcmp_var(&r, &zero, sizeof(r)) == 0); + CHECK(secp256k1_memcmp_var(&r, &secp256k1_scalar_zero, sizeof(r)) == 0); - a = one; + a = secp256k1_scalar_one; secp256k1_scalar_cmov(&r, &a, 1); - CHECK(secp256k1_memcmp_var(&r, &one, sizeof(r)) == 0); + CHECK(secp256k1_memcmp_var(&r, &secp256k1_scalar_one, sizeof(r)) == 0); - r = one; a = zero; + r = secp256k1_scalar_one; a = secp256k1_scalar_zero; secp256k1_scalar_cmov(&r, &a, 0); - CHECK(secp256k1_memcmp_var(&r, &one, sizeof(r)) == 0); + CHECK(secp256k1_memcmp_var(&r, &secp256k1_scalar_one, sizeof(r)) == 0); } static void ge_storage_cmov_test(void) { diff --git a/src/tests_exhaustive.c b/src/tests_exhaustive.c index dbb6b7eb46..3af8ec1ee5 100644 --- a/src/tests_exhaustive.c +++ b/src/tests_exhaustive.c @@ -38,8 +38,8 @@ static void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) { if (a->infinity) { return; } - CHECK(secp256k1_fe_equal_var(&a->x, &b->x)); - CHECK(secp256k1_fe_equal_var(&a->y, &b->y)); + CHECK(secp256k1_fe_equal(&a->x, &b->x)); + CHECK(secp256k1_fe_equal(&a->y, &b->y)); } static void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) { @@ -52,11 +52,11 @@ static void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) { /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */ secp256k1_fe_sqr(&z2s, &b->z); secp256k1_fe_mul(&u1, &a->x, &z2s); - u2 = b->x; secp256k1_fe_normalize_weak(&u2); + u2 = b->x; secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z); - s2 = b->y; secp256k1_fe_normalize_weak(&s2); - CHECK(secp256k1_fe_equal_var(&u1, &u2)); - CHECK(secp256k1_fe_equal_var(&s1, &s2)); + s2 = b->y; + CHECK(secp256k1_fe_equal(&u1, &u2)); + CHECK(secp256k1_fe_equal(&s1, &s2)); } static void random_fe(secp256k1_fe *x) { @@ -219,14 +219,14 @@ static void test_exhaustive_ecmult(const secp256k1_ge *group, const secp256k1_ge /* Test secp256k1_ecmult_const_xonly with all curve X coordinates, and xd=NULL. */ ret = secp256k1_ecmult_const_xonly(&tmpf, &group[i].x, NULL, &ng, 0); CHECK(ret); - CHECK(secp256k1_fe_equal_var(&tmpf, &group[(i * j) % EXHAUSTIVE_TEST_ORDER].x)); + CHECK(secp256k1_fe_equal(&tmpf, &group[(i * j) % EXHAUSTIVE_TEST_ORDER].x)); /* Test secp256k1_ecmult_const_xonly with all curve X coordinates, with random xd. */ random_fe_non_zero(&xd); secp256k1_fe_mul(&xn, &xd, &group[i].x); ret = secp256k1_ecmult_const_xonly(&tmpf, &xn, &xd, &ng, 0); CHECK(ret); - CHECK(secp256k1_fe_equal_var(&tmpf, &group[(i * j) % EXHAUSTIVE_TEST_ORDER].x)); + CHECK(secp256k1_fe_equal(&tmpf, &group[(i * j) % EXHAUSTIVE_TEST_ORDER].x)); } } } @@ -475,8 +475,8 @@ int main(int argc, char** argv) { CHECK(group[i].infinity == 0); CHECK(generated.infinity == 0); - CHECK(secp256k1_fe_equal_var(&generated.x, &group[i].x)); - CHECK(secp256k1_fe_equal_var(&generated.y, &group[i].y)); + CHECK(secp256k1_fe_equal(&generated.x, &group[i].x)); + CHECK(secp256k1_fe_equal(&generated.y, &group[i].y)); } } diff --git a/src/util.h b/src/util.h index 801ea0c885..cf7e5d1af5 100644 --- a/src/util.h +++ b/src/util.h @@ -152,14 +152,6 @@ static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_ return ret; } -static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void *ptr, size_t size) { - void *ret = realloc(ptr, size); - if (ret == NULL) { - secp256k1_callback_call(cb, "Out of memory"); - } - return ret; -} - #if defined(__BIGGEST_ALIGNMENT__) #define ALIGNMENT __BIGGEST_ALIGNMENT__ #else -- cgit v1.2.3