ecdsa_impl.h (11638B)
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("haskellsecp256k1_v0_1_0_params.sage"); print(hex(N))' 20 * 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 21 */ 22 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_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("haskellsecp256k1_v0_1_0_params.sage"); print(hex(P-N))' 30 * 0x14551231950b75fc4402da1722fc9baee 31 */ 32 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_ecdsa_const_p_minus_order = SECP256K1_FE_CONST( 33 0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL 34 ); 35 36 static int haskellsecp256k1_v0_1_0_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 haskellsecp256k1_v0_1_0_der_parse_integer(haskellsecp256k1_v0_1_0_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 (haskellsecp256k1_v0_1_0_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 haskellsecp256k1_v0_1_0_scalar_set_b32(r, ra, &overflow); 133 } 134 if (overflow) { 135 haskellsecp256k1_v0_1_0_scalar_set_int(r, 0); 136 } 137 (*sig) += rlen; 138 return 1; 139 } 140 141 static int haskellsecp256k1_v0_1_0_ecdsa_sig_parse(haskellsecp256k1_v0_1_0_scalar *rr, haskellsecp256k1_v0_1_0_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 (haskellsecp256k1_v0_1_0_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 (!haskellsecp256k1_v0_1_0_der_parse_integer(rr, &sig, sigend)) { 157 return 0; 158 } 159 if (!haskellsecp256k1_v0_1_0_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 haskellsecp256k1_v0_1_0_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const haskellsecp256k1_v0_1_0_scalar* ar, const haskellsecp256k1_v0_1_0_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 haskellsecp256k1_v0_1_0_scalar_get_b32(&r[1], ar); 176 haskellsecp256k1_v0_1_0_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 haskellsecp256k1_v0_1_0_ecdsa_sig_verify(const haskellsecp256k1_v0_1_0_scalar *sigr, const haskellsecp256k1_v0_1_0_scalar *sigs, const haskellsecp256k1_v0_1_0_ge *pubkey, const haskellsecp256k1_v0_1_0_scalar *message) { 196 unsigned char c[32]; 197 haskellsecp256k1_v0_1_0_scalar sn, u1, u2; 198 #if !defined(EXHAUSTIVE_TEST_ORDER) 199 haskellsecp256k1_v0_1_0_fe xr; 200 #endif 201 haskellsecp256k1_v0_1_0_gej pubkeyj; 202 haskellsecp256k1_v0_1_0_gej pr; 203 204 if (haskellsecp256k1_v0_1_0_scalar_is_zero(sigr) || haskellsecp256k1_v0_1_0_scalar_is_zero(sigs)) { 205 return 0; 206 } 207 208 haskellsecp256k1_v0_1_0_scalar_inverse_var(&sn, sigs); 209 haskellsecp256k1_v0_1_0_scalar_mul(&u1, &sn, message); 210 haskellsecp256k1_v0_1_0_scalar_mul(&u2, &sn, sigr); 211 haskellsecp256k1_v0_1_0_gej_set_ge(&pubkeyj, pubkey); 212 haskellsecp256k1_v0_1_0_ecmult(&pr, &pubkeyj, &u2, &u1); 213 if (haskellsecp256k1_v0_1_0_gej_is_infinity(&pr)) { 214 return 0; 215 } 216 217 #if defined(EXHAUSTIVE_TEST_ORDER) 218 { 219 haskellsecp256k1_v0_1_0_scalar computed_r; 220 haskellsecp256k1_v0_1_0_ge pr_ge; 221 haskellsecp256k1_v0_1_0_ge_set_gej(&pr_ge, &pr); 222 haskellsecp256k1_v0_1_0_fe_normalize(&pr_ge.x); 223 224 haskellsecp256k1_v0_1_0_fe_get_b32(c, &pr_ge.x); 225 haskellsecp256k1_v0_1_0_scalar_set_b32(&computed_r, c, NULL); 226 return haskellsecp256k1_v0_1_0_scalar_eq(sigr, &computed_r); 227 } 228 #else 229 haskellsecp256k1_v0_1_0_scalar_get_b32(c, sigr); 230 /* we can ignore the fe_set_b32_limit return value, because we know the input is in range */ 231 (void)haskellsecp256k1_v0_1_0_fe_set_b32_limit(&xr, c); 232 233 /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n) 234 * in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p), 235 * compute the remainder modulo n, and compare it to xr. However: 236 * 237 * xr == X(pr) mod n 238 * <=> exists h. (xr + h * n < p && xr + h * n == X(pr)) 239 * [Since 2 * n > p, h can only be 0 or 1] 240 * <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr)) 241 * [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p] 242 * <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p) 243 * [Multiplying both sides of the equations by pr.z^2 mod p] 244 * <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x) 245 * 246 * Thus, we can avoid the inversion, but we have to check both cases separately. 247 * haskellsecp256k1_v0_1_0_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test. 248 */ 249 if (haskellsecp256k1_v0_1_0_gej_eq_x_var(&xr, &pr)) { 250 /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */ 251 return 1; 252 } 253 if (haskellsecp256k1_v0_1_0_fe_cmp_var(&xr, &haskellsecp256k1_v0_1_0_ecdsa_const_p_minus_order) >= 0) { 254 /* xr + n >= p, so we can skip testing the second case. */ 255 return 0; 256 } 257 haskellsecp256k1_v0_1_0_fe_add(&xr, &haskellsecp256k1_v0_1_0_ecdsa_const_order_as_fe); 258 if (haskellsecp256k1_v0_1_0_gej_eq_x_var(&xr, &pr)) { 259 /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */ 260 return 1; 261 } 262 return 0; 263 #endif 264 } 265 266 static int haskellsecp256k1_v0_1_0_ecdsa_sig_sign(const haskellsecp256k1_v0_1_0_ecmult_gen_context *ctx, haskellsecp256k1_v0_1_0_scalar *sigr, haskellsecp256k1_v0_1_0_scalar *sigs, const haskellsecp256k1_v0_1_0_scalar *seckey, const haskellsecp256k1_v0_1_0_scalar *message, const haskellsecp256k1_v0_1_0_scalar *nonce, int *recid) { 267 unsigned char b[32]; 268 haskellsecp256k1_v0_1_0_gej rp; 269 haskellsecp256k1_v0_1_0_ge r; 270 haskellsecp256k1_v0_1_0_scalar n; 271 int overflow = 0; 272 int high; 273 274 haskellsecp256k1_v0_1_0_ecmult_gen(ctx, &rp, nonce); 275 haskellsecp256k1_v0_1_0_ge_set_gej(&r, &rp); 276 haskellsecp256k1_v0_1_0_fe_normalize(&r.x); 277 haskellsecp256k1_v0_1_0_fe_normalize(&r.y); 278 haskellsecp256k1_v0_1_0_fe_get_b32(b, &r.x); 279 haskellsecp256k1_v0_1_0_scalar_set_b32(sigr, b, &overflow); 280 if (recid) { 281 /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log 282 * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria. 283 */ 284 *recid = (overflow << 1) | haskellsecp256k1_v0_1_0_fe_is_odd(&r.y); 285 } 286 haskellsecp256k1_v0_1_0_scalar_mul(&n, sigr, seckey); 287 haskellsecp256k1_v0_1_0_scalar_add(&n, &n, message); 288 haskellsecp256k1_v0_1_0_scalar_inverse(sigs, nonce); 289 haskellsecp256k1_v0_1_0_scalar_mul(sigs, sigs, &n); 290 haskellsecp256k1_v0_1_0_scalar_clear(&n); 291 haskellsecp256k1_v0_1_0_gej_clear(&rp); 292 haskellsecp256k1_v0_1_0_ge_clear(&r); 293 high = haskellsecp256k1_v0_1_0_scalar_is_high(sigs); 294 haskellsecp256k1_v0_1_0_scalar_cond_negate(sigs, high); 295 if (recid) { 296 *recid ^= high; 297 } 298 /* P.x = order is on the curve, so technically sig->r could end up being zero, which would be an invalid signature. 299 * This is cryptographically unreachable as hitting it requires finding the discrete log of P.x = N. 300 */ 301 return (int)(!haskellsecp256k1_v0_1_0_scalar_is_zero(sigr)) & (int)(!haskellsecp256k1_v0_1_0_scalar_is_zero(sigs)); 302 } 303 304 #endif /* SECP256K1_ECDSA_IMPL_H */