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_scalar_t *rr, secp256k1_scalar_t *rs, 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) {
  57         return 0;
  58     }
  59     lenr = sig[3];
  60     if (5+lenr >= size) {
  61         return 0;
  62     }
  63     lens = sig[lenr+5];
  64     if (sig[1] != lenr+lens+4) {
  65         return 0;
  66     }
  67     if (lenr+lens+6 > size) {
  68         return 0;
  69     }
  70     if (sig[2] != 0x02) {
  71         return 0;
  72     }
  73     if (lenr == 0) {
  74         return 0;
  75     }
  76     if (sig[lenr+4] != 0x02) {
  77         return 0;
  78     }
  79     if (lens == 0) {
  80         return 0;
  81     }
  82     sp = sig + 6 + lenr;
  83     while (lens > 0 && sp[0] == 0) {
  84         lens--;
  85         sp++;
  86     }
  87     if (lens > 32) {
  88         return 0;
  89     }
  90     rp = sig + 4;
  91     while (lenr > 0 && rp[0] == 0) {
  92         lenr--;
  93         rp++;
  94     }
  95     if (lenr > 32) {
  96         return 0;
  97     }
  98     memcpy(ra + 32 - lenr, rp, lenr);
  99     memcpy(sa + 32 - lens, sp, lens);
 100     overflow = 0;
 101     secp256k1_scalar_set_b32(rr, ra, &overflow);
 102     if (overflow) {
 103         return 0;
 104     }
 105     secp256k1_scalar_set_b32(rs, sa, &overflow);
 106     if (overflow) {
 107         return 0;
 108     }
 109     return 1;
 110 }
 111
 112 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_scalar_t* ar, const secp256k1_scalar_t* as) {
 113     unsigned char r[33] = {0}, s[33] = {0};
 114     unsigned char *rp = r, *sp = s;
 115     int lenR = 33, lenS = 33;
 116     secp256k1_scalar_get_b32(&r[1], ar);
 117     secp256k1_scalar_get_b32(&s[1], as);
 118     while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
 119     while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
 120     if (*size < 6+lenS+lenR) {
 121         *size = 6 + lenS + lenR;
 122         return 0;
 123     }
 124     *size = 6 + lenS + lenR;
 125     sig[0] = 0x30;
 126     sig[1] = 4 + lenS + lenR;
 127     sig[2] = 0x02;
 128     sig[3] = lenR;
 129     memcpy(sig+4, rp, lenR);
 130     sig[4+lenR] = 0x02;
 131     sig[5+lenR] = lenS;
 132     memcpy(sig+lenR+6, sp, lenS);
 133     return 1;
 134 }
 135
 136 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t *ctx, const secp256k1_scalar_t *sigr, const secp256k1_scalar_t *sigs, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
 137     unsigned char c[32];
 138     secp256k1_scalar_t sn, u1, u2;
 139     secp256k1_fe_t xr;
 140     secp256k1_gej_t pubkeyj;
 141     secp256k1_gej_t pr;
 142
 143     if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
 144         return 0;
 145     }
 146
 147     secp256k1_scalar_inverse_var(&sn, sigs);
 148     secp256k1_scalar_mul(&u1, &sn, message);
 149     secp256k1_scalar_mul(&u2, &sn, sigr);
 150     secp256k1_gej_set_ge(&pubkeyj, pubkey);
 151     secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
 152     if (secp256k1_gej_is_infinity(&pr)) {
 153         return 0;
 154     }
 155     secp256k1_scalar_get_b32(c, sigr);
 156     secp256k1_fe_set_b32(&xr, c);
 157
 158     /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
 159      *  in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
 160      *  compute the remainder modulo n, and compare it to xr. However:
 161      *
 162      *        xr == X(pr) mod n
 163      *    <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
 164      *    [Since 2 * n > p, h can only be 0 or 1]
 165      *    <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
 166      *    [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
 167      *    <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
 168      *    [Multiplying both sides of the equations by pr.z^2 mod p]
 169      *    <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
 170      *
 171      *  Thus, we can avoid the inversion, but we have to check both cases separately.
 172      *  secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
 173      */
 174     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 175         /* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
 176         return 1;
 177     }
 178     if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
 179         /* xr + p >= n, so we can skip testing the second case. */
 180         return 0;
 181     }
 182     secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
 183     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
 184         /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
 185         return 1;
 186     }
 187     return 0;
 188 }
 189
 190 static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context_t *ctx, const secp256k1_scalar_t *sigr, const secp256k1_scalar_t* sigs, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
 191     unsigned char brx[32];
 192     secp256k1_fe_t fx;
 193     secp256k1_ge_t x;
 194     secp256k1_gej_t xj;
 195     secp256k1_scalar_t rn, u1, u2;
 196     secp256k1_gej_t qj;
 197
 198     if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
 199         return 0;
 200     }
 201
 202     secp256k1_scalar_get_b32(brx, sigr);
 203     VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
 204     if (recid & 2) {
 205         if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
 206             return 0;
 207         }
 208         secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
 209     }
 210     if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
 211         return 0;
 212     }
 213     secp256k1_gej_set_ge(&xj, &x);
 214     secp256k1_scalar_inverse_var(&rn, sigr);
 215     secp256k1_scalar_mul(&u1, &rn, message);
 216     secp256k1_scalar_negate(&u1, &u1);
 217     secp256k1_scalar_mul(&u2, &rn, sigs);
 218     secp256k1_ecmult(ctx, &qj, &xj, &u2, &u1);
 219     secp256k1_ge_set_gej_var(pubkey, &qj);
 220     return !secp256k1_gej_is_infinity(&qj);
 221 }
 222
 223 static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context_t *ctx, secp256k1_scalar_t *sigr, secp256k1_scalar_t *sigs, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
 224     unsigned char b[32];
 225     secp256k1_gej_t rp;
 226     secp256k1_ge_t r;
 227     secp256k1_scalar_t n;
 228     int overflow = 0;
 229
 230     secp256k1_ecmult_gen(ctx, &rp, nonce);
 231     secp256k1_ge_set_gej(&r, &rp);
 232     secp256k1_fe_normalize(&r.x);
 233     secp256k1_fe_normalize(&r.y);
 234     secp256k1_fe_get_b32(b, &r.x);
 235     secp256k1_scalar_set_b32(sigr, b, &overflow);
 236     if (secp256k1_scalar_is_zero(sigr)) {
 237         /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
 238         secp256k1_gej_clear(&rp);
 239         secp256k1_ge_clear(&r);
 240         return 0;
 241     }
 242     if (recid) {
 243         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
 244     }
 245     secp256k1_scalar_mul(&n, sigr, seckey);
 246     secp256k1_scalar_add(&n, &n, message);
 247     secp256k1_scalar_inverse(sigs, nonce);
 248     secp256k1_scalar_mul(sigs, sigs, &n);
 249     secp256k1_scalar_clear(&n);
 250     secp256k1_gej_clear(&rp);
 251     secp256k1_ge_clear(&r);
 252     if (secp256k1_scalar_is_zero(sigs)) {
 253         return 0;
 254     }
 255     if (secp256k1_scalar_is_high(sigs)) {
 256         secp256k1_scalar_negate(sigs, sigs);
 257         if (recid) {
 258             *recid ^= 1;
 259         }
 260     }
 261     return 1;
 262 }
 263
 264 #endif