diff --git a/src/secp256k1/CMakeLists.txt b/src/secp256k1/CMakeLists.txt --- a/src/secp256k1/CMakeLists.txt +++ b/src/secp256k1/CMakeLists.txt @@ -133,17 +133,21 @@ set(ENABLE_MODULE_SCHNORR 1) endif() +# Make the emult window size customizable. +set(SECP256K1_ECMULT_WINDOW_SIZE 15 CACHE STRING "Window size for ecmult precomputation for verification, specified as integer in range [2..24].") + # Static precomputation for elliptic curve multiplication option(SECP256K1_ECMULT_STATIC_PRECOMPUTATION "Precompute libsecp256k1's elliptic curve multiplication tables" ON) if(SECP256K1_ECMULT_STATIC_PRECOMPUTATION) set(USE_ECMULT_STATIC_PRECOMPUTATION 1) - set(SECP256K1_ECMULT_WINDOW_SIZE 15 CACHE STRING "Window size for ecmult precomputation for verification, specified as integer in range [2..24].") if(${SECP256K1_ECMULT_WINDOW_SIZE} LESS 2 OR ${SECP256K1_ECMULT_WINDOW_SIZE} GREATER 24) message(FATAL_ERROR "SECP256K1_ECMULT_WINDOW_SIZE must be an integer in range [2..24]") endif() - # FIXME: Propagate SECP256K1_ECMULT_WINDOW_SIZE include(NativeExecutable) + native_add_cmake_flags( + "-DSECP256K1_ECMULT_WINDOW_SIZE=${SECP256K1_ECMULT_WINDOW_SIZE}" + ) add_native_executable(gen_context src/gen_context.c) add_custom_command( diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac --- a/src/secp256k1/configure.ac +++ b/src/secp256k1/configure.ac @@ -85,42 +85,42 @@ ]) AC_ARG_ENABLE(benchmark, - AS_HELP_STRING([--enable-benchmark],[compile benchmark (default is yes)]), + AS_HELP_STRING([--enable-benchmark],[compile benchmark [default=yes]]), [use_benchmark=$enableval], [use_benchmark=yes]) AC_ARG_ENABLE(coverage, - AS_HELP_STRING([--enable-coverage],[enable compiler flags to support kcov coverage analysis]), + AS_HELP_STRING([--enable-coverage],[enable compiler flags to support kcov coverage analysis [default=no]]), [enable_coverage=$enableval], [enable_coverage=no]) AC_ARG_ENABLE(tests, - AS_HELP_STRING([--enable-tests],[compile tests (default is yes)]), + AS_HELP_STRING([--enable-tests],[compile tests [default=yes]]), [use_tests=$enableval], [use_tests=yes]) AC_ARG_ENABLE(openssl_tests, - AS_HELP_STRING([--enable-openssl-tests],[enable OpenSSL tests, if OpenSSL is available (default is auto)]), + AS_HELP_STRING([--enable-openssl-tests],[enable OpenSSL tests [default=auto]]), [enable_openssl_tests=$enableval], [enable_openssl_tests=auto]) AC_ARG_ENABLE(experimental, - AS_HELP_STRING([--enable-experimental],[allow experimental configure options (default is no)]), + AS_HELP_STRING([--enable-experimental],[allow experimental configure options [default=no]]), [use_experimental=$enableval], [use_experimental=no]) AC_ARG_ENABLE(exhaustive_tests, - AS_HELP_STRING([--enable-exhaustive-tests],[compile exhaustive tests (default is yes)]), + AS_HELP_STRING([--enable-exhaustive-tests],[compile exhaustive tests [default=yes]]), [use_exhaustive_tests=$enableval], [use_exhaustive_tests=yes]) AC_ARG_ENABLE(endomorphism, - AS_HELP_STRING([--enable-endomorphism],[enable endomorphism (default is no)]), + AS_HELP_STRING([--enable-endomorphism],[enable endomorphism [default=no]]), [use_endomorphism=$enableval], [use_endomorphism=no]) AC_ARG_ENABLE(ecmult_static_precomputation, - AS_HELP_STRING([--enable-ecmult-static-precomputation],[enable precomputed ecmult table for signing (default is yes)]), + AS_HELP_STRING([--enable-ecmult-static-precomputation],[enable precomputed ecmult table for signing [default=auto]]), [use_ecmult_static_precomputation=$enableval], [use_ecmult_static_precomputation=auto]) @@ -135,31 +135,40 @@ [enable_module_multiset=no]) AC_ARG_ENABLE(module_recovery, - AS_HELP_STRING([--enable-module-recovery],[enable ECDSA pubkey recovery module (default is no)]), + AS_HELP_STRING([--enable-module-recovery],[enable ECDSA pubkey recovery module [default=no]]), [enable_module_recovery=$enableval], [enable_module_recovery=no]) AC_ARG_ENABLE(module_schnorr, - AS_HELP_STRING([--enable-module-schnorr],[enable Schnorr signatures module (default is yes)]), + AS_HELP_STRING([--enable-module-schnorr],[enable Schnorr signatures module [default=yes]]), [enable_module_schnorr=$enableval], [enable_module_schnorr=yes]) AC_ARG_ENABLE(jni, - AS_HELP_STRING([--enable-jni],[enable libsecp256k1_jni (default is no)]), + AS_HELP_STRING([--enable-jni],[enable libsecp256k1_jni [default=no]]), [use_jni=$enableval], [use_jni=no]) AC_ARG_WITH([field], [AS_HELP_STRING([--with-field=64bit|32bit|auto], -[Specify Field Implementation. Default is auto])],[req_field=$withval], [req_field=auto]) +[finite field implementation to use [default=auto]])],[req_field=$withval], [req_field=auto]) AC_ARG_WITH([bignum], [AS_HELP_STRING([--with-bignum=gmp|no|auto], -[Specify Bignum Implementation. Default is auto])],[req_bignum=$withval], [req_bignum=auto]) +[bignum implementation to use [default=auto]])],[req_bignum=$withval], [req_bignum=auto]) AC_ARG_WITH([scalar], [AS_HELP_STRING([--with-scalar=64bit|32bit|auto], -[Specify scalar implementation. Default is auto])],[req_scalar=$withval], [req_scalar=auto]) +[scalar implementation to use [default=auto]])],[req_scalar=$withval], [req_scalar=auto]) -AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|arm|no|auto] -[Specify assembly optimizations to use. Default is auto (experimental: arm)])],[req_asm=$withval], [req_asm=auto]) +AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|arm|no|auto], +[assembly optimizations to use (experimental: arm) [default=auto]])],[req_asm=$withval], [req_asm=auto]) + +AC_ARG_WITH([ecmult-window], [AS_HELP_STRING([--with-ecmult-window=SIZE|auto], +[window size for ecmult precomputation for verification, specified as integer in range [2..24].] +[Larger values result in possibly better performance at the cost of an exponentially larger precomputed table.] +[The table will store 2^(SIZE-2) * 64 bytes of data but can be larger in memory due to platform-specific padding and alignment.] +[If the endomorphism optimization is enabled, two tables of this size are used instead of only one.] +["auto" is a reasonable setting for desktop machines (currently 15). [default=auto]] +)], +[req_ecmult_window=$withval], [req_ecmult_window=auto]) AC_CHECK_TYPES([__int128]) @@ -397,6 +406,28 @@ ;; esac +#set ecmult window size +if test x"$req_ecmult_window" = x"auto"; then + set_ecmult_window=15 +else + set_ecmult_window=$req_ecmult_window +fi + +error_window_size=['window size for ecmult precomputation not an integer in range [2..24] or "auto"'] +case $set_ecmult_window in +''|*[[!0-9]]*) + # no valid integer + AC_MSG_ERROR($error_window_size) + ;; +*) + if test "$set_ecmult_window" -lt 2 -o "$set_ecmult_window" -gt 24 ; then + # not in range + AC_MSG_ERROR($error_window_size) + fi + AC_DEFINE_UNQUOTED(ECMULT_WINDOW_SIZE, $set_ecmult_window, [Set window size for ecmult precomputation]) + ;; +esac + if test x"$use_tests" = x"yes"; then SECP_OPENSSL_CHECK if test x"$has_openssl_ec" = x"yes"; then @@ -538,6 +569,7 @@ echo " bignum = $set_bignum" echo " field = $set_field" echo " scalar = $set_scalar" +echo " ecmult window size = $set_ecmult_window" echo echo " CC = $CC" echo " CFLAGS = $CFLAGS" diff --git a/src/secp256k1/src/basic-config.h b/src/secp256k1/src/basic-config.h --- a/src/secp256k1/src/basic-config.h +++ b/src/secp256k1/src/basic-config.h @@ -28,6 +28,7 @@ #define USE_SCALAR_INV_BUILTIN 1 #define USE_FIELD_10X26 1 #define USE_SCALAR_8X32 1 +#define ECMULT_WINDOW_SIZE 15 #endif /* USE_BASIC_CONFIG */ diff --git a/src/secp256k1/src/ecmult_impl.h b/src/secp256k1/src/ecmult_impl.h --- a/src/secp256k1/src/ecmult_impl.h +++ b/src/secp256k1/src/ecmult_impl.h @@ -30,16 +30,32 @@ # endif #else /* optimal for 128-bit and 256-bit exponents. */ -#define WINDOW_A 5 -/** larger numbers may result in slightly better performance, at the cost of - exponentially larger precomputed tables. */ -#ifdef USE_ENDOMORPHISM -/** Two tables for window size 15: 1.375 MiB. */ -#define WINDOW_G 15 -#else -/** One table for window size 16: 1.375 MiB. */ -#define WINDOW_G 16 +# define WINDOW_A 5 +/** Larger values for ECMULT_WINDOW_SIZE result in possibly better + * performance at the cost of an exponentially larger precomputed + * table. The exact table size is + * (1 << (WINDOW_G - 2)) * sizeof(secp256k1_ge_storage) bytes, + * where sizeof(secp256k1_ge_storage) is typically 64 bytes but can + * be larger due to platform-specific padding and alignment. + * If the endomorphism optimization is enabled (USE_ENDOMORMPHSIM) + * two tables of this size are used instead of only one. + */ +# define WINDOW_G ECMULT_WINDOW_SIZE #endif + +/* Noone will ever need more than a window size of 24. The code might + * be correct for larger values of ECMULT_WINDOW_SIZE but this is not + * tested. + * + * The following limitations are known, and there are probably more: + * If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect + * because the size of the memory object that we allocate (in bytes) + * will not fit in a size_t. + * If WINDOW_G > 31 and int has 32 bits, then the code is incorrect + * because certain expressions will overflow. + */ +#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24 +# error Set ECMULT_WINDOW_SIZE to an integer in range [2..24]. #endif #ifdef USE_ENDOMORPHISM @@ -311,7 +327,12 @@ /* get the generator */ secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); - ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)); + { + size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); + /* check for overflow */ + VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); + ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); + } /* precompute the tables with odd multiples */ secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj); @@ -321,7 +342,10 @@ secp256k1_gej g_128j; int i; - ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)); + size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G)); + /* check for overflow */ + VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); + ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); /* calculate 2^128*generator */ g_128j = gj; @@ -338,7 +362,7 @@ if (src->pre_g == NULL) { dst->pre_g = NULL; } else { - size_t size = sizeof((*dst->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G); + size_t size = sizeof((*dst->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); dst->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); memcpy(dst->pre_g, src->pre_g, size); } @@ -346,7 +370,7 @@ if (src->pre_g_128 == NULL) { dst->pre_g_128 = NULL; } else { - size_t size = sizeof((*dst->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G); + size_t size = sizeof((*dst->pre_g_128)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); dst->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); memcpy(dst->pre_g_128, src->pre_g_128, size); }