diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml --- a/src/secp256k1/.travis.yml +++ b/src/secp256k1/.travis.yml @@ -20,6 +20,7 @@ - SCALAR=auto - ENDOMORPHISM=no - STATICPRECOMPUTATION=yes + - ECMULTGENPRECISION=auto - ASM=no - AUTOTOOLS_TARGET=check - CMAKE_TARGET=check-secp256k1 @@ -48,6 +49,8 @@ - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DDETERMINISTIC CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DDETERMINISTIC - AUTOTOOLS_EXTRA_FLAGS=CFLAGS=-O0 CMAKE_EXTRA_FLAGS=-DCMAKE_BUILD_TYPE=Debug - AUTOTOOLS_TARGET=check-java CMAKE_TARGET=check-secp256k1-java JNI=yes ECDH=yes EXPERIMENTAL=yes + - ECMULTGENPRECISION=2 + - ECMULTGENPRECISION=8 - SCHNORR=no jobs: fast_finish: true diff --git a/src/secp256k1/CMakeLists.txt b/src/secp256k1/CMakeLists.txt --- a/src/secp256k1/CMakeLists.txt +++ b/src/secp256k1/CMakeLists.txt @@ -210,18 +210,25 @@ # 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].") +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() + +set(SECP256K1_ECMULT_GEN_PRECISION 4 CACHE STRING "Precision bits to tune the precomputed table size for signing.") +set(VALID_PRECISIONS 2 4 8) +if(NOT ${SECP256K1_ECMULT_GEN_PRECISION} IN_LIST VALID_PRECISIONS) + message(FATAL_ERROR "SECP256K1_ECMULT_GEN_PRECISION not 2, 4, 8") +endif() # 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) - 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() include(NativeExecutable) native_add_cmake_flags( "-DSECP256K1_ECMULT_WINDOW_SIZE=${SECP256K1_ECMULT_WINDOW_SIZE}" + "-DSECP256K1_ECMULT_GEN_PRECISION=${SECP256K1_ECMULT_GEN_PRECISION}" ) add_native_executable(gen_context src/gen_context.c) diff --git a/src/secp256k1/Makefile.am b/src/secp256k1/Makefile.am --- a/src/secp256k1/Makefile.am +++ b/src/secp256k1/Makefile.am @@ -146,11 +146,11 @@ endif if USE_ECMULT_STATIC_PRECOMPUTATION -CPPFLAGS_FOR_BUILD +=-I$(top_srcdir) +CPPFLAGS_FOR_BUILD +=-I$(top_srcdir) -I$(builddir)/src gen_context_OBJECTS = gen_context.o gen_context_BIN = gen_context$(BUILD_EXEEXT) -gen_%.o: src/gen_%.c +gen_%.o: src/gen_%.c src/libsecp256k1-config.h $(CC_FOR_BUILD) $(CPPFLAGS_FOR_BUILD) $(CFLAGS_FOR_BUILD) -c $< -o $@ $(gen_context_BIN): $(gen_context_OBJECTS) diff --git a/src/secp256k1/README.md b/src/secp256k1/README.md --- a/src/secp256k1/README.md +++ b/src/secp256k1/README.md @@ -78,3 +78,12 @@ ninja check-secp256k1 sudo ninja install # optional ``` + +Exhaustive tests +----------- + + $ ./exhaustive_tests + +With valgrind, you might need to increase the max stack size: + + $ valgrind --max-stackframe=2500000 ./exhaustive_tests diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac --- a/src/secp256k1/configure.ac +++ b/src/secp256k1/configure.ac @@ -175,6 +175,14 @@ )], [req_ecmult_window=$withval], [req_ecmult_window=auto]) +AC_ARG_WITH([ecmult-gen-precision], [AS_HELP_STRING([--with-ecmult-gen-precision=2|4|8|auto], +[Precision bits to tune the precomputed table size for signing.] +[The size of the table is 32kB for 2 bits, 64kB for 4 bits, 512kB for 8 bits of precision.] +[A larger table size usually results in possible faster signing.] +["auto" is a reasonable setting for desktop machines (currently 4). [default=auto]] +)], +[req_ecmult_gen_precision=$withval], [req_ecmult_gen_precision=auto]) + AC_CHECK_TYPES([__int128]) if test x"$enable_coverage" = x"yes"; then @@ -433,6 +441,22 @@ ;; esac +#set ecmult gen precision +if test x"$req_ecmult_gen_precision" = x"auto"; then + set_ecmult_gen_precision=4 +else + set_ecmult_gen_precision=$req_ecmult_gen_precision +fi + +case $set_ecmult_gen_precision in +2|4|8) + AC_DEFINE_UNQUOTED(ECMULT_GEN_PREC_BITS, $set_ecmult_gen_precision, [Set ecmult gen precision bits]) + ;; +*) + AC_MSG_ERROR(['ecmult gen precision not 2, 4, 8 or "auto"']) + ;; +esac + if test x"$use_tests" = x"yes"; then SECP_OPENSSL_CHECK if test x"$has_openssl_ec" = x"yes"; then @@ -580,6 +604,7 @@ echo " field = $set_field" echo " scalar = $set_scalar" echo " ecmult window size = $set_ecmult_window" +echo " ecmult gen prec. bits = $set_ecmult_gen_precision" 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 @@ -24,6 +24,7 @@ #undef USE_SCALAR_8X32 #undef USE_SCALAR_INV_BUILTIN #undef USE_SCALAR_INV_NUM +#undef ECMULT_WINDOW_SIZE #define USE_NUM_NONE 1 #define USE_FIELD_INV_BUILTIN 1 diff --git a/src/secp256k1/src/ecmult_gen.h b/src/secp256k1/src/ecmult_gen.h --- a/src/secp256k1/src/ecmult_gen.h +++ b/src/secp256k1/src/ecmult_gen.h @@ -10,20 +10,27 @@ #include "scalar.h" #include "group.h" +#if ECMULT_GEN_PREC_BITS != 2 && ECMULT_GEN_PREC_BITS != 4 && ECMULT_GEN_PREC_BITS != 8 +# error "Set ECMULT_GEN_PREC_BITS to 2, 4 or 8." +#endif +#define ECMULT_GEN_PREC_B ECMULT_GEN_PREC_BITS +#define ECMULT_GEN_PREC_G (1 << ECMULT_GEN_PREC_B) +#define ECMULT_GEN_PREC_N (256 / ECMULT_GEN_PREC_B) + typedef struct { /* For accelerating the computation of a*G: * To harden against timing attacks, use the following mechanism: - * * Break up the multiplicand into groups of 4 bits, called n_0, n_1, n_2, ..., n_63. - * * Compute sum(n_i * 16^i * G + U_i, i=0..63), where: - * * U_i = U * 2^i (for i=0..62) - * * U_i = U * (1-2^63) (for i=63) - * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0..63) = 0. - * For each i, and each of the 16 possible values of n_i, (n_i * 16^i * G + U_i) is - * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0..63). + * * Break up the multiplicand into groups of PREC_B bits, called n_0, n_1, n_2, ..., n_(PREC_N-1). + * * Compute sum(n_i * (PREC_G)^i * G + U_i, i=0 ... PREC_N-1), where: + * * U_i = U * 2^i, for i=0 ... PREC_N-2 + * * U_i = U * (1-2^(PREC_N-1)), for i=PREC_N-1 + * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0 ... PREC_N-1) = 0. + * For each i, and each of the PREC_G possible values of n_i, (n_i * (PREC_G)^i * G + U_i) is + * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0 ... PREC_N-1). * None of the resulting prec group elements have a known scalar, and neither do any of * the intermediate sums while computing a*G. */ - secp256k1_ge_storage (*prec)[64][16]; /* prec[j][i] = 16^j * i * G + U_i */ + secp256k1_ge_storage (*prec)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G]; /* prec[j][i] = (PREC_G)^j * i * G + U_i */ secp256k1_scalar blind; secp256k1_gej initial; } secp256k1_ecmult_gen_context; diff --git a/src/secp256k1/src/ecmult_gen_impl.h b/src/secp256k1/src/ecmult_gen_impl.h --- a/src/secp256k1/src/ecmult_gen_impl.h +++ b/src/secp256k1/src/ecmult_gen_impl.h @@ -28,7 +28,7 @@ static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx, void **prealloc) { #ifndef USE_ECMULT_STATIC_PRECOMPUTATION - secp256k1_ge prec[1024]; + secp256k1_ge prec[ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G]; secp256k1_gej gj; secp256k1_gej nums_gej; int i, j; @@ -40,7 +40,7 @@ return; } #ifndef USE_ECMULT_STATIC_PRECOMPUTATION - ctx->prec = (secp256k1_ge_storage (*)[64][16])manual_alloc(prealloc, prealloc_size, base, prealloc_size); + ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])manual_alloc(prealloc, prealloc_size, base, prealloc_size); /* get the generator */ secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); @@ -64,39 +64,39 @@ /* compute prec. */ { - secp256k1_gej precj[1024]; /* Jacobian versions of prec. */ + secp256k1_gej precj[ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G]; /* Jacobian versions of prec. */ secp256k1_gej gbase; secp256k1_gej numsbase; - gbase = gj; /* 16^j * G */ + gbase = gj; /* PREC_G^j * G */ numsbase = nums_gej; /* 2^j * nums. */ - for (j = 0; j < 64; j++) { - /* Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase). */ - precj[j*16] = numsbase; - for (i = 1; i < 16; i++) { - secp256k1_gej_add_var(&precj[j*16 + i], &precj[j*16 + i - 1], &gbase, NULL); + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + /* Set precj[j*PREC_G .. j*PREC_G+(PREC_G-1)] to (numsbase, numsbase + gbase, ..., numsbase + (PREC_G-1)*gbase). */ + precj[j*ECMULT_GEN_PREC_G] = numsbase; + for (i = 1; i < ECMULT_GEN_PREC_G; i++) { + secp256k1_gej_add_var(&precj[j*ECMULT_GEN_PREC_G + i], &precj[j*ECMULT_GEN_PREC_G + i - 1], &gbase, NULL); } - /* Multiply gbase by 16. */ - for (i = 0; i < 4; i++) { + /* Multiply gbase by PREC_G. */ + for (i = 0; i < ECMULT_GEN_PREC_B; i++) { secp256k1_gej_double_var(&gbase, &gbase, NULL); } /* Multiply numbase by 2. */ secp256k1_gej_double_var(&numsbase, &numsbase, NULL); - if (j == 62) { + if (j == ECMULT_GEN_PREC_N - 2) { /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */ secp256k1_gej_neg(&numsbase, &numsbase); secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL); } } - secp256k1_ge_set_all_gej_var(prec, precj, 1024); + secp256k1_ge_set_all_gej_var(prec, precj, ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G); } - for (j = 0; j < 64; j++) { - for (i = 0; i < 16; i++) { - secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*16 + i]); + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + for (i = 0; i < ECMULT_GEN_PREC_G; i++) { + secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*ECMULT_GEN_PREC_G + i]); } } #else (void)prealloc; - ctx->prec = (secp256k1_ge_storage (*)[64][16])secp256k1_ecmult_static_context; + ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])secp256k1_ecmult_static_context; #endif secp256k1_ecmult_gen_blind(ctx, NULL); } @@ -109,7 +109,7 @@ #ifndef USE_ECMULT_STATIC_PRECOMPUTATION if (src->prec != NULL) { /* We cast to void* first to suppress a -Wcast-align warning. */ - dst->prec = (secp256k1_ge_storage (*)[64][16])(void*)((unsigned char*)dst + ((unsigned char*)src->prec - (unsigned char*)src)); + dst->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])(void*)((unsigned char*)dst + ((unsigned char*)src->prec - (unsigned char*)src)); } #else (void)dst, (void)src; @@ -133,9 +133,9 @@ /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */ secp256k1_scalar_add(&gnb, gn, &ctx->blind); add.infinity = 0; - for (j = 0; j < 64; j++) { - bits = secp256k1_scalar_get_bits(&gnb, j * 4, 4); - for (i = 0; i < 16; i++) { + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + bits = secp256k1_scalar_get_bits(&gnb, j * ECMULT_GEN_PREC_B, ECMULT_GEN_PREC_B); + for (i = 0; i < ECMULT_GEN_PREC_G; i++) { /** This uses a conditional move to avoid any secret data in array indexes. * _Any_ use of secret indexes has been demonstrated to result in timing * sidechannels, even when the cache-line access patterns are uniform. diff --git a/src/secp256k1/src/gen_context.c b/src/secp256k1/src/gen_context.c --- a/src/secp256k1/src/gen_context.c +++ b/src/secp256k1/src/gen_context.c @@ -4,9 +4,14 @@ * file COPYING or http://www.opensource.org/licenses/mit-license.php.* **********************************************************************/ +/* Autotools creates libsecp256k1-config.h, of which ECMULT_GEN_PREC_BITS is needed. */ +/* ifndef guard so downstream users can define their own if they do not use autotools. */ +#if !defined(ECMULT_GEN_PREC_BITS) +#include "libsecp256k1-config.h" +#endif #define USE_BASIC_CONFIG 1 - #include "basic-config.h" + #include "include/secp256k1.h" #include "util.h" #include "field_impl.h" @@ -45,23 +50,26 @@ fprintf(fp, "#define _SECP256K1_ECMULT_STATIC_CONTEXT_\n"); fprintf(fp, "#include \"src/group.h\"\n"); fprintf(fp, "#define SC SECP256K1_GE_STORAGE_CONST\n"); - fprintf(fp, "static const secp256k1_ge_storage secp256k1_ecmult_static_context[64][16] = {\n"); + fprintf(fp, "#if ECMULT_GEN_PREC_N != %d || ECMULT_GEN_PREC_G != %d\n", ECMULT_GEN_PREC_N, ECMULT_GEN_PREC_G); + fprintf(fp, " #error configuration mismatch, invalid ECMULT_GEN_PREC_N, ECMULT_GEN_PREC_G. Try deleting ecmult_static_context.h before the build.\n"); + fprintf(fp, "#endif\n"); + fprintf(fp, "static const secp256k1_ge_storage secp256k1_ecmult_static_context[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G] = {\n"); base = checked_malloc(&default_error_callback, SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE); prealloc = base; secp256k1_ecmult_gen_context_init(&ctx); secp256k1_ecmult_gen_context_build(&ctx, &prealloc); - for(outer = 0; outer != 64; outer++) { + for(outer = 0; outer != ECMULT_GEN_PREC_N; outer++) { fprintf(fp,"{\n"); - for(inner = 0; inner != 16; inner++) { + for(inner = 0; inner != ECMULT_GEN_PREC_G; inner++) { fprintf(fp," SC(%uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu)", SECP256K1_GE_STORAGE_CONST_GET((*ctx.prec)[outer][inner])); - if (inner != 15) { + if (inner != ECMULT_GEN_PREC_G - 1) { fprintf(fp,",\n"); } else { fprintf(fp,"\n"); } } - if (outer != 63) { + if (outer != ECMULT_GEN_PREC_N - 1) { fprintf(fp,"},\n"); } else { fprintf(fp,"}\n"); diff --git a/src/secp256k1/src/libsecp256k1-config.h.cmake.in b/src/secp256k1/src/libsecp256k1-config.h.cmake.in --- a/src/secp256k1/src/libsecp256k1-config.h.cmake.in +++ b/src/secp256k1/src/libsecp256k1-config.h.cmake.in @@ -26,6 +26,7 @@ #cmakedefine USE_ECMULT_STATIC_PRECOMPUTATION #define ECMULT_WINDOW_SIZE ${SECP256K1_ECMULT_WINDOW_SIZE} +#define ECMULT_GEN_PREC_BITS ${SECP256K1_ECMULT_GEN_PRECISION} #cmakedefine ENABLE_MODULE_ECDH #cmakedefine ENABLE_MODULE_MULTISET diff --git a/src/secp256k1/travis/build_autotools.sh b/src/secp256k1/travis/build_autotools.sh --- a/src/secp256k1/travis/build_autotools.sh +++ b/src/secp256k1/travis/build_autotools.sh @@ -25,6 +25,7 @@ --with-asm=$ASM \ --with-scalar=$SCALAR \ --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION \ + --with-ecmult-gen-precision=$ECMULTGENPRECISION \ --enable-module-ecdh=$ECDH \ --enable-module-recovery=$RECOVERY \ --enable-module-schnorr=$SCHNORR \ diff --git a/src/secp256k1/travis/build_cmake.sh b/src/secp256k1/travis/build_cmake.sh --- a/src/secp256k1/travis/build_cmake.sh +++ b/src/secp256k1/travis/build_cmake.sh @@ -18,6 +18,7 @@ ${CMAKE_COMMAND} -GNinja .. \ -DCMAKE_INSTALL_PREFIX=install \ -DSECP256K1_ECMULT_STATIC_PRECOMPUTATION=$STATICPRECOMPUTATION \ + -DSECP256K1_ECMULT_GEN_PRECISION=$ECMULTGENPRECISION \ -DSECP256K1_ENABLE_MODULE_ECDH=$ECDH \ -DSECP256K1_ENABLE_MODULE_RECOVERY=$RECOVERY \ -DSECP256K1_ENABLE_MODULE_SCHNORR=$SCHNORR \