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 static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
  19     0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
  20     0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
  21 );
  22
  23 static const secp256k1_fe_t secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
  24     0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
  25 );
  26
  27 static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
  28     unsigned char ra[32] = {0}, sa[32] = {0};
  29     const unsigned char *rp;
  30     const unsigned char *sp;
  31     int lenr;
  32     int lens;
  33     int overflow;
  34     if (sig[0] != 0x30) return 0;
  35     lenr = sig[3];
  36     if (5+lenr >= size) return 0;
  37     lens = sig[lenr+5];
  38     if (sig[1] != lenr+lens+4) return 0;
  39     if (lenr+lens+6 > size) return 0;
  40     if (sig[2] != 0x02) return 0;
  41     if (lenr == 0) return 0;
  42     if (sig[lenr+4] != 0x02) return 0;
  43     if (lens == 0) return 0;
  44     sp = sig + 6 + lenr;
  45     while (lens > 0 && sp[0] == 0) {
  46         lens--;
  47         sp++;
  48     }
  49     if (lens > 32) return 0;
  50     rp = sig + 4;
  51     while (lenr > 0 && rp[0] == 0) {
  52         lenr--;
  53         rp++;
  54     }
  55     if (lenr > 32) return 0;
  56     memcpy(ra + 32 - lenr, rp, lenr);
  57     memcpy(sa + 32 - lens, sp, lens);
  58     overflow = 0;
  59     secp256k1_scalar_set_b32(&r->r, ra, &overflow);
  60     if (overflow) return 0;
  61     secp256k1_scalar_set_b32(&r->s, sa, &overflow);
  62     if (overflow) return 0;
  63     return 1;
  64 }
  65
  66 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
  67     unsigned char r[33] = {0}, s[33] = {0};
  68     unsigned char *rp = r, *sp = s;
  69     int lenR = 33, lenS = 33;
  70     secp256k1_scalar_get_b32(&r[1], &a->r);
  71     secp256k1_scalar_get_b32(&s[1], &a->s);
  72     while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
  73     while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
  74     if (*size < 6+lenS+lenR)
  75         return 0;
  76     *size = 6 + lenS + lenR;
  77     sig[0] = 0x30;
  78     sig[1] = 4 + lenS + lenR;
  79     sig[2] = 0x02;
  80     sig[3] = lenR;
  81     memcpy(sig+4, rp, lenR);
  82     sig[4+lenR] = 0x02;
  83     sig[5+lenR] = lenS;
  84     memcpy(sig+lenR+6, sp, lenS);
  85     return 1;
  86 }
  87
  88 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
  89     unsigned char c[32];
  90     secp256k1_scalar_t sn, u1, u2;
  91     secp256k1_fe_t xr;
  92     secp256k1_gej_t pubkeyj;
  93     secp256k1_gej_t pr;
  94
  95     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
  96         return 0;
  97
  98     secp256k1_scalar_inverse_var(&sn, &sig->s);
  99     secp256k1_scalar_mul(&u1, &sn, message);
 100     secp256k1_scalar_mul(&u2, &sn, &sig->r);
 101     secp256k1_gej_set_ge(&pubkeyj, pubkey);
 102     secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
 103     if (secp256k1_gej_is_infinity(&pr)) {
 104         return 0;
 105     }
 106     secp256k1_scalar_get_b32(c, &sig->r);
 107     secp256k1_fe_set_b32(&xr, c);
 108
 109     /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
 110      *  in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
 111      *  compute the remainder modulo n, and compare it to xr. However:
 112      *
 113      *        xr == X(pr) mod n
 114      *    <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
 115      *    [Since 2 * n > p, h can only be 0 or 1]
 116      *    <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
 117      *    [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
 118      *    <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
 119      *    [Multiplying both sides of the equations by pr.z^2 mod p]
 120      *    <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
 121      *
 122      *  Thus, we can avoid the inversion, but we have to check both cases separately.
 123      *  secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
 124      */
 125     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 126         /* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
 127         return 1;
 128     }
 129     if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
 130         /* xr + p >= n, so we can skip testing the second case. */
 131         return 0;
 132     }
 133     secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
 134     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 135         /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
 136         return 1;
 137     }
 138     return 0;
 139 }
 140
 141 static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
 142     unsigned char brx[32];
 143     secp256k1_fe_t fx;
 144     secp256k1_ge_t x;
 145     secp256k1_gej_t xj;
 146     secp256k1_scalar_t rn, u1, u2;
 147     secp256k1_gej_t qj;
 148
 149     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
 150         return 0;
 151
 152     secp256k1_scalar_get_b32(brx, &sig->r);
 153     VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
 154     if (recid & 2) {
 155         if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0)
 156             return 0;
 157         secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
 158     }
 159     if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
 160         return 0;
 161     secp256k1_gej_set_ge(&xj, &x);
 162     secp256k1_scalar_inverse_var(&rn, &sig->r);
 163     secp256k1_scalar_mul(&u1, &rn, message);
 164     secp256k1_scalar_negate(&u1, &u1);
 165     secp256k1_scalar_mul(&u2, &rn, &sig->s);
 166     secp256k1_ecmult(&qj, &xj, &u2, &u1);
 167     secp256k1_ge_set_gej_var(pubkey, &qj);
 168     return !secp256k1_gej_is_infinity(&qj);
 169 }
 170
 171 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) {
 172     unsigned char b[32];
 173     secp256k1_gej_t rp;
 174     secp256k1_ge_t r;
 175     secp256k1_scalar_t n;
 176     int overflow = 0;
 177
 178     secp256k1_ecmult_gen(&rp, nonce);
 179     secp256k1_ge_set_gej(&r, &rp);
 180     secp256k1_fe_normalize(&r.x);
 181     secp256k1_fe_normalize(&r.y);
 182     secp256k1_fe_get_b32(b, &r.x);
 183     secp256k1_scalar_set_b32(&sig->r, b, &overflow);
 184     if (secp256k1_scalar_is_zero(&sig->r)) {
 185         /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
 186         secp256k1_gej_clear(&rp);
 187         secp256k1_ge_clear(&r);
 188         return 0;
 189     }
 190     if (recid)
 191         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
 192     secp256k1_scalar_mul(&n, &sig->r, seckey);
 193     secp256k1_scalar_add(&n, &n, message);
 194     secp256k1_scalar_inverse(&sig->s, nonce);
 195     secp256k1_scalar_mul(&sig->s, &sig->s, &n);
 196     secp256k1_scalar_clear(&n);
 197     secp256k1_gej_clear(&rp);
 198     secp256k1_ge_clear(&r);
 199     if (secp256k1_scalar_is_zero(&sig->s))
 200         return 0;
 201     if (secp256k1_scalar_is_high(&sig->s)) {
 202         secp256k1_scalar_negate(&sig->s, &sig->s);
 203         if (recid)
 204             *recid ^= 1;
 205     }
 206     return 1;
 207 }
 208
 209 #endif