1 /* 2 * Copyright (c) 2016 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 I31_LEN ((BR_MAX_EC_SIZE + 61) / 31) 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_i31_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 uint32_t n[I31_LEN], r[I31_LEN], s[I31_LEN], x[I31_LEN]; 46 uint32_t m[I31_LEN], k[I31_LEN], t1[I31_LEN], t2[I31_LEN]; 47 unsigned char tt[ORDER_LEN << 1]; 48 unsigned char eU[POINT_LEN]; 49 size_t hash_len, nlen, ulen; 50 uint32_t n0i, ctl; 51 br_hmac_drbg_context drbg; 52 53 /* 54 * If the curve is not supported, then exit with an error. 55 */ 56 if (((impl->supported_curves >> sk->curve) & 1) == 0) { 57 return 0; 58 } 59 60 /* 61 * Get the curve parameters (generator and order). 62 */ 63 switch (sk->curve) { 64 case BR_EC_secp256r1: 65 cd = &br_secp256r1; 66 break; 67 case BR_EC_secp384r1: 68 cd = &br_secp384r1; 69 break; 70 case BR_EC_secp521r1: 71 cd = &br_secp521r1; 72 break; 73 default: 74 return 0; 75 } 76 77 /* 78 * Get modulus. 79 */ 80 nlen = cd->order_len; 81 br_i31_decode(n, cd->order, nlen); 82 n0i = br_i31_ninv31(n[1]); 83 84 /* 85 * Get private key as an i31 integer. This also checks that the 86 * private key is well-defined (not zero, and less than the 87 * curve order). 88 */ 89 if (!br_i31_decode_mod(x, sk->x, sk->xlen, n)) { 90 return 0; 91 } 92 if (br_i31_iszero(x)) { 93 return 0; 94 } 95 96 /* 97 * Get hash length. 98 */ 99 hash_len = (hf->desc >> BR_HASHDESC_OUT_OFF) & BR_HASHDESC_OUT_MASK; 100 101 /* 102 * Truncate and reduce the hash value modulo the curve order. 103 */ 104 br_ecdsa_i31_bits2int(m, hash_value, hash_len, n[0]); 105 br_i31_sub(m, n, br_i31_sub(m, n, 0) ^ 1); 106 107 /* 108 * RFC 6979 generation of the "k" value. 109 * 110 * The process uses HMAC_DRBG (with the hash function used to 111 * process the message that is to be signed). The seed is the 112 * concatenation of the encodings of the private key and 113 * the hash value (after truncation and modular reduction). 114 */ 115 br_i31_encode(tt, nlen, x); 116 br_i31_encode(tt + nlen, nlen, m); 117 br_hmac_drbg_init(&drbg, hf, tt, nlen << 1); 118 for (;;) { 119 br_hmac_drbg_generate(&drbg, tt, nlen); 120 br_ecdsa_i31_bits2int(k, tt, nlen, n[0]); 121 if (br_i31_iszero(k)) { 122 continue; 123 } 124 if (br_i31_sub(k, n, 0)) { 125 break; 126 } 127 } 128 129 /* 130 * Compute k*G and extract the X coordinate, then reduce it 131 * modulo the curve order. Since we support only curves with 132 * prime order, that reduction is only a matter of computing 133 * a subtraction. 134 */ 135 br_i31_encode(tt, nlen, k); 136 ulen = impl->mulgen(eU, tt, nlen, sk->curve); 137 br_i31_zero(r, n[0]); 138 br_i31_decode(r, &eU[1], ulen >> 1); 139 r[0] = n[0]; 140 br_i31_sub(r, n, br_i31_sub(r, n, 0) ^ 1); 141 142 /* 143 * Compute 1/k in double-Montgomery representation. We do so by 144 * first converting _from_ Montgomery representation (twice), 145 * then using a modular exponentiation. 146 */ 147 br_i31_from_monty(k, n, n0i); 148 br_i31_from_monty(k, n, n0i); 149 memcpy(tt, cd->order, nlen); 150 tt[nlen - 1] -= 2; 151 br_i31_modpow(k, tt, nlen, n, n0i, t1, t2); 152 153 /* 154 * Compute s = (m+xr)/k (mod n). 155 * The k[] array contains R^2/k (double-Montgomery representation); 156 * we thus can use direct Montgomery multiplications and conversions 157 * from Montgomery, avoiding any call to br_i31_to_monty() (which 158 * is slower). 159 */ 160 br_i31_from_monty(m, n, n0i); 161 br_i31_montymul(t1, x, r, n, n0i); 162 ctl = br_i31_add(t1, m, 1); 163 ctl |= br_i31_sub(t1, n, 0) ^ 1; 164 br_i31_sub(t1, n, ctl); 165 br_i31_montymul(s, t1, k, n, n0i); 166 167 /* 168 * Encode r and s in the signature. 169 */ 170 br_i31_encode(sig, nlen, r); 171 br_i31_encode((unsigned char *)sig + nlen, nlen, s); 172 return nlen << 1; 173 } 174