Squashed 'src/secp256k1/' changes from ad2028f..b0210a9

b0210a9 Merge pull request #135
ee3eb4b Fix a memory leak and add a number of small tests.
4d879a3 Merge pull request #134
d5e8362 Merge pull request #127
7b92cf6 Merge pull request #132
0bf70a5 Merge pull request #133
29ae131 Make scalar_add_bit test's overflow detection exact
9048def Avoid undefined shift behaviour
efb7d4b Use constant-time conditional moves instead of byte slicing
d220062 Merge pull request #131
82f9254 Fix typo
601ca04 Merge pull request #129
35399e0 Bugfix: b is restricted, not r
c35ff1e Convert lambda splitter to pure scalar code.
cc604e9 Avoid division when decomposing scalars
ff8746d Add secp256k1_scalar_mul_shift_var
bd313f7 Merge pull request #119
276f987 Merge pull request #124
25d125e Merge pull request #126
24b3c65 Add a test case for ECDSA recomputing infinity
32600e5 Add a test for r >= order signature handling
4d4eeea Make secp256k1_fe_mul_inner use the r != property
be82e92 Require that r and b are different for field multiplication.
597128d Make num optional
659b554 Make constant initializers independent from num
0af5b47 Merge pull request #120
e2e8a36 Merge pull request #117
c76be9e Remove unused num functions
4285a98 Move lambda-splitting code to scalar.
f24041d Switch all EC/ECDSA logic from num to scalar
6794be6 Add scalar splitting functions
d1502eb Add secp256k1_scalar_inverse_var which delegates to GMP
b5c9ee7 Make test_point_times_order test meaningful again
0b73059 Switch wnaf splitting from num-based to scalar-based
1e6c77c Generalize secp256k1_scalar_get_bits
5213207 Add secp256k1_scalar_add_bit
3c0ae43 Merge pull request #122
6e05287 Do signature recovery/verification with 4 possible recid case
e3d692f Explain why no y=0 check is necessary for doubling
f7dc1c6 Optimize doubling: secp256k1 has no y=0 point
666d3b5 Merge pull request #121
2a54f9b Correct typo in comment
9d64145 Merge pull request #114
99f0728 Fix secp256k1_num_set_bin handling of 0
d907ebc Add bounds checking to field element setters
bb2cd94 Merge pull request #116
665775b Don't split the g factor when not using endomorphism
9431d6b Merge pull request #115
e2274c5 build: osx: attempt to work with homebrew keg-only packages

git-subtree-dir: src/secp256k1
git-subtree-split: b0210a95da433e048a11d298efbcc14eb423c95f

1 files changed, 101 insertions, 79 deletions

diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
index 4c05ec39f8..a951d0b4ad 100644
--- a/src/ecdsa_impl.h
+++ b/src/ecdsa_impl.h
@@ -8,13 +8,51 @@
 #ifndef _SECP256K1_ECDSA_IMPL_H_
 #define _SECP256K1_ECDSA_IMPL_H_
 
-#include "num.h"
+#include "scalar.h"
 #include "field.h"
 #include "group.h"
 #include "ecmult.h"
 #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*)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(&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);
+}
+
 static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
     if (sig[0] != 0x30) return 0;
     int lenr = sig[3];
@@ -26,18 +64,37 @@ static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned ch
     if (lenr == 0) return 0;
     if (sig[lenr+4] != 0x02) return 0;
     if (lens == 0) return 0;
-    secp256k1_num_set_bin(&r->r, sig+4, lenr);
-    secp256k1_num_set_bin(&r->s, sig+6+lenr, lens);
+    const unsigned char *sp = sig + 6 + lenr;
+    while (lens > 0 && sp[0] == 0) {
+        lens--;
+        sp++;
+    }
+    if (lens > 32) return 0;
+    const unsigned char *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;
+    secp256k1_scalar_set_b32(&r->r, ra, &overflow);
+    if (overflow) return 0;
+    secp256k1_scalar_set_b32(&r->s, sa, &overflow);
+    if (overflow) return 0;
     return 1;
 }
 
 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
-    int lenR = (secp256k1_num_bits(&a->r) + 7)/8;
-    if (lenR == 0 || secp256k1_num_get_bit(&a->r, lenR*8-1))
-        lenR++;
-    int lenS = (secp256k1_num_bits(&a->s) + 7)/8;
-    if (lenS == 0 || secp256k1_num_get_bit(&a->s, lenS*8-1))
-        lenS++;
+    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;
+    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)
         return 0;
     *size = 6 + lenS + lenR;
@@ -45,98 +102,67 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const se
     sig[1] = 4 + lenS + lenR;
     sig[2] = 0x02;
     sig[3] = lenR;
-    secp256k1_num_get_bin(sig+4, lenR, &a->r);
+    memcpy(sig+4, rp, lenR);
     sig[4+lenR] = 0x02;
     sig[5+lenR] = lenS;
-    secp256k1_num_get_bin(sig+lenR+6, lenS, &a->s);
+    memcpy(sig+lenR+6, sp, lenS);
     return 1;
 }
 
-static int secp256k1_ecdsa_sig_recompute(secp256k1_num_t *r2, const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_num_t *message) {
-    const secp256k1_ge_consts_t *c = secp256k1_ge_consts;
-
-    if (secp256k1_num_is_neg(&sig->r) || secp256k1_num_is_neg(&sig->s))
-        return 0;
-    if (secp256k1_num_is_zero(&sig->r) || secp256k1_num_is_zero(&sig->s))
-        return 0;
-    if (secp256k1_num_cmp(&sig->r, &c->order) >= 0 || secp256k1_num_cmp(&sig->s, &c->order) >= 0)
+static int secp256k1_ecdsa_sig_recompute(secp256k1_scalar_t *r2, const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
+    if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
         return 0;
 
     int ret = 0;
-    secp256k1_num_t sn, u1, u2;
-    secp256k1_num_init(&sn);
-    secp256k1_num_init(&u1);
-    secp256k1_num_init(&u2);
-    secp256k1_num_mod_inverse(&sn, &sig->s, &c->order);
-    secp256k1_num_mod_mul(&u1, &sn, message, &c->order);
-    secp256k1_num_mod_mul(&u2, &sn, &sig->r, &c->order);
+    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);
     if (!secp256k1_gej_is_infinity(&pr)) {
         secp256k1_fe_t xr; secp256k1_gej_get_x_var(&xr, &pr);
         secp256k1_fe_normalize(&xr);
         unsigned char xrb[32]; secp256k1_fe_get_b32(xrb, &xr);
-        secp256k1_num_set_bin(r2, xrb, 32);
-        secp256k1_num_mod(r2, &c->order);
+        secp256k1_scalar_set_b32(r2, xrb, NULL);
         ret = 1;
     }
-    secp256k1_num_free(&sn);
-    secp256k1_num_free(&u1);
-    secp256k1_num_free(&u2);
     return ret;
 }
 
-static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_num_t *message, int recid) {
-    const secp256k1_ge_consts_t *c = secp256k1_ge_consts;
-
-    if (secp256k1_num_is_neg(&sig->r) || secp256k1_num_is_neg(&sig->s))
-        return 0;
-    if (secp256k1_num_is_zero(&sig->r) || secp256k1_num_is_zero(&sig->s))
-        return 0;
-    if (secp256k1_num_cmp(&sig->r, &c->order) >= 0 || secp256k1_num_cmp(&sig->s, &c->order) >= 0)
+static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
+    if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
         return 0;
 
-    secp256k1_num_t rx;
-    secp256k1_num_init(&rx);
-    secp256k1_num_copy(&rx, &sig->r);
+    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) {
-        secp256k1_num_add(&rx, &rx, &c->order);
-        if (secp256k1_num_cmp(&rx, &secp256k1_fe_consts->p) >= 0)
+        if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
             return 0;
+        secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
     }
-    unsigned char brx[32];
-    secp256k1_num_get_bin(brx, 32, &rx);
-    secp256k1_num_free(&rx);
-    secp256k1_fe_t fx;
-    secp256k1_fe_set_b32(&fx, brx);
     secp256k1_ge_t x;
     if (!secp256k1_ge_set_xo(&x, &fx, recid & 1))
         return 0;
     secp256k1_gej_t xj;
     secp256k1_gej_set_ge(&xj, &x);
-    secp256k1_num_t rn, u1, u2;
-    secp256k1_num_init(&rn);
-    secp256k1_num_init(&u1);
-    secp256k1_num_init(&u2);
-    secp256k1_num_mod_inverse(&rn, &sig->r, &c->order);
-    secp256k1_num_mod_mul(&u1, &rn, message, &c->order);
-    secp256k1_num_sub(&u1, &c->order, &u1);
-    secp256k1_num_mod_mul(&u2, &rn, &sig->s, &c->order);
+    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);
-    secp256k1_num_free(&rn);
-    secp256k1_num_free(&u1);
-    secp256k1_num_free(&u2);
     return !secp256k1_gej_is_infinity(&qj);
 }
 
-static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_num_t *message) {
-    secp256k1_num_t r2;
-    secp256k1_num_init(&r2);
+static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
+    secp256k1_scalar_t r2;
     int ret = 0;
-    ret = secp256k1_ecdsa_sig_recompute(&r2, sig, pubkey, message) && secp256k1_num_cmp(&sig->r, &r2) == 0;
-    secp256k1_num_free(&r2);
+    ret = secp256k1_ecdsa_sig_recompute(&r2, sig, pubkey, message) && secp256k1_scalar_eq(&sig->r, &r2);
     return ret;
 }
 
@@ -150,34 +176,30 @@ static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_
     secp256k1_fe_normalize(&r.y);
     secp256k1_fe_get_b32(b, &r.x);
     int overflow = 0;
-    secp256k1_scalar_t sigr;
-    secp256k1_scalar_set_b32(&sigr, b, &overflow);
+    secp256k1_scalar_set_b32(&sig->r, b, &overflow);
     if (recid)
         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
     secp256k1_scalar_t n;
-    secp256k1_scalar_mul(&n, &sigr, seckey);
+    secp256k1_scalar_mul(&n, &sig->r, seckey);
     secp256k1_scalar_add(&n, &n, message);
-    secp256k1_scalar_t sigs;
-    secp256k1_scalar_inverse(&sigs, nonce);
-    secp256k1_scalar_mul(&sigs, &sigs, &n);
+    secp256k1_scalar_inverse(&sig->s, nonce);
+    secp256k1_scalar_mul(&sig->s, &sig->s, &n);
     secp256k1_scalar_clear(&n);
     secp256k1_gej_clear(&rp);
     secp256k1_ge_clear(&r);
-    if (secp256k1_scalar_is_zero(&sigs))
+    if (secp256k1_scalar_is_zero(&sig->s))
         return 0;
-    if (secp256k1_scalar_is_high(&sigs)) {
-        secp256k1_scalar_negate(&sigs, &sigs);
+    if (secp256k1_scalar_is_high(&sig->s)) {
+        secp256k1_scalar_negate(&sig->s, &sig->s);
         if (recid)
             *recid ^= 1;
     }
-    secp256k1_scalar_get_num(&sig->s, &sigs);
-    secp256k1_scalar_get_num(&sig->r, &sigr);
     return 1;
 }
 
-static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_num_t *r, const secp256k1_num_t *s) {
-    secp256k1_num_copy(&sig->r, r);
-    secp256k1_num_copy(&sig->s, s);
+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