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
ec_GFp_mont_mul_single(const EC_GROUP * group,EC_RAW_POINT * r,const EC_RAW_POINT * p,const EC_SCALAR * scalar)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
ec_GFp_mont_mul(const EC_GROUP * group,EC_RAW_POINT * r,const EC_SCALAR * g_scalar,const EC_RAW_POINT * p,const EC_SCALAR * p_scalar)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