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 #include <openssl/err.h>
17 #include <openssl/mem.h>
18
19 #include "internal.h"
20 #include "../bn/internal.h"
21 #include "../../internal.h"
22
23
ec_bignum_to_scalar(const EC_GROUP * group,EC_SCALAR * out,const BIGNUM * in)24 int ec_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
25 const BIGNUM *in) {
26 if (!bn_copy_words(out->words, group->order.width, in) ||
27 !bn_less_than_words(out->words, group->order.d, group->order.width)) {
28 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
29 return 0;
30 }
31 return 1;
32 }
33
ec_scalar_equal_vartime(const EC_GROUP * group,const EC_SCALAR * a,const EC_SCALAR * b)34 int ec_scalar_equal_vartime(const EC_GROUP *group, const EC_SCALAR *a,
35 const EC_SCALAR *b) {
36 return OPENSSL_memcmp(a->words, b->words,
37 group->order.width * sizeof(BN_ULONG)) == 0;
38 }
39
ec_scalar_is_zero(const EC_GROUP * group,const EC_SCALAR * a)40 int ec_scalar_is_zero(const EC_GROUP *group, const EC_SCALAR *a) {
41 BN_ULONG mask = 0;
42 for (int i = 0; i < group->order.width; i++) {
43 mask |= a->words[i];
44 }
45 return mask == 0;
46 }
47
ec_random_nonzero_scalar(const EC_GROUP * group,EC_SCALAR * out,const uint8_t additional_data[32])48 int ec_random_nonzero_scalar(const EC_GROUP *group, EC_SCALAR *out,
49 const uint8_t additional_data[32]) {
50 return bn_rand_range_words(out->words, 1, group->order.d, group->order.width,
51 additional_data);
52 }
53
ec_scalar_to_bytes(const EC_GROUP * group,uint8_t * out,size_t * out_len,const EC_SCALAR * in)54 void ec_scalar_to_bytes(const EC_GROUP *group, uint8_t *out, size_t *out_len,
55 const EC_SCALAR *in) {
56 size_t len = BN_num_bytes(&group->order);
57 for (size_t i = 0; i < len; i++) {
58 out[len - i - 1] = in->bytes[i];
59 }
60 *out_len = len;
61 }
62
ec_scalar_from_bytes(const EC_GROUP * group,EC_SCALAR * out,const uint8_t * in,size_t len)63 int ec_scalar_from_bytes(const EC_GROUP *group, EC_SCALAR *out,
64 const uint8_t *in, size_t len) {
65 if (len != BN_num_bytes(&group->order)) {
66 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
67 return 0;
68 }
69
70 OPENSSL_memset(out, 0, sizeof(EC_SCALAR));
71
72 for (size_t i = 0; i < len; i++) {
73 out->bytes[i] = in[len - i - 1];
74 }
75
76 if (!bn_less_than_words(out->words, group->order.d, group->order.width)) {
77 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
78 return 0;
79 }
80
81 return 1;
82 }
83
ec_scalar_reduce(const EC_GROUP * group,EC_SCALAR * out,const BN_ULONG * words,size_t num)84 void ec_scalar_reduce(const EC_GROUP *group, EC_SCALAR *out,
85 const BN_ULONG *words, size_t num) {
86 // Convert "from" Montgomery form so the value is reduced modulo the order.
87 bn_from_montgomery_small(out->words, group->order.width, words, num,
88 group->order_mont);
89 // Convert "to" Montgomery form to remove the R^-1 factor added.
90 ec_scalar_to_montgomery(group, out, out);
91 }
92
ec_scalar_add(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a,const EC_SCALAR * b)93 void ec_scalar_add(const EC_GROUP *group, EC_SCALAR *r, const EC_SCALAR *a,
94 const EC_SCALAR *b) {
95 const BIGNUM *order = &group->order;
96 BN_ULONG tmp[EC_MAX_WORDS];
97 bn_mod_add_words(r->words, a->words, b->words, order->d, tmp, order->width);
98 OPENSSL_cleanse(tmp, sizeof(tmp));
99 }
100
ec_scalar_sub(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a,const EC_SCALAR * b)101 void ec_scalar_sub(const EC_GROUP *group, EC_SCALAR *r, const EC_SCALAR *a,
102 const EC_SCALAR *b) {
103 const BIGNUM *order = &group->order;
104 BN_ULONG tmp[EC_MAX_WORDS];
105 bn_mod_sub_words(r->words, a->words, b->words, order->d, tmp, order->width);
106 OPENSSL_cleanse(tmp, sizeof(tmp));
107 }
108
ec_scalar_neg(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)109 void ec_scalar_neg(const EC_GROUP *group, EC_SCALAR *r, const EC_SCALAR *a) {
110 EC_SCALAR zero;
111 OPENSSL_memset(&zero, 0, sizeof(EC_SCALAR));
112 ec_scalar_sub(group, r, &zero, a);
113 }
114
ec_scalar_select(const EC_GROUP * group,EC_SCALAR * out,BN_ULONG mask,const EC_SCALAR * a,const EC_SCALAR * b)115 void ec_scalar_select(const EC_GROUP *group, EC_SCALAR *out, BN_ULONG mask,
116 const EC_SCALAR *a, const EC_SCALAR *b) {
117 const BIGNUM *order = &group->order;
118 bn_select_words(out->words, mask, a->words, b->words, order->width);
119 }
120
ec_scalar_to_montgomery(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)121 void ec_scalar_to_montgomery(const EC_GROUP *group, EC_SCALAR *r,
122 const EC_SCALAR *a) {
123 const BIGNUM *order = &group->order;
124 bn_to_montgomery_small(r->words, a->words, order->width, group->order_mont);
125 }
126
ec_scalar_from_montgomery(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)127 void ec_scalar_from_montgomery(const EC_GROUP *group, EC_SCALAR *r,
128 const EC_SCALAR *a) {
129 const BIGNUM *order = &group->order;
130 bn_from_montgomery_small(r->words, order->width, a->words, order->width,
131 group->order_mont);
132 }
133
ec_scalar_mul_montgomery(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a,const EC_SCALAR * b)134 void ec_scalar_mul_montgomery(const EC_GROUP *group, EC_SCALAR *r,
135 const EC_SCALAR *a, const EC_SCALAR *b) {
136 const BIGNUM *order = &group->order;
137 bn_mod_mul_montgomery_small(r->words, a->words, b->words, order->width,
138 group->order_mont);
139 }
140
ec_simple_scalar_inv0_montgomery(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)141 void ec_simple_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
142 const EC_SCALAR *a) {
143 const BIGNUM *order = &group->order;
144 bn_mod_inverse0_prime_mont_small(r->words, a->words, order->width,
145 group->order_mont);
146 }
147
ec_simple_scalar_to_montgomery_inv_vartime(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)148 int ec_simple_scalar_to_montgomery_inv_vartime(const EC_GROUP *group,
149 EC_SCALAR *r,
150 const EC_SCALAR *a) {
151 if (ec_scalar_is_zero(group, a)) {
152 return 0;
153 }
154
155 // This implementation (in fact) runs in constant time,
156 // even though for this interface it is not mandatory.
157
158 // r = a^-1 in the Montgomery domain. This is
159 // |ec_scalar_to_montgomery| followed by |ec_scalar_inv0_montgomery|, but
160 // |ec_scalar_inv0_montgomery| followed by |ec_scalar_from_montgomery| is
161 // equivalent and slightly more efficient.
162 ec_scalar_inv0_montgomery(group, r, a);
163 ec_scalar_from_montgomery(group, r, r);
164 return 1;
165 }
166
ec_scalar_inv0_montgomery(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)167 void ec_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
168 const EC_SCALAR *a) {
169 group->meth->scalar_inv0_montgomery(group, r, a);
170 }
171
ec_scalar_to_montgomery_inv_vartime(const EC_GROUP * group,EC_SCALAR * r,const EC_SCALAR * a)172 int ec_scalar_to_montgomery_inv_vartime(const EC_GROUP *group, EC_SCALAR *r,
173 const EC_SCALAR *a) {
174 return group->meth->scalar_to_montgomery_inv_vartime(group, r, a);
175 }
176