1 /* Copyright (c) 2018, Google Inc. 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 24 static void ec_GFp_mont_mul_single(const EC_GROUP *group, EC_RAW_POINT *r, 25 const EC_RAW_POINT *p, 26 const EC_SCALAR *scalar) { 27 // This is a generic implementation for uncommon curves that not do not 28 // warrant a tuned one. It uses unsigned digits so that the doubling case in 29 // |ec_GFp_mont_add| is always unreachable, erring on safety and simplicity. 30 31 // Compute a table of the first 32 multiples of |p| (including infinity). 32 EC_RAW_POINT precomp[32]; 33 ec_GFp_simple_point_set_to_infinity(group, &precomp[0]); 34 ec_GFp_simple_point_copy(&precomp[1], p); 35 for (size_t j = 2; j < OPENSSL_ARRAY_SIZE(precomp); j++) { 36 if (j & 1) { 37 ec_GFp_mont_add(group, &precomp[j], &precomp[1], &precomp[j - 1]); 38 } else { 39 ec_GFp_mont_dbl(group, &precomp[j], &precomp[j / 2]); 40 } 41 } 42 43 // Divide bits in |scalar| into windows. 44 unsigned bits = BN_num_bits(&group->order); 45 int r_is_at_infinity = 1; 46 for (unsigned i = bits - 1; i < bits; i--) { 47 if (!r_is_at_infinity) { 48 ec_GFp_mont_dbl(group, r, r); 49 } 50 if (i % 5 == 0) { 51 // Compute the next window value. 52 const size_t width = group->order.width; 53 uint8_t window = bn_is_bit_set_words(scalar->words, width, i + 4) << 4; 54 window |= bn_is_bit_set_words(scalar->words, width, i + 3) << 3; 55 window |= bn_is_bit_set_words(scalar->words, width, i + 2) << 2; 56 window |= bn_is_bit_set_words(scalar->words, width, i + 1) << 1; 57 window |= bn_is_bit_set_words(scalar->words, width, i); 58 59 // Select the entry in constant-time. 60 EC_RAW_POINT tmp; 61 OPENSSL_memset(&tmp, 0, sizeof(EC_RAW_POINT)); 62 for (size_t j = 0; j < OPENSSL_ARRAY_SIZE(precomp); j++) { 63 BN_ULONG mask = constant_time_eq_w(j, window); 64 ec_felem_select(group, &tmp.X, mask, &precomp[j].X, &tmp.X); 65 ec_felem_select(group, &tmp.Y, mask, &precomp[j].Y, &tmp.Y); 66 ec_felem_select(group, &tmp.Z, mask, &precomp[j].Z, &tmp.Z); 67 } 68 69 if (r_is_at_infinity) { 70 ec_GFp_simple_point_copy(r, &tmp); 71 r_is_at_infinity = 0; 72 } else { 73 ec_GFp_mont_add(group, r, r, &tmp); 74 } 75 } 76 } 77 if (r_is_at_infinity) { 78 ec_GFp_simple_point_set_to_infinity(group, r); 79 } 80 } 81 82 void ec_GFp_mont_mul(const EC_GROUP *group, EC_RAW_POINT *r, 83 const EC_SCALAR *g_scalar, const EC_RAW_POINT *p, 84 const EC_SCALAR *p_scalar) { 85 assert(g_scalar != NULL || p_scalar != NULL); 86 if (p_scalar == NULL) { 87 ec_GFp_mont_mul_single(group, r, &group->generator->raw, g_scalar); 88 } else if (g_scalar == NULL) { 89 ec_GFp_mont_mul_single(group, r, p, p_scalar); 90 } else { 91 // Support constant-time two-point multiplication for compatibility. This 92 // does not actually come up in keygen, ECDH, or ECDSA, so we implement it 93 // the naive way. 94 ec_GFp_mont_mul_single(group, r, &group->generator->raw, g_scalar); 95 EC_RAW_POINT tmp; 96 ec_GFp_mont_mul_single(group, &tmp, p, p_scalar); 97 ec_GFp_mont_add(group, r, r, &tmp); 98 } 99 } 100
