1 /* 2 * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be 13 * included in all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 #include "inner.h" 26 27 #define I15_LEN ((BR_MAX_EC_SIZE + 29) / 15) 28 #define POINT_LEN (1 + (((BR_MAX_EC_SIZE + 7) >> 3) << 1)) 29 #define ORDER_LEN ((BR_MAX_EC_SIZE + 7) >> 3) 30 31 /* see bearssl_ec.h */ 32 size_t 33 br_ecdsa_i15_sign_raw(const br_ec_impl *impl, 34 const br_hash_class *hf, const void *hash_value, 35 const br_ec_private_key *sk, void *sig) 36 { 37 /* 38 * IMPORTANT: this code is fit only for curves with a prime 39 * order. This is needed so that modular reduction of the X 40 * coordinate of a point can be done with a simple subtraction. 41 * We also rely on the last byte of the curve order to be distinct 42 * from 0 and 1. 43 */ 44 const br_ec_curve_def *cd; 45 uint16_t n[I15_LEN], r[I15_LEN], s[I15_LEN], x[I15_LEN]; 46 uint16_t m[I15_LEN], k[I15_LEN], t1[I15_LEN], t2[I15_LEN]; 47 unsigned char tt[ORDER_LEN << 1]; 48 unsigned char eU[POINT_LEN]; 49 size_t hash_len, nlen, ulen; 50 uint16_t n0i; 51 uint32_t ctl; 52 br_hmac_drbg_context drbg; 53 54 /* 55 * If the curve is not supported, then exit with an error. 56 */ 57 if (((impl->supported_curves >> sk->curve) & 1) == 0) { 58 return 0; 59 } 60 61 /* 62 * Get the curve parameters (generator and order). 63 */ 64 switch (sk->curve) { 65 case BR_EC_secp256r1: 66 cd = &br_secp256r1; 67 break; 68 case BR_EC_secp384r1: 69 cd = &br_secp384r1; 70 break; 71 case BR_EC_secp521r1: 72 cd = &br_secp521r1; 73 break; 74 default: 75 return 0; 76 } 77 78 /* 79 * Get modulus. 80 */ 81 nlen = cd->order_len; 82 br_i15_decode(n, cd->order, nlen); 83 n0i = br_i15_ninv15(n[1]); 84 85 /* 86 * Get private key as an i15 integer. This also checks that the 87 * private key is well-defined (not zero, and less than the 88 * curve order). 89 */ 90 if (!br_i15_decode_mod(x, sk->x, sk->xlen, n)) { 91 return 0; 92 } 93 if (br_i15_iszero(x)) { 94 return 0; 95 } 96 97 /* 98 * Get hash length. 99 */ 100 hash_len = (hf->desc >> BR_HASHDESC_OUT_OFF) & BR_HASHDESC_OUT_MASK; 101 102 /* 103 * Truncate and reduce the hash value modulo the curve order. 104 */ 105 br_ecdsa_i15_bits2int(m, hash_value, hash_len, n[0]); 106 br_i15_sub(m, n, br_i15_sub(m, n, 0) ^ 1); 107 108 /* 109 * RFC 6979 generation of the "k" value. 110 * 111 * The process uses HMAC_DRBG (with the hash function used to 112 * process the message that is to be signed). The seed is the 113 * concatenation of the encodings of the private key and 114 * the hash value (after truncation and modular reduction). 115 */ 116 br_i15_encode(tt, nlen, x); 117 br_i15_encode(tt + nlen, nlen, m); 118 br_hmac_drbg_init(&drbg, hf, tt, nlen << 1); 119 for (;;) { 120 br_hmac_drbg_generate(&drbg, tt, nlen); 121 br_ecdsa_i15_bits2int(k, tt, nlen, n[0]); 122 if (br_i15_iszero(k)) { 123 continue; 124 } 125 if (br_i15_sub(k, n, 0)) { 126 break; 127 } 128 } 129 130 /* 131 * Compute k*G and extract the X coordinate, then reduce it 132 * modulo the curve order. Since we support only curves with 133 * prime order, that reduction is only a matter of computing 134 * a subtraction. 135 */ 136 br_i15_encode(tt, nlen, k); 137 ulen = impl->mulgen(eU, tt, nlen, sk->curve); 138 br_i15_zero(r, n[0]); 139 br_i15_decode(r, &eU[1], ulen >> 1); 140 r[0] = n[0]; 141 br_i15_sub(r, n, br_i15_sub(r, n, 0) ^ 1); 142 143 /* 144 * Compute 1/k in double-Montgomery representation. We do so by 145 * first converting _from_ Montgomery representation (twice), 146 * then using a modular exponentiation. 147 */ 148 br_i15_from_monty(k, n, n0i); 149 br_i15_from_monty(k, n, n0i); 150 memcpy(tt, cd->order, nlen); 151 tt[nlen - 1] -= 2; 152 br_i15_modpow(k, tt, nlen, n, n0i, t1, t2); 153 154 /* 155 * Compute s = (m+xr)/k (mod n). 156 * The k[] array contains R^2/k (double-Montgomery representation); 157 * we thus can use direct Montgomery multiplications and conversions 158 * from Montgomery, avoiding any call to br_i15_to_monty() (which 159 * is slower). 160 */ 161 br_i15_from_monty(m, n, n0i); 162 br_i15_montymul(t1, x, r, n, n0i); 163 ctl = br_i15_add(t1, m, 1); 164 ctl |= br_i15_sub(t1, n, 0) ^ 1; 165 br_i15_sub(t1, n, ctl); 166 br_i15_montymul(s, t1, k, n, n0i); 167 168 /* 169 * Encode r and s in the signature. 170 */ 171 br_i15_encode(sig, nlen, r); 172 br_i15_encode((unsigned char *)sig + nlen, nlen, s); 173 return nlen << 1; 174 } 175