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, 68 insertions, 18 deletions

diff --git a/src/testrand_impl.h b/src/testrand_impl.h
index 21c69f1c51..15c7b9f12d 100644
--- a/src/testrand_impl.h
+++ b/src/testrand_impl.h
@@ -1,5 +1,5 @@
 /**********************************************************************
- * Copyright (c) 2013, 2014 Pieter Wuille                             *
+ * Copyright (c) 2013-2015 Pieter Wuille                              *
  * Distributed under the MIT software license, see the accompanying   *
  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
  **********************************************************************/
@@ -16,9 +16,11 @@
 static secp256k1_rfc6979_hmac_sha256_t secp256k1_test_rng;
 static uint32_t secp256k1_test_rng_precomputed[8];
 static int secp256k1_test_rng_precomputed_used = 8;
+static uint64_t secp256k1_test_rng_integer;
+static int secp256k1_test_rng_integer_bits_left = 0;
 
 SECP256K1_INLINE static void secp256k1_rand_seed(const unsigned char *seed16) {
-    secp256k1_rfc6979_hmac_sha256_initialize(&secp256k1_test_rng, (const unsigned char*)"TestRNG", 7, seed16, 16, NULL, 0);
+    secp256k1_rfc6979_hmac_sha256_initialize(&secp256k1_test_rng, seed16, 16);
 }
 
 SECP256K1_INLINE static uint32_t secp256k1_rand32(void) {
@@ -29,32 +31,80 @@ SECP256K1_INLINE static uint32_t secp256k1_rand32(void) {
     return secp256k1_test_rng_precomputed[secp256k1_test_rng_precomputed_used++];
 }
 
+static uint32_t secp256k1_rand_bits(int bits) {
+    uint32_t ret;
+    if (secp256k1_test_rng_integer_bits_left < bits) {
+        secp256k1_test_rng_integer |= (((uint64_t)secp256k1_rand32()) << secp256k1_test_rng_integer_bits_left);
+        secp256k1_test_rng_integer_bits_left += 32;
+    }
+    ret = secp256k1_test_rng_integer;
+    secp256k1_test_rng_integer >>= bits;
+    secp256k1_test_rng_integer_bits_left -= bits;
+    ret &= ((~((uint32_t)0)) >> (32 - bits));
+    return ret;
+}
+
+static uint32_t secp256k1_rand_int(uint32_t range) {
+    /* We want a uniform integer between 0 and range-1, inclusive.
+     * B is the smallest number such that range <= 2**B.
+     * two mechanisms implemented here:
+     * - generate B bits numbers until one below range is found, and return it
+     * - find the largest multiple M of range that is <= 2**(B+A), generate B+A
+     *   bits numbers until one below M is found, and return it modulo range
+     * The second mechanism consumes A more bits of entropy in every iteration,
+     * but may need fewer iterations due to M being closer to 2**(B+A) then
+     * range is to 2**B. The array below (indexed by B) contains a 0 when the
+     * first mechanism is to be used, and the number A otherwise.
+     */
+    static const int addbits[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0};
+    uint32_t trange, mult;
+    int bits = 0;
+    if (range <= 1) {
+        return 0;
+    }
+    trange = range - 1;
+    while (trange > 0) {
+        trange >>= 1;
+        bits++;
+    }
+    if (addbits[bits]) {
+        bits = bits + addbits[bits];
+        mult = ((~((uint32_t)0)) >> (32 - bits)) / range;
+        trange = range * mult;
+    } else {
+        trange = range;
+        mult = 1;
+    }
+    while(1) {
+        uint32_t x = secp256k1_rand_bits(bits);
+        if (x < trange) {
+            return (mult == 1) ? x : (x % range);
+        }
+    }
+}
+
 static void secp256k1_rand256(unsigned char *b32) {
     secp256k1_rfc6979_hmac_sha256_generate(&secp256k1_test_rng, b32, 32);
 }
 
-static void secp256k1_rand256_test(unsigned char *b32) {
-    int bits=0;
-    uint64_t ent = 0;
-    int entleft = 0;
-    memset(b32, 0, 32);
-    while (bits < 256) {
+static void secp256k1_rand_bytes_test(unsigned char *bytes, size_t len) {
+    size_t bits = 0;
+    memset(bytes, 0, len);
+    while (bits < len * 8) {
         int now;
         uint32_t val;
-        if (entleft < 12) {
-            ent |= ((uint64_t)secp256k1_rand32()) << entleft;
-            entleft += 32;
-        }
-        now = 1 + ((ent % 64)*((ent >> 6) % 32)+16)/31;
-        val = 1 & (ent >> 11);
-        ent >>= 12;
-        entleft -= 12;
-        while (now > 0 && bits < 256) {
-            b32[bits / 8] |= val << (bits % 8);
+        now = 1 + (secp256k1_rand_bits(6) * secp256k1_rand_bits(5) + 16) / 31;
+        val = secp256k1_rand_bits(1);
+        while (now > 0 && bits < len * 8) {
+            bytes[bits / 8] |= val << (bits % 8);
             now--;
             bits++;
         }
     }
 }
 
+static void secp256k1_rand256_test(unsigned char *b32) {
+    secp256k1_rand_bytes_test(b32, 32);
+}
+
 #endif