diff options
Diffstat (limited to 'src/ecdsa_impl.h')
-rw-r--r-- | src/ecdsa_impl.h | 180 |
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 |