Squashed 'src/secp256k1/' changes from 50cc6ab..1897b8e

1897b8e Merge pull request #229
efc571c Add simple testcases for signing with rfc6979 extra entropy.
1573a10 Add ability to pass extra entropy to rfc6979
3087bc4 Merge pull request #228
d9b9f11 Merge pull request #218
0065a8f Eliminate multiple-returns from secp256k1.c.
354ffa3 Make secp256k1_ec_pubkey_create reject oversized secrets.
27bc131 Silence some warnings from pedantic static analysis tools, improve compatibility with C++.
3b7ea63 Merge pull request #221
f789c5b Merge pull request #215
4bc273b Merge pull request #222
137a8ec Merge pull request #216
7c3771d Disable overlength-strings warnings.
8956111 use 128-bit hex seed
02efd06 Use RFC6979 for test PRNGs
ae55e85 Use faster byteswapping and avoid alignment-increasing casts.
443cd4b Get rid of hex format and some binary conversions
0bada0e Merge #214: Improve signing API documentation & specification
8030d7c Improve signing API documentation & specification
7b2fc1c Merge #213: Removed gotos, which are hard to trace and maintain.
11690d3 Removed gotos, which are hard to trace and maintain.
122a1ec Merge pull request #205
035406d Merge pull request #206
2d4cd53 Merge pull request #161
34b898d Additional comments for the testing PRNG and a seeding fix.
6efd6e7 Some comments explaining some of the constants in the code.
ffccfd2 x86_64 assembly optimization for scalar_4x64
67cbdf0 Merge pull request #207
039723d Benchmarks for all internal operations
6cc8425 Include a comment on secp256k1_ecdsa_sign explaining low-s.
f88343f Merge pull request #203
d61e899 Add group operation counts
2473f17 Merge pull request #202
b5bbce6 Some readme updates, e.g. removal of the GMP field.
f0d851e Merge pull request #201
a0ea884 Merge pull request #200
f735446 Convert the rest of the codebase to C89.
bf2e1ac Convert tests to C89. (also fixes a use of bare "inline" in field)
fc8285f Merge pull request #199
fff412e Merge pull request #197
4be8d6f Centralize the definition of uint128_t and use it uniformly.
d9543c9 Switch scalar code to C89.
fcc48c4 Remove the non-storage cmov
55422b6 Switch ecmult_gen to use storage types
41f8455 Use group element storage type in EC multiplications
e68d720 Add group element storage type
ff889f7 Field storage type
7137be8 Merge pull request #196
0768bd5 Get rid of variable-length hex string conversions
e84e761 Merge pull request #195
792bcdb Covert several more files to C89.
45cdf44 Merge pull request #193
17db09e Merge pull request #194
402878a fix ifdef/ifndef
25b35c7 Convert field code to strict C89 (+ long long, +__int128)
3627437 C89 nits and dead code removal.
a9f350d Merge pull request #191
4732d26 Convert the field/group/ecdsa constant initialization to static consts
19f3e76 Remove unused secp256k1_fe_inner_{start, stop} functions
f1ebfe3 Convert the scalar constant initialization to static consts

git-subtree-dir: src/secp256k1
git-subtree-split: 1897b8e90bbbdcd919427c9a8ae35b420e919d8f

1 files changed, 86 insertions, 87 deletions

diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
index 674650c1e9..1a77649390 100644
--- a/src/ecdsa_impl.h
+++ b/src/ecdsa_impl.h
@@ -15,71 +15,69 @@
 #include "ecmult_gen.h"
 #include "ecdsa.h"
 
-typedef struct {
-    secp256k1_fe_t order_as_fe;
-    secp256k1_fe_t p_minus_order;
-} secp256k1_ecdsa_consts_t;
-
-static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;
-
-static void secp256k1_ecdsa_start(void) {
-    if (secp256k1_ecdsa_consts != NULL)
-        return;
-
-    /* Allocate. */
-    secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
-
-    static const unsigned char order[] = {
-        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
-        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
-        0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
-        0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
-    };
-
-    secp256k1_fe_set_b32(&ret->order_as_fe, order);
-    secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
-    secp256k1_fe_normalize_var(&ret->p_minus_order);
-
-    /* Set the global pointer. */
-    secp256k1_ecdsa_consts = ret;
-}
-
-static void secp256k1_ecdsa_stop(void) {
-    if (secp256k1_ecdsa_consts == NULL)
-        return;
-
-    secp256k1_ecdsa_consts_t *c = (secp256k1_ecdsa_consts_t*)secp256k1_ecdsa_consts;
-    secp256k1_ecdsa_consts = NULL;
-    free(c);
-}
+/** Group order for secp256k1 defined as 'n' in "Standards for Efficient Cryptography" (SEC2) 2.7.1
+ *  sage: for t in xrange(1023, -1, -1):
+ *     ..   p = 2**256 - 2**32 - t
+ *     ..   if p.is_prime():
+ *     ..     print '%x'%p
+ *     ..     break
+ *   'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f'
+ *  sage: a = 0
+ *  sage: b = 7
+ *  sage: F = FiniteField (p)
+ *  sage: '%x' % (EllipticCurve ([F (a), F (b)]).order())
+ *   'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
+ */
+static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
+    0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
+    0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
+);
+
+/** Difference between field and order, values 'p' and 'n' values defined in
+ *  "Standards for Efficient Cryptography" (SEC2) 2.7.1.
+ *  sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
+ *  sage: a = 0
+ *  sage: b = 7
+ *  sage: F = FiniteField (p)
+ *  sage: '%x' % (p - EllipticCurve ([F (a), F (b)]).order())
+ *   '14551231950b75fc4402da1722fc9baee'
+ */
+static const secp256k1_fe_t secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
+    0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
+);
 
 static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
+    unsigned char ra[32] = {0}, sa[32] = {0};
+    const unsigned char *rp;
+    const unsigned char *sp;
+    int lenr;
+    int lens;
+    int overflow;
     if (sig[0] != 0x30) return 0;
-    int lenr = sig[3];
+    lenr = sig[3];
     if (5+lenr >= size) return 0;
-    int lens = sig[lenr+5];
+    lens = sig[lenr+5];
     if (sig[1] != lenr+lens+4) return 0;
     if (lenr+lens+6 > size) return 0;
     if (sig[2] != 0x02) return 0;
     if (lenr == 0) return 0;
     if (sig[lenr+4] != 0x02) return 0;
     if (lens == 0) return 0;
-    const unsigned char *sp = sig + 6 + lenr;
+    sp = sig + 6 + lenr;
     while (lens > 0 && sp[0] == 0) {
         lens--;
         sp++;
     }
     if (lens > 32) return 0;
-    const unsigned char *rp = sig + 4;
+    rp = sig + 4;
     while (lenr > 0 && rp[0] == 0) {
         lenr--;
         rp++;
     }
     if (lenr > 32) return 0;
-    unsigned char ra[32] = {0}, sa[32] = {0};
     memcpy(ra + 32 - lenr, rp, lenr);
     memcpy(sa + 32 - lens, sp, lens);
-    int overflow = 0;
+    overflow = 0;
     secp256k1_scalar_set_b32(&r->r, ra, &overflow);
     if (overflow) return 0;
     secp256k1_scalar_set_b32(&r->s, sa, &overflow);
@@ -89,10 +87,10 @@ static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned ch
 
 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
     unsigned char r[33] = {0}, s[33] = {0};
-    secp256k1_scalar_get_b32(&r[1], &a->r);
-    secp256k1_scalar_get_b32(&s[1], &a->s);
     unsigned char *rp = r, *sp = s;
     int lenR = 33, lenS = 33;
+    secp256k1_scalar_get_b32(&r[1], &a->r);
+    secp256k1_scalar_get_b32(&s[1], &a->s);
     while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
     while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
     if (*size < 6+lenS+lenR)
@@ -110,93 +108,100 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const se
 }
 
 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
+    unsigned char c[32];
+    secp256k1_scalar_t sn, u1, u2;
+    secp256k1_fe_t xr;
+    secp256k1_gej_t pubkeyj;
+    secp256k1_gej_t pr;
+
     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
         return 0;
 
-    secp256k1_scalar_t sn, u1, u2;
     secp256k1_scalar_inverse_var(&sn, &sig->s);
     secp256k1_scalar_mul(&u1, &sn, message);
     secp256k1_scalar_mul(&u2, &sn, &sig->r);
-    secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
-    secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
+    secp256k1_gej_set_ge(&pubkeyj, pubkey);
+    secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
     if (secp256k1_gej_is_infinity(&pr)) {
         return 0;
     }
-    unsigned char c[32];
     secp256k1_scalar_get_b32(c, &sig->r);
-    secp256k1_fe_t xr;
     secp256k1_fe_set_b32(&xr, c);
 
-    // We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
-    // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
-    // compute the remainder modulo n, and compare it to xr. However:
-    //
-    //       xr == X(pr) mod n
-    //   <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
-    //   [Since 2 * n > p, h can only be 0 or 1]
-    //   <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
-    //   [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
-    //   <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
-    //   [Multiplying both sides of the equations by pr.z^2 mod p]
-    //   <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
-    //
-    // Thus, we can avoid the inversion, but we have to check both cases separately.
-    // secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
+    /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
+     *  in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
+     *  compute the remainder modulo n, and compare it to xr. However:
+     *
+     *        xr == X(pr) mod n
+     *    <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
+     *    [Since 2 * n > p, h can only be 0 or 1]
+     *    <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
+     *    [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
+     *    <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
+     *    [Multiplying both sides of the equations by pr.z^2 mod p]
+     *    <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
+     *
+     *  Thus, we can avoid the inversion, but we have to check both cases separately.
+     *  secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
+     */
     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
-        // xr.x == xr * xr.z^2 mod p, so the signature is valid.
+        /* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
         return 1;
     }
-    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
-        // xr + p >= n, so we can skip testing the second case.
+    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
+        /* xr + p >= n, so we can skip testing the second case. */
         return 0;
     }
-    secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
+    secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
-        // (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid.
+        /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
         return 1;
     }
     return 0;
 }
 
 static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
+    unsigned char brx[32];
+    secp256k1_fe_t fx;
+    secp256k1_ge_t x;
+    secp256k1_gej_t xj;
+    secp256k1_scalar_t rn, u1, u2;
+    secp256k1_gej_t qj;
+
     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
         return 0;
 
-    unsigned char brx[32];
     secp256k1_scalar_get_b32(brx, &sig->r);
-    secp256k1_fe_t fx;
     VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
     if (recid & 2) {
-        if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
+        if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0)
             return 0;
-        secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
+        secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
     }
-    secp256k1_ge_t x;
     if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
         return 0;
-    secp256k1_gej_t xj;
     secp256k1_gej_set_ge(&xj, &x);
-    secp256k1_scalar_t rn, u1, u2;
     secp256k1_scalar_inverse_var(&rn, &sig->r);
     secp256k1_scalar_mul(&u1, &rn, message);
     secp256k1_scalar_negate(&u1, &u1);
     secp256k1_scalar_mul(&u2, &rn, &sig->s);
-    secp256k1_gej_t qj;
     secp256k1_ecmult(&qj, &xj, &u2, &u1);
     secp256k1_ge_set_gej_var(pubkey, &qj);
     return !secp256k1_gej_is_infinity(&qj);
 }
 
 static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
+    unsigned char b[32];
     secp256k1_gej_t rp;
-    secp256k1_ecmult_gen(&rp, nonce);
     secp256k1_ge_t r;
+    secp256k1_scalar_t n;
+    int overflow = 0;
+
+    secp256k1_ecmult_gen(&rp, nonce);
     secp256k1_ge_set_gej(&r, &rp);
-    unsigned char b[32];
     secp256k1_fe_normalize(&r.x);
     secp256k1_fe_normalize(&r.y);
     secp256k1_fe_get_b32(b, &r.x);
-    int overflow = 0;
     secp256k1_scalar_set_b32(&sig->r, b, &overflow);
     if (secp256k1_scalar_is_zero(&sig->r)) {
         /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
@@ -206,7 +211,6 @@ static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_
     }
     if (recid)
         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
-    secp256k1_scalar_t n;
     secp256k1_scalar_mul(&n, &sig->r, seckey);
     secp256k1_scalar_add(&n, &n, message);
     secp256k1_scalar_inverse(&sig->s, nonce);
@@ -224,9 +228,4 @@ static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_
     return 1;
 }
 
-static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *r, const secp256k1_scalar_t *s) {
-    sig->r = *r;
-    sig->s = *s;
-}
-
 #endif