Squashed 'src/secp256k1/' changes from 22f60a6..2bfb82b

2bfb82b Merge pull request #351
06aeea5 Turn secp256k1_ec_pubkey_serialize outlen to in/out
970164d Merge pull request #348
6466625 Improvements for coordinate decompression
e2100ad Merge pull request #347
8e48787 Change secp256k1_ec_pubkey_combine's count argument to size_t.
c69dea0 Clear output in more cases for pubkey_combine, adds tests.
269d422 Comment copyediting.
b4d17da Merge pull request #344
4709265 Merge pull request #345
26abce7 Adds 32 static test vectors for scalar mul, sqr, inv.
5b71a3f Better error case handling for pubkey_create & pubkey_serialize, more tests.
3b7bc69 Merge pull request #343
eed87af Change contrib/laxder from headers-only to files compilable as standalone C
d7eb1ae Merge pull request #342
7914a6e Make lax_der_privatekey_parsing.h not depend on internal code
73f64ff Merge pull request #339
9234391 Overhaul flags handling
1a36898 Make flags more explicit, add runtime checks.
1a3e03a Merge pull request #340
96be204 Add additional tests for eckey and arg-checks.
bb5aa4d Make the tweak function zeroize-output-on-fail behavior consistent.
4a243da Move secp256k1_ec_privkey_import/export to contrib.
1b3efc1 Move secp256k1_ecdsa_sig_recover into the recovery module.
e3cd679 Eliminate all side-effects from VERIFY_CHECK() usage.
b30fc85 Avoid nonce_function_rfc6979 algo16 argument emulation.
70d4640 Make secp256k1_ec_pubkey_create skip processing invalid secret keys.
6c476a8 Minor comment improvements.
131afe5 Merge pull request #334
0c6ab2f Introduce explicit lower-S normalization
fea19e7 Add contrib/lax_der_parsing.h
3bb9c44 Rewrite ECDSA signature parsing code
fa57f1b Use secp256k1_rand_int and secp256k1_rand_bits more
49b3749 Add new tests for the extra testrand functions
f684d7d Faster secp256k1_rand_int implementation
251b1a6 Improve testrand: add extra random functions
31994c8 Merge pull request #338
f79aa88 Bugfix: swap arguments to noncefp
c98df26 Merge pull request #319
67f7da4 Extensive interface and operations tests for secp256k1_ec_pubkey_parse.
ee2cb40 Add ARG_CHECKs to secp256k1_ec_pubkey_parse/secp256k1_ec_pubkey_serialize
7450ef1 Merge pull request #328
68a3c76 Merge pull request #329
98135ee Merge pull request #332
37100d7 improve ECDH header-doc
b13d749 Fix couple of typos in API comments
7c823e3 travis: fixup module configs
cc3141a Merge pull request #325
ee58fae Merge pull request #326
213aa67 Do not force benchmarks to be statically linked.
338fc8b Add API exports to secp256k1_nonce_function_default and secp256k1_nonce_function_rfc6979.
52fd03f Merge pull request #320
9f6993f Remove some dead code.
357f8cd Merge pull request #314
118cd82 Use explicit symbol visibility.
4e64608 Include public module headers when compiling modules.
1f41437 Merge pull request #316
fe0d463 Merge pull request #317
cfe0ed9 Fix miscellaneous style nits that irritate overactive static analysis.
2b199de Use the explicit NULL macro for pointer comparisons.
9e90516 Merge pull request #294
dd891e0 Get rid of _t as it is POSIX reserved
201819b Merge pull request #313
912f203 Eliminate a few unbraced statements that crept into the code.
eeab823 Merge pull request #299
486b9bb Use a flags bitfield for compressed option to secp256k1_ec_pubkey_serialize and secp256k1_ec_privkey_export
05732c5 Callback data: Accept pointers to either const or non-const data
1973c73 Bugfix: Reinitialise buffer lengths that have been used as outputs
788038d Use size_t for lengths (at least in external API)
c9d7c2a secp256k1_context_set_{error,illegal}_callback: Restore default handler by passing NULL as function argument
9aac008 secp256k1_context_destroy: Allow NULL argument as a no-op
64b730b secp256k1_context_create: Use unsigned type for flags bitfield
cb04ab5 Merge pull request #309
a551669 Merge pull request #295
81e45ff Update group_impl.h
85e3a2c Merge pull request #112
b2eb63b Merge pull request #293
dc0ce9f [API BREAK] Change argument order to out/outin/in
6d947ca Merge pull request #298
c822693 Merge pull request #301
6d04350 Merge pull request #303
7ab311c Merge pull request #304
5fb3229 Fixes a bug where bench_sign would fail due to passing in too small a buffer.
263dcbc remove unused assignment
b183b41 bugfix: "ARG_CHECK(ctx != NULL)" makes no sense
6da1446 build: fix parallel build
5eb4356 Merge pull request #291
c996d53 Print success
9f443be Move pubkey recovery code to separate module
d49abbd Separate ECDSA recovery tests
439d34a Separate recoverable and normal signatures
a7b046e Merge pull request #289
f66907f Improve/reformat API documentation secp256k1.h
2f77487 Add context building benchmarks
cc623d5 Merge pull request #287
de7e398 small typo fix
9d96e36 Merge pull request #280
432e1ce Merge pull request #283
14727fd Use correct name in gitignore
356b0e9 Actually test static precomputation in Travis
ff3a5df Merge pull request #284
2587208 Merge pull request #212
a5a66c7 Add support for custom EC-Schnorr-SHA256 signatures
d84a378 Merge pull request #252
72ae443 Improve perf. of cmov-based table lookup
92e53fc Implement endomorphism optimization for secp256k1_ecmult_const
ed35d43 Make `secp256k1_scalar_add_bit` conditional; make `secp256k1_scalar_split_lambda_var` constant time
91c0ce9 Add benchmarks for ECDH and const-time multiplication
0739bbb Add ECDH module which works by hashing the output of ecmult_const
4401500 Add constant-time multiply `secp256k1_ecmult_const` for ECDH
e4ce393 build: fix hard-coded usage of "gen_context"
b8e39ac build: don't use BUILT_SOURCES for the static context header
baa75da tests: add a couple tests
ae4f0c6 Merge pull request #278
995c548 Introduce callback functions for dealing with errors.
c333074 Merge pull request #282
18c329c Remove the internal secp256k1_ecdsa_sig_t type
74a2acd Add a secp256k1_ecdsa_signature_t type
23cfa91 Introduce secp256k1_pubkey_t type
4c63780 Merge pull request #269
3e6f1e2 Change rfc6979 implementation to be a generic PRNG
ed5334a Update configure.ac to make it build on OpenBSD
1b68366 Merge pull request #274
a83bb48 Make ecmult static precomputation default
166b32f Merge pull request #276
c37812f Add gen_context src/ecmult_static_context.h to CLEANFILES to fix distclean.
125c15d Merge pull request #275
76f6769 Fix build with static ecmult altroot and make dist.
5133f78 Merge pull request #254
b0a60e6 Merge pull request #258
733c1e6 Add travis build to test the static context.
fbecc38 Add ability to use a statically generated ecmult context.
4fb174d Merge pull request #263
4ab8990 Merge pull request #270
bdf0e0c Merge pull request #271
31d0c1f Merge pull request #273
eb2c8ff Add missing casts to SECP256K1_FE_CONST_INNER
55399c2 Further performance improvements to _ecmult_wnaf
99fd963 Add secp256k1_ec_pubkey_compress(), with test similar to the related decompress() function.
145cc6e Improve performance of _ecmult_wnaf
36b305a Verify the result of GMP modular inverse using non-GMP code
0cbc860 Merge pull request #266
06ff7fe Merge pull request #267
5a43124 Save 1 _fe_negate since s1 == -s2
a5d796e Update code comments
3f3964e Add specific VERIFY tests for _fe_cmov
7d054cd Refactor to save a _fe_negate
b28d02a Refactor to remove a local var
55e7fc3 Perf. improvement in _gej_add_ge
a0601cd Fix VERIFY calculations in _fe_cmov methods
17f7148 Merge pull request #261
7657420 Add tests for adding P+Q with P.x!=Q.x and P.y=-Q.y
8c5d5f7 tests: Add failing unit test for #257 (bad addition formula)
5de4c5d gej_add_ge: fix degenerate case when computing P + (-lambda)P
bcf2fcf gej_add_ge: rearrange algebra
e2a07c7 Fix compilation with C++
873a453 Merge pull request #250
91eb0da Merge pull request #247
210ffed Use separate in and out pointers in `secp256k1_ec_pubkey_decompress`
a1d5ae1 Tiny optimization
729badf Merge pull request #210
2d5a186 Apply effective-affine trick to precomp
4f9791a Effective affine addition in EC multiplication
2b4cf41 Use pkg-config always when possible, with failover to manual checks for libcrypto

git-subtree-dir: src/secp256k1
git-subtree-split: 2bfb82b10edf0f0b0e366a12f94c8b21a914159d

1 files changed, 260 insertions, 0 deletions

diff --git a/src/ecmult_const_impl.h b/src/ecmult_const_impl.h
new file mode 100644
index 0000000000..90ac94770e
--- /dev/null
+++ b/src/ecmult_const_impl.h
@@ -0,0 +1,260 @@
+/**********************************************************************
+ * Copyright (c) 2015 Pieter Wuille, Andrew Poelstra                  *
+ * Distributed under the MIT software license, see the accompanying   *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef _SECP256K1_ECMULT_CONST_IMPL_
+#define _SECP256K1_ECMULT_CONST_IMPL_
+
+#include "scalar.h"
+#include "group.h"
+#include "ecmult_const.h"
+#include "ecmult_impl.h"
+
+#ifdef USE_ENDOMORPHISM
+    #define WNAF_BITS 128
+#else
+    #define WNAF_BITS 256
+#endif
+#define WNAF_SIZE(w) ((WNAF_BITS + (w) - 1) / (w))
+
+/* This is like `ECMULT_TABLE_GET_GE` but is constant time */
+#define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \
+    int m; \
+    int abs_n = (n) * (((n) > 0) * 2 - 1); \
+    int idx_n = abs_n / 2; \
+    secp256k1_fe neg_y; \
+    VERIFY_CHECK(((n) & 1) == 1); \
+    VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
+    VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
+    VERIFY_SETUP(secp256k1_fe_clear(&(r)->x)); \
+    VERIFY_SETUP(secp256k1_fe_clear(&(r)->y)); \
+    for (m = 0; m < ECMULT_TABLE_SIZE(w); m++) { \
+        /* This loop is used to avoid secret data in array indices. See
+         * the comment in ecmult_gen_impl.h for rationale. */ \
+        secp256k1_fe_cmov(&(r)->x, &(pre)[m].x, m == idx_n); \
+        secp256k1_fe_cmov(&(r)->y, &(pre)[m].y, m == idx_n); \
+    } \
+    (r)->infinity = 0; \
+    secp256k1_fe_negate(&neg_y, &(r)->y, 1); \
+    secp256k1_fe_cmov(&(r)->y, &neg_y, (n) != abs_n); \
+} while(0)
+
+
+/** Convert a number to WNAF notation. The number becomes represented by sum(2^{wi} * wnaf[i], i=0..return_val)
+ *  with the following guarantees:
+ *  - each wnaf[i] an odd integer between -(1 << w) and (1 << w)
+ *  - each wnaf[i] is nonzero
+ *  - the number of words set is returned; this is always (WNAF_BITS + w - 1) / w
+ *
+ *  Adapted from `The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar
+ *  Multiplications Secure against Side Channel Attacks`, Okeya and Tagaki. M. Joye (Ed.)
+ *  CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlagy Berlin Heidelberg 2003
+ *
+ *  Numbers reference steps of `Algorithm SPA-resistant Width-w NAF with Odd Scalar` on pp. 335
+ */
+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
+     * 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 */
+    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);
+    /* 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);
+    secp256k1_scalar_cadd_bit(&s, bit, not_neg_one);
+    /* If we had negative one, flip == 1, s.d[0] == 0, bit == 1, so caller expects
+     * that we added two to it and flipped it. In fact for -1 these operations are
+     * identical. We only flipped, but since skewing is required (in the sense that
+     * the skew must be 1 or 2, never zero) and flipping is not, we need to change
+     * our flags to claim that we only skewed. */
+    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);
+    while (word * w < WNAF_BITS) {
+        int sign;
+        int even;
+
+        /* 4.1 4.4 */
+        u = secp256k1_scalar_shr_int(&s, w);
+        /* 4.2 */
+        even = ((u & 1) == 0);
+        sign = 2 * (u_last > 0) - 1;
+        u += sign * even;
+        u_last -= sign * even * (1 << w);
+
+        /* 4.3, adapted for global sign change */
+        wnaf[word++] = u_last * global_sign;
+
+        u_last = u;
+    }
+    wnaf[word] = u * global_sign;
+
+    VERIFY_CHECK(secp256k1_scalar_is_zero(&s));
+    VERIFY_CHECK(word == WNAF_SIZE(w));
+    return skew;
+}
+
+
+static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *scalar) {
+    secp256k1_ge pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
+    secp256k1_ge tmpa;
+    secp256k1_fe Z;
+
+#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;
+    secp256k1_scalar sc = *scalar;
+
+    /* build wnaf representation for q. */
+#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);
+#endif
+
+    /* Calculate odd multiples of a.
+     * All multiples are brought to the same Z 'denominator', which is stored
+     * in Z. Due to secp256k1' isomorphism we can do all operations pretending
+     * that the Z coordinate was 1, use affine addition formulae, and correct
+     * the Z coordinate of the result once at the end.
+     */
+    secp256k1_gej_set_ge(r, a);
+    secp256k1_ecmult_odd_multiples_table_globalz_windowa(pre_a, &Z, r);
+    for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
+        secp256k1_fe_normalize_weak(&pre_a[i].y);
+    }
+#ifdef USE_ENDOMORPHISM
+    for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
+        secp256k1_ge_mul_lambda(&pre_a_lam[i], &pre_a[i]);
+    }
+#endif
+
+    /* 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);
+
+    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--) {
+        int n;
+        int j;
+        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);
+
+        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;
+        secp256k1_ge_storage correction_lam_stor;
+        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);
+        secp256k1_ge_to_storage(&correction_lam_stor, a);
+        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);
+        secp256k1_ge_storage_cmov(&correction_lam_stor, &a2_stor, skew_lam == 2);
+
+        /* Apply the correction */
+        secp256k1_ge_from_storage(&correction, &correction_1_stor);
+        secp256k1_ge_neg(&correction, &correction);
+        secp256k1_gej_add_ge(r, r, &correction);
+
+        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