1/* Copyright 2018 The BoringSSL Authors 2 * 3 * Permission to use, copy, modify, and/or distribute this software for any 4 * purpose with or without fee is hereby granted, provided that the above 5 * copyright notice and this permission notice appear in all copies. 6 * 7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 14 15#include <openssl/ec.h> 16 17#include <assert.h> 18 19#include "internal.h" 20#include "../bn/internal.h" 21#include "../../internal.h" 22 23 24void ec_GFp_mont_mul(const EC_GROUP *group, EC_JACOBIAN *r, 25 const EC_JACOBIAN *p, const EC_SCALAR *scalar) { 26 // This is a generic implementation for uncommon curves that not do not 27 // warrant a tuned one. It uses unsigned digits so that the doubling case in 28 // |ec_GFp_mont_add| is always unreachable, erring on safety and simplicity. 29 30 // Compute a table of the first 32 multiples of |p| (including infinity). 31 EC_JACOBIAN precomp[32]; 32 ec_GFp_simple_point_set_to_infinity(group, &precomp[0]); 33 ec_GFp_simple_point_copy(&precomp[1], p); 34 for (size_t j = 2; j < OPENSSL_ARRAY_SIZE(precomp); j++) { 35 if (j & 1) { 36 ec_GFp_mont_add(group, &precomp[j], &precomp[1], &precomp[j - 1]); 37 } else { 38 ec_GFp_mont_dbl(group, &precomp[j], &precomp[j / 2]); 39 } 40 } 41 42 // Divide bits in |scalar| into windows. 43 unsigned bits = EC_GROUP_order_bits(group); 44 int r_is_at_infinity = 1; 45 for (unsigned i = bits - 1; i < bits; i--) { 46 if (!r_is_at_infinity) { 47 ec_GFp_mont_dbl(group, r, r); 48 } 49 if (i % 5 == 0) { 50 // Compute the next window value. 51 const size_t width = group->order.N.width; 52 uint8_t window = bn_is_bit_set_words(scalar->words, width, i + 4) << 4; 53 window |= bn_is_bit_set_words(scalar->words, width, i + 3) << 3; 54 window |= bn_is_bit_set_words(scalar->words, width, i + 2) << 2; 55 window |= bn_is_bit_set_words(scalar->words, width, i + 1) << 1; 56 window |= bn_is_bit_set_words(scalar->words, width, i); 57 58 // Select the entry in constant-time. 59 EC_JACOBIAN tmp; 60 OPENSSL_memset(&tmp, 0, sizeof(EC_JACOBIAN)); 61 for (size_t j = 0; j < OPENSSL_ARRAY_SIZE(precomp); j++) { 62 BN_ULONG mask = constant_time_eq_w(j, window); 63 ec_point_select(group, &tmp, mask, &precomp[j], &tmp); 64 } 65 66 if (r_is_at_infinity) { 67 ec_GFp_simple_point_copy(r, &tmp); 68 r_is_at_infinity = 0; 69 } else { 70 ec_GFp_mont_add(group, r, r, &tmp); 71 } 72 } 73 } 74 if (r_is_at_infinity) { 75 ec_GFp_simple_point_set_to_infinity(group, r); 76 } 77} 78 79void ec_GFp_mont_mul_base(const EC_GROUP *group, EC_JACOBIAN *r, 80 const EC_SCALAR *scalar) { 81 ec_GFp_mont_mul(group, r, &group->generator.raw, scalar); 82} 83 84static void ec_GFp_mont_batch_precomp(const EC_GROUP *group, EC_JACOBIAN *out, 85 size_t num, const EC_JACOBIAN *p) { 86 assert(num > 1); 87 ec_GFp_simple_point_set_to_infinity(group, &out[0]); 88 ec_GFp_simple_point_copy(&out[1], p); 89 for (size_t j = 2; j < num; j++) { 90 if (j & 1) { 91 ec_GFp_mont_add(group, &out[j], &out[1], &out[j - 1]); 92 } else { 93 ec_GFp_mont_dbl(group, &out[j], &out[j / 2]); 94 } 95 } 96} 97 98static void ec_GFp_mont_batch_get_window(const EC_GROUP *group, 99 EC_JACOBIAN *out, 100 const EC_JACOBIAN precomp[17], 101 const EC_SCALAR *scalar, unsigned i) { 102 const size_t width = group->order.N.width; 103 uint8_t window = bn_is_bit_set_words(scalar->words, width, i + 4) << 5; 104 window |= bn_is_bit_set_words(scalar->words, width, i + 3) << 4; 105 window |= bn_is_bit_set_words(scalar->words, width, i + 2) << 3; 106 window |= bn_is_bit_set_words(scalar->words, width, i + 1) << 2; 107 window |= bn_is_bit_set_words(scalar->words, width, i) << 1; 108 if (i > 0) { 109 window |= bn_is_bit_set_words(scalar->words, width, i - 1); 110 } 111 crypto_word_t sign, digit; 112 ec_GFp_nistp_recode_scalar_bits(&sign, &digit, window); 113 114 // Select the entry in constant-time. 115 OPENSSL_memset(out, 0, sizeof(EC_JACOBIAN)); 116 for (size_t j = 0; j < 17; j++) { 117 BN_ULONG mask = constant_time_eq_w(j, digit); 118 ec_point_select(group, out, mask, &precomp[j], out); 119 } 120 121 // Negate if necessary. 122 EC_FELEM neg_Y; 123 ec_felem_neg(group, &neg_Y, &out->Y); 124 crypto_word_t sign_mask = sign; 125 sign_mask = 0u - sign_mask; 126 ec_felem_select(group, &out->Y, sign_mask, &neg_Y, &out->Y); 127} 128 129void ec_GFp_mont_mul_batch(const EC_GROUP *group, EC_JACOBIAN *r, 130 const EC_JACOBIAN *p0, const EC_SCALAR *scalar0, 131 const EC_JACOBIAN *p1, const EC_SCALAR *scalar1, 132 const EC_JACOBIAN *p2, const EC_SCALAR *scalar2) { 133 EC_JACOBIAN precomp[3][17]; 134 ec_GFp_mont_batch_precomp(group, precomp[0], 17, p0); 135 ec_GFp_mont_batch_precomp(group, precomp[1], 17, p1); 136 if (p2 != NULL) { 137 ec_GFp_mont_batch_precomp(group, precomp[2], 17, p2); 138 } 139 140 // Divide bits in |scalar| into windows. 141 unsigned bits = EC_GROUP_order_bits(group); 142 int r_is_at_infinity = 1; 143 for (unsigned i = bits; i <= bits; i--) { 144 if (!r_is_at_infinity) { 145 ec_GFp_mont_dbl(group, r, r); 146 } 147 if (i % 5 == 0) { 148 EC_JACOBIAN tmp; 149 ec_GFp_mont_batch_get_window(group, &tmp, precomp[0], scalar0, i); 150 if (r_is_at_infinity) { 151 ec_GFp_simple_point_copy(r, &tmp); 152 r_is_at_infinity = 0; 153 } else { 154 ec_GFp_mont_add(group, r, r, &tmp); 155 } 156 157 ec_GFp_mont_batch_get_window(group, &tmp, precomp[1], scalar1, i); 158 ec_GFp_mont_add(group, r, r, &tmp); 159 160 if (p2 != NULL) { 161 ec_GFp_mont_batch_get_window(group, &tmp, precomp[2], scalar2, i); 162 ec_GFp_mont_add(group, r, r, &tmp); 163 } 164 } 165 } 166 if (r_is_at_infinity) { 167 ec_GFp_simple_point_set_to_infinity(group, r); 168 } 169} 170 171static unsigned ec_GFp_mont_comb_stride(const EC_GROUP *group) { 172 return (EC_GROUP_get_degree(group) + EC_MONT_PRECOMP_COMB_SIZE - 1) / 173 EC_MONT_PRECOMP_COMB_SIZE; 174} 175 176int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out, 177 const EC_JACOBIAN *p) { 178 // comb[i - 1] stores the ith element of the comb. That is, if i is 179 // b4 * 2^4 + b3 * 2^3 + ... + b0 * 2^0, it stores k * |p|, where k is 180 // b4 * 2^(4*stride) + b3 * 2^(3*stride) + ... + b0 * 2^(0*stride). stride 181 // here is |ec_GFp_mont_comb_stride|. We store at index i - 1 because the 0th 182 // comb entry is always infinity. 183 EC_JACOBIAN comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1]; 184 unsigned stride = ec_GFp_mont_comb_stride(group); 185 186 // We compute the comb sequentially by the highest set bit. Initially, all 187 // entries up to 2^0 are filled. 188 comb[(1 << 0) - 1] = *p; 189 for (unsigned i = 1; i < EC_MONT_PRECOMP_COMB_SIZE; i++) { 190 // Compute entry 2^i by doubling the entry for 2^(i-1) |stride| times. 191 unsigned bit = 1 << i; 192 ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit / 2 - 1]); 193 for (unsigned j = 1; j < stride; j++) { 194 ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit - 1]); 195 } 196 // Compute entries from 2^i + 1 to 2^i + (2^i - 1) by adding entry 2^i to 197 // a previous entry. 198 for (unsigned j = 1; j < bit; j++) { 199 ec_GFp_mont_add(group, &comb[bit + j - 1], &comb[bit - 1], &comb[j - 1]); 200 } 201 } 202 203 // Store the comb in affine coordinates to shrink the table. (This reduces 204 // cache pressure and makes the constant-time selects faster.) 205 static_assert(OPENSSL_ARRAY_SIZE(comb) == OPENSSL_ARRAY_SIZE(out->comb), 206 "comb sizes did not match"); 207 return ec_jacobian_to_affine_batch(group, out->comb, comb, 208 OPENSSL_ARRAY_SIZE(comb)); 209} 210 211static void ec_GFp_mont_get_comb_window(const EC_GROUP *group, 212 EC_JACOBIAN *out, 213 const EC_PRECOMP *precomp, 214 const EC_SCALAR *scalar, unsigned i) { 215 const size_t width = group->order.N.width; 216 unsigned stride = ec_GFp_mont_comb_stride(group); 217 // Select the bits corresponding to the comb shifted up by |i|. 218 unsigned window = 0; 219 for (unsigned j = 0; j < EC_MONT_PRECOMP_COMB_SIZE; j++) { 220 window |= bn_is_bit_set_words(scalar->words, width, j * stride + i) 221 << j; 222 } 223 224 // Select precomp->comb[window - 1]. If |window| is zero, |match| will always 225 // be zero, which will leave |out| at infinity. 226 OPENSSL_memset(out, 0, sizeof(EC_JACOBIAN)); 227 for (unsigned j = 0; j < OPENSSL_ARRAY_SIZE(precomp->comb); j++) { 228 BN_ULONG match = constant_time_eq_w(window, j + 1); 229 ec_felem_select(group, &out->X, match, &precomp->comb[j].X, &out->X); 230 ec_felem_select(group, &out->Y, match, &precomp->comb[j].Y, &out->Y); 231 } 232 BN_ULONG is_infinity = constant_time_is_zero_w(window); 233 ec_felem_select(group, &out->Z, is_infinity, &out->Z, ec_felem_one(group)); 234} 235 236void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_JACOBIAN *r, 237 const EC_PRECOMP *p0, const EC_SCALAR *scalar0, 238 const EC_PRECOMP *p1, const EC_SCALAR *scalar1, 239 const EC_PRECOMP *p2, const EC_SCALAR *scalar2) { 240 unsigned stride = ec_GFp_mont_comb_stride(group); 241 int r_is_at_infinity = 1; 242 for (unsigned i = stride - 1; i < stride; i--) { 243 if (!r_is_at_infinity) { 244 ec_GFp_mont_dbl(group, r, r); 245 } 246 247 EC_JACOBIAN tmp; 248 ec_GFp_mont_get_comb_window(group, &tmp, p0, scalar0, i); 249 if (r_is_at_infinity) { 250 ec_GFp_simple_point_copy(r, &tmp); 251 r_is_at_infinity = 0; 252 } else { 253 ec_GFp_mont_add(group, r, r, &tmp); 254 } 255 256 if (p1 != NULL) { 257 ec_GFp_mont_get_comb_window(group, &tmp, p1, scalar1, i); 258 ec_GFp_mont_add(group, r, r, &tmp); 259 } 260 261 if (p2 != NULL) { 262 ec_GFp_mont_get_comb_window(group, &tmp, p2, scalar2, i); 263 ec_GFp_mont_add(group, r, r, &tmp); 264 } 265 } 266 if (r_is_at_infinity) { 267 ec_GFp_simple_point_set_to_infinity(group, r); 268 } 269} 270