diff options
author | MarcoFalke <falke.marco@gmail.com> | 2016-12-13 12:37:40 +0100 |
---|---|---|
committer | MarcoFalke <falke.marco@gmail.com> | 2016-12-13 12:37:40 +0100 |
commit | 64dfdde0aa7f7ef24e6cbf3c57e6d24efc55367e (patch) | |
tree | 8a1dfe59fe37e649e6c687386318cf6f2194f199 /src/ecmult_const_impl.h | |
parent | 5ad54630935d1f340666de7bc9ffef9b8a1df296 (diff) | |
download | bitcoin-64dfdde0aa7f7ef24e6cbf3c57e6d24efc55367e.tar.xz |
Squashed 'src/secp256k1/' changes from 6c527ec..8225239
8225239 Merge #433: Make the libcrypto detection fail the newer API.
12de863 Make the libcrypto detection fail the newer API.
2928420 Merge #427: Remove Schnorr from travis as well
8eecc4a Remove Schnorr from travis as well
a8abae7 Merge #310: Add exhaustive test for group functions on a low-order subgroup
b4ceedf Add exhaustive test for verification
83836a9 Add exhaustive tests for group arithmetic, signing, and ecmult on a small group
20b8877 Add exhaustive test for group functions on a low-order subgroup
80773a6 Merge #425: Remove Schnorr experiment
e06e878 Remove Schnorr experiment
04c8ef3 Merge #407: Modify parameter order of internal functions to match API parameter order
6e06696 Merge #411: Remove guarantees about memcmp-ability
40c8d7e Merge #421: Update scalar_4x64_impl.h
a922365 Merge #422: Restructure nonce clearing
3769783 Restructure nonce clearing
0f9e69d Restructure nonce clearing
9d67afa Update scalar_4x64_impl.h
7d15cd7 Merge #413: fix auto-enabled static precompuatation
00c5d2e fix auto-enabled static precompuatation
91219a1 Remove guarantees about memcmp-ability
7a49cac Merge #410: Add string.h include to ecmult_impl
0bbd5d4 Add string.h include to ecmult_impl
353c1bf Fix secp256k1_ge_set_table_gej_var parameter order
541b783 Fix secp256k1_ge_set_all_gej_var parameter order
7d893f4 Fix secp256k1_fe_inv_all_var parameter order
c5b32e1 Merge #405: Make secp256k1_fe_sqrt constant time
926836a Make secp256k1_fe_sqrt constant time
e2a8e92 Merge #404: Replace 3M + 4S doubling formula with 2M + 5S one
8ec49d8 Add note about 2M + 5S doubling formula
5a91bd7 Merge #400: A couple minor cleanups
ac01378 build: add -DSECP256K1_BUILD to benchmark_internal build flags
a6c6f99 Remove a bunch of unused stdlib #includes
65285a6 Merge #403: configure: add flag to disable OpenSSL tests
a9b2a5d configure: add flag to disable OpenSSL tests
b340123 Merge #402: Add support for testing quadratic residues
e6e9805 Add function for testing quadratic residue field/group elements.
efd953a Add Jacobi symbol test via GMP
fa36a0d Merge #401: ecmult_const: unify endomorphism and non-endomorphism skew cases
c6191fd ecmult_const: unify endomorphism and non-endomorphism skew cases
0b3e618 Merge #378: .gitignore build-aux cleanup
6042217 Merge #384: JNI: align shared files copyright/comments to bitcoinj's
24ad20f Merge #399: build: verify that the native compiler works for static precomp
b3be852 Merge #398: Test whether ECDH and Schnorr are enabled for JNI
aa0b1fd build: verify that the native compiler works for static precomp
eee808d Test whether ECDH and Schnorr are enabled for JNI
7b0fb18 Merge #366: ARM assembly implementation of field_10x26 inner (rebase of #173)
001f176 ARM assembly implementation of field_10x26 inner
0172be9 Merge #397: Small fixes for sha256
3f8b78e Fix undefs in hash_impl.h
2ab4695 Fix state size in sha256 struct
6875b01 Merge #386: Add some missing `VERIFY_CHECK(ctx != NULL)`
2c52b5d Merge #389: Cast pointers through uintptr_t under JNI
43097a4 Merge #390: Update bitcoin-core GitHub links
31c9c12 Merge #391: JNI: Only call ecdsa_verify if its inputs parsed correctly
1cb2302 Merge #392: Add testcase which hits additional branch in secp256k1_scalar_sqr
d2ee340 Merge #388: bench_ecdh: fix call to secp256k1_context_create
093a497 Add testcase which hits additional branch in secp256k1_scalar_sqr
a40c701 JNI: Only call ecdsa_verify if its inputs parsed correctly
faa2a11 Update bitcoin-core GitHub links
47b9e78 Cast pointers through uintptr_t under JNI
f36f9c6 bench_ecdh: fix call to secp256k1_context_create
bcc4881 Add some missing `VERIFY_CHECK(ctx != NULL)` for functions that use `ARG_CHECK`
6ceea2c align shared files copyright/comments to bitcoinj's
70141a8 Update .gitignore
7b549b1 Merge #373: build: fix x86_64 asm detection for some compilers
bc7c93c Merge #374: Add note about y=0 being possible on one of the sextic twists
e457018 Merge #364: JNI rebased
86e2d07 JNI library: cleanup, removed unimplemented code
3093576a JNI library
bd2895f Merge pull request #371
e72e93a Add note about y=0 being possible on one of the sextic twists
3f8fdfb build: fix x86_64 asm detection for some compilers
e5a9047 [Trivial] Remove double semicolons
c18b869 Merge pull request #360
3026daa Merge pull request #302
03d4611 Add sage verification script for the group laws
a965937 Merge pull request #361
83221ec Add experimental features to configure
5d4c5a3 Prevent damage_array in the signature test from going out of bounds.
419bf7f Merge pull request #356
03d84a4 Benchmark against OpenSSL verification
git-subtree-dir: src/secp256k1
git-subtree-split: 8225239f490f79842a5a3b82ad6cc8aa11d5208e
Diffstat (limited to 'src/ecmult_const_impl.h')
-rw-r--r-- | src/ecmult_const_impl.h | 69 |
1 files changed, 24 insertions, 45 deletions
diff --git a/src/ecmult_const_impl.h b/src/ecmult_const_impl.h index 90ac94770e..0db314c48e 100644 --- a/src/ecmult_const_impl.h +++ b/src/ecmult_const_impl.h @@ -58,25 +58,27 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w) { int global_sign; int skew = 0; int word = 0; + /* 1 2 3 */ int u_last; int u; -#ifdef USE_ENDOMORPHISM int flip; int bit; secp256k1_scalar neg_s; int not_neg_one; - /* If we are using the endomorphism, we cannot handle even numbers by negating - * them, since we are working with 128-bit numbers whose negations would be 256 - * bits, eliminating the performance advantage. Instead we use a technique from + /* Note that we cannot handle even numbers by negating them to be odd, as is + * done in other implementations, since if our scalars were specified to have + * width < 256 for performance reasons, their negations would have width 256 + * and we'd lose any performance benefit. Instead, we use a technique from * Section 4.2 of the Okeya/Tagaki paper, which is to add either 1 (for even) - * or 2 (for odd) to the number we are encoding, then compensating after the - * multiplication. */ - /* Negative 128-bit numbers will be negated, since otherwise they are 256-bit */ + * or 2 (for odd) to the number we are encoding, returning a skew value indicating + * this, and having the caller compensate after doing the multiplication. */ + + /* Negative numbers will be negated to keep their bit representation below the maximum width */ flip = secp256k1_scalar_is_high(&s); /* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */ - bit = flip ^ (s.d[0] & 1); + bit = flip ^ !secp256k1_scalar_is_even(&s); /* We check for negative one, since adding 2 to it will cause an overflow */ secp256k1_scalar_negate(&neg_s, &s); not_neg_one = !secp256k1_scalar_is_one(&neg_s); @@ -89,11 +91,6 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w) { global_sign = secp256k1_scalar_cond_negate(&s, flip); global_sign *= not_neg_one * 2 - 1; skew = 1 << bit; -#else - /* Otherwise, we just negate to force oddness */ - int is_even = secp256k1_scalar_is_even(&s); - global_sign = secp256k1_scalar_cond_negate(&s, is_even); -#endif /* 4 */ u_last = secp256k1_scalar_shr_int(&s, w); @@ -127,15 +124,13 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons secp256k1_ge tmpa; secp256k1_fe Z; + int skew_1; + int wnaf_1[1 + WNAF_SIZE(WINDOW_A - 1)]; #ifdef USE_ENDOMORPHISM secp256k1_ge pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)]; - int wnaf_1[1 + WNAF_SIZE(WINDOW_A - 1)]; int wnaf_lam[1 + WNAF_SIZE(WINDOW_A - 1)]; - int skew_1; int skew_lam; secp256k1_scalar q_1, q_lam; -#else - int wnaf[1 + WNAF_SIZE(WINDOW_A - 1)]; #endif int i; @@ -145,18 +140,10 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons #ifdef USE_ENDOMORPHISM /* split q into q_1 and q_lam (where q = q_1 + q_lam*lambda, and q_1 and q_lam are ~128 bit) */ secp256k1_scalar_split_lambda(&q_1, &q_lam, &sc); - /* no need for zero correction when using endomorphism since even - * numbers have one added to them anyway */ skew_1 = secp256k1_wnaf_const(wnaf_1, q_1, WINDOW_A - 1); skew_lam = secp256k1_wnaf_const(wnaf_lam, q_lam, WINDOW_A - 1); #else - int is_zero = secp256k1_scalar_is_zero(scalar); - /* the wNAF ladder cannot handle zero, so bump this to one .. we will - * correct the result after the fact */ - sc.d[0] += is_zero; - VERIFY_CHECK(!secp256k1_scalar_is_zero(&sc)); - - secp256k1_wnaf_const(wnaf, sc, WINDOW_A - 1); + skew_1 = secp256k1_wnaf_const(wnaf_1, sc, WINDOW_A - 1); #endif /* Calculate odd multiples of a. @@ -179,21 +166,15 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons /* first loop iteration (separated out so we can directly set r, rather * than having it start at infinity, get doubled several times, then have * its new value added to it) */ -#ifdef USE_ENDOMORPHISM i = wnaf_1[WNAF_SIZE(WINDOW_A - 1)]; VERIFY_CHECK(i != 0); ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, i, WINDOW_A); secp256k1_gej_set_ge(r, &tmpa); - +#ifdef USE_ENDOMORPHISM i = wnaf_lam[WNAF_SIZE(WINDOW_A - 1)]; VERIFY_CHECK(i != 0); ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, i, WINDOW_A); secp256k1_gej_add_ge(r, r, &tmpa); -#else - i = wnaf[WNAF_SIZE(WINDOW_A - 1)]; - VERIFY_CHECK(i != 0); - ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, i, WINDOW_A); - secp256k1_gej_set_ge(r, &tmpa); #endif /* remaining loop iterations */ for (i = WNAF_SIZE(WINDOW_A - 1) - 1; i >= 0; i--) { @@ -202,59 +183,57 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons for (j = 0; j < WINDOW_A - 1; ++j) { secp256k1_gej_double_nonzero(r, r, NULL); } -#ifdef USE_ENDOMORPHISM + n = wnaf_1[i]; ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A); VERIFY_CHECK(n != 0); secp256k1_gej_add_ge(r, r, &tmpa); - +#ifdef USE_ENDOMORPHISM n = wnaf_lam[i]; ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, n, WINDOW_A); VERIFY_CHECK(n != 0); secp256k1_gej_add_ge(r, r, &tmpa); -#else - n = wnaf[i]; - VERIFY_CHECK(n != 0); - ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A); - secp256k1_gej_add_ge(r, r, &tmpa); #endif } secp256k1_fe_mul(&r->z, &r->z, &Z); -#ifdef USE_ENDOMORPHISM { /* Correct for wNAF skew */ secp256k1_ge correction = *a; secp256k1_ge_storage correction_1_stor; +#ifdef USE_ENDOMORPHISM secp256k1_ge_storage correction_lam_stor; +#endif secp256k1_ge_storage a2_stor; secp256k1_gej tmpj; secp256k1_gej_set_ge(&tmpj, &correction); secp256k1_gej_double_var(&tmpj, &tmpj, NULL); secp256k1_ge_set_gej(&correction, &tmpj); secp256k1_ge_to_storage(&correction_1_stor, a); +#ifdef USE_ENDOMORPHISM secp256k1_ge_to_storage(&correction_lam_stor, a); +#endif secp256k1_ge_to_storage(&a2_stor, &correction); /* For odd numbers this is 2a (so replace it), for even ones a (so no-op) */ secp256k1_ge_storage_cmov(&correction_1_stor, &a2_stor, skew_1 == 2); +#ifdef USE_ENDOMORPHISM secp256k1_ge_storage_cmov(&correction_lam_stor, &a2_stor, skew_lam == 2); +#endif /* Apply the correction */ secp256k1_ge_from_storage(&correction, &correction_1_stor); secp256k1_ge_neg(&correction, &correction); secp256k1_gej_add_ge(r, r, &correction); +#ifdef USE_ENDOMORPHISM secp256k1_ge_from_storage(&correction, &correction_lam_stor); secp256k1_ge_neg(&correction, &correction); secp256k1_ge_mul_lambda(&correction, &correction); secp256k1_gej_add_ge(r, r, &correction); - } -#else - /* correct for zero */ - r->infinity |= is_zero; #endif + } } #endif |