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