ecdsa_impl.h
1 /*********************************************************************** 2 * Copyright (c) 2013-2015 Pieter Wuille * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://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 -c 'load("secp256k1_params.sage"); print(hex(N))' 20 * 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 21 */ 22 static const secp256k1_fe secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST( 23 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 24 0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL 25 ); 26 27 /** Difference between field and order, values 'p' and 'n' values defined in 28 * "Standards for Efficient Cryptography" (SEC2) 2.7.1. 29 * $ sage -c 'load("secp256k1_params.sage"); print(hex(P-N))' 30 * 0x14551231950b75fc4402da1722fc9baee 31 */ 32 static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST( 33 0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL 34 ); 35 36 static int secp256k1_der_read_len(size_t *len, const unsigned char **sigp, const unsigned char *sigend) { 37 size_t lenleft; 38 unsigned char b1; 39 VERIFY_CHECK(len != NULL); 40 *len = 0; 41 if (*sigp >= sigend) { 42 return 0; 43 } 44 b1 = *((*sigp)++); 45 if (b1 == 0xFF) { 46 /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */ 47 return 0; 48 } 49 if ((b1 & 0x80) == 0) { 50 /* X.690-0207 8.1.3.4 short form length octets */ 51 *len = b1; 52 return 1; 53 } 54 if (b1 == 0x80) { 55 /* Indefinite length is not allowed in DER. */ 56 return 0; 57 } 58 /* X.690-207 8.1.3.5 long form length octets */ 59 lenleft = b1 & 0x7F; /* lenleft is at least 1 */ 60 if (lenleft > (size_t)(sigend - *sigp)) { 61 return 0; 62 } 63 if (**sigp == 0) { 64 /* Not the shortest possible length encoding. */ 65 return 0; 66 } 67 if (lenleft > sizeof(size_t)) { 68 /* The resulting length would exceed the range of a size_t, so 69 * it is certainly longer than the passed array size. */ 70 return 0; 71 } 72 while (lenleft > 0) { 73 *len = (*len << 8) | **sigp; 74 (*sigp)++; 75 lenleft--; 76 } 77 if (*len > (size_t)(sigend - *sigp)) { 78 /* Result exceeds the length of the passed array. 79 (Checking this is the responsibility of the caller but it 80 can't hurt do it here, too.) */ 81 return 0; 82 } 83 if (*len < 128) { 84 /* Not the shortest possible length encoding. */ 85 return 0; 86 } 87 return 1; 88 } 89 90 static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) { 91 int overflow = 0; 92 unsigned char ra[32] = {0}; 93 size_t rlen; 94 95 if (*sig == sigend || **sig != 0x02) { 96 /* Not a primitive integer (X.690-0207 8.3.1). */ 97 return 0; 98 } 99 (*sig)++; 100 if (secp256k1_der_read_len(&rlen, sig, sigend) == 0) { 101 return 0; 102 } 103 if (rlen == 0 || rlen > (size_t)(sigend - *sig)) { 104 /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1). */ 105 return 0; 106 } 107 if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) { 108 /* Excessive 0x00 padding. */ 109 return 0; 110 } 111 if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) { 112 /* Excessive 0xFF padding. */ 113 return 0; 114 } 115 if ((**sig & 0x80) == 0x80) { 116 /* Negative. */ 117 overflow = 1; 118 } 119 /* There is at most one leading zero byte: 120 * if there were two leading zero bytes, we would have failed and returned 0 121 * because of excessive 0x00 padding already. */ 122 if (rlen > 0 && **sig == 0) { 123 /* Skip leading zero byte */ 124 rlen--; 125 (*sig)++; 126 } 127 if (rlen > 32) { 128 overflow = 1; 129 } 130 if (!overflow) { 131 if (rlen) memcpy(ra + 32 - rlen, *sig, rlen); 132 secp256k1_scalar_set_b32(r, ra, &overflow); 133 } 134 if (overflow) { 135 secp256k1_scalar_set_int(r, 0); 136 } 137 (*sig) += rlen; 138 return 1; 139 } 140 141 static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) { 142 const unsigned char *sigend = sig + size; 143 size_t rlen; 144 if (sig == sigend || *(sig++) != 0x30) { 145 /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */ 146 return 0; 147 } 148 if (secp256k1_der_read_len(&rlen, &sig, sigend) == 0) { 149 return 0; 150 } 151 if (rlen != (size_t)(sigend - sig)) { 152 /* Tuple exceeds bounds or garage after tuple. */ 153 return 0; 154 } 155 156 if (!secp256k1_der_parse_integer(rr, &sig, sigend)) { 157 return 0; 158 } 159 if (!secp256k1_der_parse_integer(rs, &sig, sigend)) { 160 return 0; 161 } 162 163 if (sig != sigend) { 164 /* Trailing garbage inside tuple. */ 165 return 0; 166 } 167 168 return 1; 169 } 170 171 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const secp256k1_scalar* ar, const secp256k1_scalar* as) { 172 unsigned char r[33] = {0}, s[33] = {0}; 173 unsigned char *rp = r, *sp = s; 174 size_t lenR = 33, lenS = 33; 175 secp256k1_scalar_get_b32(&r[1], ar); 176 secp256k1_scalar_get_b32(&s[1], as); 177 while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; } 178 while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; } 179 if (*size < 6+lenS+lenR) { 180 *size = 6 + lenS + lenR; 181 return 0; 182 } 183 *size = 6 + lenS + lenR; 184 sig[0] = 0x30; 185 sig[1] = 4 + lenS + lenR; 186 sig[2] = 0x02; 187 sig[3] = lenR; 188 memcpy(sig+4, rp, lenR); 189 sig[4+lenR] = 0x02; 190 sig[5+lenR] = lenS; 191 memcpy(sig+lenR+6, sp, lenS); 192 return 1; 193 } 194 195 static int secp256k1_ecdsa_sig_verify(const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) { 196 unsigned char c[32]; 197 secp256k1_scalar sn, u1, u2; 198 #if !defined(EXHAUSTIVE_TEST_ORDER) 199 int range; 200 secp256k1_fe xr; 201 #endif 202 secp256k1_gej pubkeyj; 203 secp256k1_gej pr; 204 205 if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) { 206 return 0; 207 } 208 209 secp256k1_scalar_inverse_var(&sn, sigs); 210 secp256k1_scalar_mul(&u1, &sn, message); 211 secp256k1_scalar_mul(&u2, &sn, sigr); 212 secp256k1_gej_set_ge(&pubkeyj, pubkey); 213 secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1); 214 if (secp256k1_gej_is_infinity(&pr)) { 215 return 0; 216 } 217 218 #if defined(EXHAUSTIVE_TEST_ORDER) 219 { 220 secp256k1_scalar computed_r; 221 secp256k1_ge pr_ge; 222 secp256k1_ge_set_gej(&pr_ge, &pr); 223 secp256k1_fe_normalize(&pr_ge.x); 224 225 secp256k1_fe_get_b32(c, &pr_ge.x); 226 secp256k1_scalar_set_b32(&computed_r, c, NULL); 227 return secp256k1_scalar_eq(sigr, &computed_r); 228 } 229 #else 230 231 /* Interpret sigr as a field element xr */ 232 secp256k1_scalar_get_b32(c, sigr); 233 range = secp256k1_fe_set_b32_limit(&xr, c); 234 #ifdef VERIFY 235 /* We know that c is in range; it comes from a scalar. */ 236 VERIFY_CHECK(range); 237 #else 238 (void)range; 239 #endif 240 241 /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n) 242 * in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p), 243 * compute the remainder modulo n, and compare it to xr. However: 244 * 245 * xr == X(pr) mod n 246 * <=> exists h. (xr + h * n < p && xr + h * n == X(pr)) 247 * [Since 2 * n > p, h can only be 0 or 1] 248 * <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr)) 249 * [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p] 250 * <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p) 251 * [Multiplying both sides of the equations by pr.z^2 mod p] 252 * <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x) 253 * 254 * Thus, we can avoid the inversion, but we have to check both cases separately. 255 * secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test. 256 */ 257 if (secp256k1_gej_eq_x_var(&xr, &pr)) { 258 /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */ 259 return 1; 260 } 261 if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) { 262 /* xr + n >= p, so we can skip testing the second case. */ 263 return 0; 264 } 265 secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe); 266 if (secp256k1_gej_eq_x_var(&xr, &pr)) { 267 /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */ 268 return 1; 269 } 270 return 0; 271 #endif 272 } 273 274 static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid) { 275 unsigned char b[32]; 276 secp256k1_gej rp; 277 secp256k1_ge r; 278 secp256k1_scalar n; 279 int overflow = 0; 280 int high; 281 282 secp256k1_ecmult_gen(ctx, &rp, nonce); 283 secp256k1_ge_set_gej(&r, &rp); 284 secp256k1_fe_normalize(&r.x); 285 secp256k1_fe_normalize(&r.y); 286 secp256k1_fe_get_b32(b, &r.x); 287 secp256k1_scalar_set_b32(sigr, b, &overflow); 288 if (recid) { 289 /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log 290 * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria. 291 */ 292 *recid = (overflow << 1) | secp256k1_fe_is_odd(&r.y); 293 } 294 secp256k1_scalar_mul(&n, sigr, seckey); 295 secp256k1_scalar_add(&n, &n, message); 296 secp256k1_scalar_inverse(sigs, nonce); 297 secp256k1_scalar_mul(sigs, sigs, &n); 298 secp256k1_scalar_clear(&n); 299 secp256k1_gej_clear(&rp); 300 secp256k1_ge_clear(&r); 301 high = secp256k1_scalar_is_high(sigs); 302 secp256k1_scalar_cond_negate(sigs, high); 303 if (recid) { 304 *recid ^= high; 305 } 306 /* P.x = order is on the curve, so technically sig->r could end up being zero, which would be an invalid signature. 307 * This is cryptographically unreachable as hitting it requires finding the discrete log of P.x = N. 308 */ 309 return (int)(!secp256k1_scalar_is_zero(sigr)) & (int)(!secp256k1_scalar_is_zero(sigs)); 310 } 311 312 #endif /* SECP256K1_ECDSA_IMPL_H */