src/ecdsa_impl.h

   1 /**********************************************************************
   2  * Copyright (c) 2013, 2014 Pieter Wuille                               *
   3  * Distributed under the MIT software license, see the accompanying   *
   4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
   5  **********************************************************************/
   6
   7
   8 #ifndef _SECP256K1_ECDSA_IMPL_H_
   9 #define _SECP256K1_ECDSA_IMPL_H_
  10
  11 #include "scalar.h"
  12 #include "field.h"
  13 #include "group.h"
  14 #include "ecmult.h"
  15 #include "ecmult_gen.h"
  16 #include "ecdsa.h"
  17
  18 typedef struct {
  19     secp256k1_fe_t order_as_fe;
  20     secp256k1_fe_t p_minus_order;
  21 } secp256k1_ecdsa_consts_t;
  22
  23 static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;
  24
  25 static void secp256k1_ecdsa_start(void) {
  26     if (secp256k1_ecdsa_consts != NULL)
  27         return;
  28
  29     /* Allocate. */
  30     secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
  31
  32     static const unsigned char order[] = {
  33         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  34         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
  35         0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
  36         0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
  37     };
  38
  39     secp256k1_fe_set_b32(&ret->order_as_fe, order);
  40     secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
  41     secp256k1_fe_normalize_var(&ret->p_minus_order);
  42
  43     /* Set the global pointer. */
  44     secp256k1_ecdsa_consts = ret;
  45 }
  46
  47 static void secp256k1_ecdsa_stop(void) {
  48     if (secp256k1_ecdsa_consts == NULL)
  49         return;
  50
  51     secp256k1_ecdsa_consts_t *c = (secp256k1_ecdsa_consts_t*)secp256k1_ecdsa_consts;
  52     secp256k1_ecdsa_consts = NULL;
  53     free(c);
  54 }
  55
  56 static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
  57     if (sig[0] != 0x30) return 0;
  58     int lenr = sig[3];
  59     if (5+lenr >= size) return 0;
  60     int lens = sig[lenr+5];
  61     if (sig[1] != lenr+lens+4) return 0;
  62     if (lenr+lens+6 > size) return 0;
  63     if (sig[2] != 0x02) return 0;
  64     if (lenr == 0) return 0;
  65     if (sig[lenr+4] != 0x02) return 0;
  66     if (lens == 0) return 0;
  67     const unsigned char *sp = sig + 6 + lenr;
  68     while (lens > 0 && sp[0] == 0) {
  69         lens--;
  70         sp++;
  71     }
  72     if (lens > 32) return 0;
  73     const unsigned char *rp = sig + 4;
  74     while (lenr > 0 && rp[0] == 0) {
  75         lenr--;
  76         rp++;
  77     }
  78     if (lenr > 32) return 0;
  79     unsigned char ra[32] = {0}, sa[32] = {0};
  80     memcpy(ra + 32 - lenr, rp, lenr);
  81     memcpy(sa + 32 - lens, sp, lens);
  82     int overflow = 0;
  83     secp256k1_scalar_set_b32(&r->r, ra, &overflow);
  84     if (overflow) return 0;
  85     secp256k1_scalar_set_b32(&r->s, sa, &overflow);
  86     if (overflow) return 0;
  87     return 1;
  88 }
  89
  90 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
  91     unsigned char r[33] = {0}, s[33] = {0};
  92     secp256k1_scalar_get_b32(&r[1], &a->r);
  93     secp256k1_scalar_get_b32(&s[1], &a->s);
  94     unsigned char *rp = r, *sp = s;
  95     int lenR = 33, lenS = 33;
  96     while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
  97     while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
  98     if (*size < 6+lenS+lenR)
  99         return 0;
 100     *size = 6 + lenS + lenR;
 101     sig[0] = 0x30;
 102     sig[1] = 4 + lenS + lenR;
 103     sig[2] = 0x02;
 104     sig[3] = lenR;
 105     memcpy(sig+4, rp, lenR);
 106     sig[4+lenR] = 0x02;
 107     sig[5+lenR] = lenS;
 108     memcpy(sig+lenR+6, sp, lenS);
 109     return 1;
 110 }
 111
 112 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
 113     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
 114         return 0;
 115
 116     secp256k1_scalar_t sn, u1, u2;
 117     secp256k1_scalar_inverse_var(&sn, &sig->s);
 118     secp256k1_scalar_mul(&u1, &sn, message);
 119     secp256k1_scalar_mul(&u2, &sn, &sig->r);
 120     secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
 121     secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
 122     if (secp256k1_gej_is_infinity(&pr)) {
 123         return 0;
 124     }
 125     unsigned char c[32];
 126     secp256k1_scalar_get_b32(c, &sig->r);
 127     secp256k1_fe_t xr;
 128     secp256k1_fe_set_b32(&xr, c);
 129
 130     // We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
 131     // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
 132     // compute the remainder modulo n, and compare it to xr. However:
 133     //
 134     //       xr == X(pr) mod n
 135     //   <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
 136     //   [Since 2 * n > p, h can only be 0 or 1]
 137     //   <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
 138     //   [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
 139     //   <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
 140     //   [Multiplying both sides of the equations by pr.z^2 mod p]
 141     //   <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
 142     //
 143     // Thus, we can avoid the inversion, but we have to check both cases separately.
 144     // secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
 145     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 146         // xr.x == xr * xr.z^2 mod p, so the signature is valid.
 147         return 1;
 148     }
 149     if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
 150         // xr + p >= n, so we can skip testing the second case.
 151         return 0;
 152     }
 153     secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
 154     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 155         // (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid.
 156         return 1;
 157     }
 158     return 0;
 159 }
 160
 161 static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
 162     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
 163         return 0;
 164
 165     unsigned char brx[32];
 166     secp256k1_scalar_get_b32(brx, &sig->r);
 167     secp256k1_fe_t fx;
 168     VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
 169     if (recid & 2) {
 170         if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
 171             return 0;
 172         secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
 173     }
 174     secp256k1_ge_t x;
 175     if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
 176         return 0;
 177     secp256k1_gej_t xj;
 178     secp256k1_gej_set_ge(&xj, &x);
 179     secp256k1_scalar_t rn, u1, u2;
 180     secp256k1_scalar_inverse_var(&rn, &sig->r);
 181     secp256k1_scalar_mul(&u1, &rn, message);
 182     secp256k1_scalar_negate(&u1, &u1);
 183     secp256k1_scalar_mul(&u2, &rn, &sig->s);
 184     secp256k1_gej_t qj;
 185     secp256k1_ecmult(&qj, &xj, &u2, &u1);
 186     secp256k1_ge_set_gej_var(pubkey, &qj);
 187     return !secp256k1_gej_is_infinity(&qj);
 188 }
 189
 190 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) {
 191     secp256k1_gej_t rp;
 192     secp256k1_ecmult_gen(&rp, nonce);
 193     secp256k1_ge_t r;
 194     secp256k1_ge_set_gej(&r, &rp);
 195     unsigned char b[32];
 196     secp256k1_fe_normalize(&r.x);
 197     secp256k1_fe_normalize(&r.y);
 198     secp256k1_fe_get_b32(b, &r.x);
 199     int overflow = 0;
 200     secp256k1_scalar_set_b32(&sig->r, b, &overflow);
 201     if (recid)
 202         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
 203     secp256k1_scalar_t n;
 204     secp256k1_scalar_mul(&n, &sig->r, seckey);
 205     secp256k1_scalar_add(&n, &n, message);
 206     secp256k1_scalar_inverse(&sig->s, nonce);
 207     secp256k1_scalar_mul(&sig->s, &sig->s, &n);
 208     secp256k1_scalar_clear(&n);
 209     secp256k1_gej_clear(&rp);
 210     secp256k1_ge_clear(&r);
 211     if (secp256k1_scalar_is_zero(&sig->s))
 212         return 0;
 213     if (secp256k1_scalar_is_high(&sig->s)) {
 214         secp256k1_scalar_negate(&sig->s, &sig->s);
 215         if (recid)
 216             *recid ^= 1;
 217     }
 218     return 1;
 219 }
 220
 221 static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *r, const secp256k1_scalar_t *s) {
 222     sig->r = *r;
 223     sig->s = *s;
 224 }
 225
 226 #endif