- src/java/guava/
env:
global:
- - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no STATICPRECOMPUTATION=yes ASM=no BUILD=check EXTRAFLAGS= HOST= ECDH=no RECOVERY=no EXPERIMENTAL=no JNI=no
+ - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no STATICPRECOMPUTATION=yes ECMULTGENPRECISION=auto ASM=no BUILD=check EXTRAFLAGS= HOST= ECDH=no RECOVERY=no EXPERIMENTAL=no JNI=no
- GUAVA_URL=https://search.maven.org/remotecontent?filepath=com/google/guava/guava/18.0/guava-18.0.jar GUAVA_JAR=src/java/guava/guava-18.0.jar
matrix:
- SCALAR=32bit RECOVERY=yes
- EXTRAFLAGS=CPPFLAGS=-DDETERMINISTIC
- EXTRAFLAGS=CFLAGS=-O0
- BUILD=check-java JNI=yes ECDH=yes EXPERIMENTAL=yes
+ - ECMULTGENPRECISION=2
+ - ECMULTGENPRECISION=8
matrix:
fast_finish: true
include:
script:
- if [ -n "$HOST" ]; then export USE_HOST="--host=$HOST"; fi
- if [ "x$HOST" = "xi686-linux-gnu" ]; then export CC="$CC -m32"; fi
- - ./configure --enable-experimental=$EXPERIMENTAL --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION --enable-module-ecdh=$ECDH --enable-module-recovery=$RECOVERY --enable-jni=$JNI $EXTRAFLAGS $USE_HOST && make -j2 $BUILD
+ - ./configure --enable-experimental=$EXPERIMENTAL --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION --with-ecmult-gen-precision=$ECMULTGENPRECISION --enable-module-ecdh=$ECDH --enable-module-recovery=$RECOVERY --enable-jni=$JNI $EXTRAFLAGS $USE_HOST && make -j2 $BUILD
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)
$ make
$ make check
$ sudo make install # optional
+
+Exhaustive tests
+-----------
+
+ $ ./exhaustive_tests
+
+With valgrind, you might need to increase the max stack size:
+
+ $ valgrind --max-stackframe=2500000 ./exhaustive_tests
)],
[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
;;
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
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"
#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
#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;
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;
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);
/* 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);
}
#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;
/* 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.
* 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"
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");
projects / secp256k1.git / commitdiff