/src/boringssl/crypto/fipsmodule/ec/simple.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Originally written by Bodo Moeller for the OpenSSL project. |
2 | | * ==================================================================== |
3 | | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
4 | | * |
5 | | * Redistribution and use in source and binary forms, with or without |
6 | | * modification, are permitted provided that the following conditions |
7 | | * are met: |
8 | | * |
9 | | * 1. Redistributions of source code must retain the above copyright |
10 | | * notice, this list of conditions and the following disclaimer. |
11 | | * |
12 | | * 2. Redistributions in binary form must reproduce the above copyright |
13 | | * notice, this list of conditions and the following disclaimer in |
14 | | * the documentation and/or other materials provided with the |
15 | | * distribution. |
16 | | * |
17 | | * 3. All advertising materials mentioning features or use of this |
18 | | * software must display the following acknowledgment: |
19 | | * "This product includes software developed by the OpenSSL Project |
20 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
21 | | * |
22 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
23 | | * endorse or promote products derived from this software without |
24 | | * prior written permission. For written permission, please contact |
25 | | * openssl-core@openssl.org. |
26 | | * |
27 | | * 5. Products derived from this software may not be called "OpenSSL" |
28 | | * nor may "OpenSSL" appear in their names without prior written |
29 | | * permission of the OpenSSL Project. |
30 | | * |
31 | | * 6. Redistributions of any form whatsoever must retain the following |
32 | | * acknowledgment: |
33 | | * "This product includes software developed by the OpenSSL Project |
34 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
35 | | * |
36 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
37 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
38 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
39 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
40 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
41 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
42 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
43 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
44 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
45 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
46 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
47 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
48 | | * ==================================================================== |
49 | | * |
50 | | * This product includes cryptographic software written by Eric Young |
51 | | * (eay@cryptsoft.com). This product includes software written by Tim |
52 | | * Hudson (tjh@cryptsoft.com). |
53 | | * |
54 | | */ |
55 | | /* ==================================================================== |
56 | | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. |
57 | | * |
58 | | * Portions of the attached software ("Contribution") are developed by |
59 | | * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. |
60 | | * |
61 | | * The Contribution is licensed pursuant to the OpenSSL open source |
62 | | * license provided above. |
63 | | * |
64 | | * The elliptic curve binary polynomial software is originally written by |
65 | | * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems |
66 | | * Laboratories. */ |
67 | | |
68 | | #include <openssl/ec.h> |
69 | | |
70 | | #include <string.h> |
71 | | |
72 | | #include <openssl/bn.h> |
73 | | #include <openssl/err.h> |
74 | | #include <openssl/mem.h> |
75 | | |
76 | | #include "internal.h" |
77 | | #include "../../internal.h" |
78 | | |
79 | | |
80 | | // Most method functions in this file are designed to work with non-trivial |
81 | | // representations of field elements if necessary (see ecp_mont.c): while |
82 | | // standard modular addition and subtraction are used, the field_mul and |
83 | | // field_sqr methods will be used for multiplication, and field_encode and |
84 | | // field_decode (if defined) will be used for converting between |
85 | | // representations. |
86 | | // |
87 | | // Functions here specifically assume that if a non-trivial representation is |
88 | | // used, it is a Montgomery representation (i.e. 'encoding' means multiplying |
89 | | // by some factor R). |
90 | | |
91 | | int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p, |
92 | | const BIGNUM *a, const BIGNUM *b, |
93 | 0 | BN_CTX *ctx) { |
94 | | // p must be a prime > 3 |
95 | 0 | if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { |
96 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD); |
97 | 0 | return 0; |
98 | 0 | } |
99 | | |
100 | 0 | int ret = 0; |
101 | 0 | BN_CTX_start(ctx); |
102 | 0 | BIGNUM *tmp = BN_CTX_get(ctx); |
103 | 0 | if (tmp == NULL) { |
104 | 0 | goto err; |
105 | 0 | } |
106 | | |
107 | 0 | if (!BN_MONT_CTX_set(&group->field, p, ctx) || |
108 | 0 | !ec_bignum_to_felem(group, &group->a, a) || |
109 | 0 | !ec_bignum_to_felem(group, &group->b, b) || |
110 | | // Reuse Z from the generator to cache the value one. |
111 | 0 | !ec_bignum_to_felem(group, &group->generator.raw.Z, BN_value_one())) { |
112 | 0 | goto err; |
113 | 0 | } |
114 | | |
115 | | // group->a_is_minus3 |
116 | 0 | if (!BN_copy(tmp, a) || |
117 | 0 | !BN_add_word(tmp, 3)) { |
118 | 0 | goto err; |
119 | 0 | } |
120 | 0 | group->a_is_minus3 = (0 == BN_cmp(tmp, &group->field.N)); |
121 | |
|
122 | 0 | ret = 1; |
123 | |
|
124 | 0 | err: |
125 | 0 | BN_CTX_end(ctx); |
126 | 0 | return ret; |
127 | 0 | } |
128 | | |
129 | | int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, |
130 | 0 | BIGNUM *b) { |
131 | 0 | if ((p != NULL && !BN_copy(p, &group->field.N)) || |
132 | 0 | (a != NULL && !ec_felem_to_bignum(group, a, &group->a)) || |
133 | 0 | (b != NULL && !ec_felem_to_bignum(group, b, &group->b))) { |
134 | 0 | return 0; |
135 | 0 | } |
136 | 0 | return 1; |
137 | 0 | } |
138 | | |
139 | 976 | void ec_GFp_simple_point_init(EC_JACOBIAN *point) { |
140 | 976 | OPENSSL_memset(&point->X, 0, sizeof(EC_FELEM)); |
141 | 976 | OPENSSL_memset(&point->Y, 0, sizeof(EC_FELEM)); |
142 | 976 | OPENSSL_memset(&point->Z, 0, sizeof(EC_FELEM)); |
143 | 976 | } |
144 | | |
145 | 1.41k | void ec_GFp_simple_point_copy(EC_JACOBIAN *dest, const EC_JACOBIAN *src) { |
146 | 1.41k | OPENSSL_memcpy(&dest->X, &src->X, sizeof(EC_FELEM)); |
147 | 1.41k | OPENSSL_memcpy(&dest->Y, &src->Y, sizeof(EC_FELEM)); |
148 | 1.41k | OPENSSL_memcpy(&dest->Z, &src->Z, sizeof(EC_FELEM)); |
149 | 1.41k | } |
150 | | |
151 | | void ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, |
152 | 40 | EC_JACOBIAN *point) { |
153 | | // Although it is strictly only necessary to zero Z, we zero the entire point |
154 | | // in case |point| was stack-allocated and yet to be initialized. |
155 | 40 | ec_GFp_simple_point_init(point); |
156 | 40 | } |
157 | | |
158 | 303 | void ec_GFp_simple_invert(const EC_GROUP *group, EC_JACOBIAN *point) { |
159 | 303 | ec_felem_neg(group, &point->Y, &point->Y); |
160 | 303 | } |
161 | | |
162 | | int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, |
163 | 111 | const EC_JACOBIAN *point) { |
164 | 111 | return ec_felem_non_zero_mask(group, &point->Z) == 0; |
165 | 111 | } |
166 | | |
167 | | int ec_GFp_simple_is_on_curve(const EC_GROUP *group, |
168 | 132 | const EC_JACOBIAN *point) { |
169 | | // We have a curve defined by a Weierstrass equation |
170 | | // y^2 = x^3 + a*x + b. |
171 | | // The point to consider is given in Jacobian projective coordinates |
172 | | // where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). |
173 | | // Substituting this and multiplying by Z^6 transforms the above equation |
174 | | // into |
175 | | // Y^2 = X^3 + a*X*Z^4 + b*Z^6. |
176 | | // To test this, we add up the right-hand side in 'rh'. |
177 | | // |
178 | | // This function may be used when double-checking the secret result of a point |
179 | | // multiplication, so we proceed in constant-time. |
180 | | |
181 | 132 | void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a, |
182 | 132 | const EC_FELEM *b) = group->meth->felem_mul; |
183 | 132 | void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) = |
184 | 132 | group->meth->felem_sqr; |
185 | | |
186 | | // rh := X^2 |
187 | 132 | EC_FELEM rh; |
188 | 132 | felem_sqr(group, &rh, &point->X); |
189 | | |
190 | 132 | EC_FELEM tmp, Z4, Z6; |
191 | 132 | felem_sqr(group, &tmp, &point->Z); |
192 | 132 | felem_sqr(group, &Z4, &tmp); |
193 | 132 | felem_mul(group, &Z6, &Z4, &tmp); |
194 | | |
195 | | // rh := rh + a*Z^4 |
196 | 132 | if (group->a_is_minus3) { |
197 | 132 | ec_felem_add(group, &tmp, &Z4, &Z4); |
198 | 132 | ec_felem_add(group, &tmp, &tmp, &Z4); |
199 | 132 | ec_felem_sub(group, &rh, &rh, &tmp); |
200 | 132 | } else { |
201 | 0 | felem_mul(group, &tmp, &Z4, &group->a); |
202 | 0 | ec_felem_add(group, &rh, &rh, &tmp); |
203 | 0 | } |
204 | | |
205 | | // rh := (rh + a*Z^4)*X |
206 | 132 | felem_mul(group, &rh, &rh, &point->X); |
207 | | |
208 | | // rh := rh + b*Z^6 |
209 | 132 | felem_mul(group, &tmp, &group->b, &Z6); |
210 | 132 | ec_felem_add(group, &rh, &rh, &tmp); |
211 | | |
212 | | // 'lh' := Y^2 |
213 | 132 | felem_sqr(group, &tmp, &point->Y); |
214 | | |
215 | 132 | ec_felem_sub(group, &tmp, &tmp, &rh); |
216 | 132 | BN_ULONG not_equal = ec_felem_non_zero_mask(group, &tmp); |
217 | | |
218 | | // If Z = 0, the point is infinity, which is always on the curve. |
219 | 132 | BN_ULONG not_infinity = ec_felem_non_zero_mask(group, &point->Z); |
220 | | |
221 | 132 | return 1 & ~(not_infinity & not_equal); |
222 | 132 | } |
223 | | |
224 | | int ec_GFp_simple_points_equal(const EC_GROUP *group, const EC_JACOBIAN *a, |
225 | 3 | const EC_JACOBIAN *b) { |
226 | | // This function is implemented in constant-time for two reasons. First, |
227 | | // although EC points are usually public, their Jacobian Z coordinates may be |
228 | | // secret, or at least are not obviously public. Second, more complex |
229 | | // protocols will sometimes manipulate secret points. |
230 | | // |
231 | | // This does mean that we pay a 6M+2S Jacobian comparison when comparing two |
232 | | // publicly affine points costs no field operations at all. If needed, we can |
233 | | // restore this optimization by keeping better track of affine vs. Jacobian |
234 | | // forms. See https://crbug.com/boringssl/326. |
235 | | |
236 | | // If neither |a| or |b| is infinity, we have to decide whether |
237 | | // (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), |
238 | | // or equivalently, whether |
239 | | // (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). |
240 | | |
241 | 3 | void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a, |
242 | 3 | const EC_FELEM *b) = group->meth->felem_mul; |
243 | 3 | void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) = |
244 | 3 | group->meth->felem_sqr; |
245 | | |
246 | 3 | EC_FELEM tmp1, tmp2, Za23, Zb23; |
247 | 3 | felem_sqr(group, &Zb23, &b->Z); // Zb23 = Z_b^2 |
248 | 3 | felem_mul(group, &tmp1, &a->X, &Zb23); // tmp1 = X_a * Z_b^2 |
249 | 3 | felem_sqr(group, &Za23, &a->Z); // Za23 = Z_a^2 |
250 | 3 | felem_mul(group, &tmp2, &b->X, &Za23); // tmp2 = X_b * Z_a^2 |
251 | 3 | ec_felem_sub(group, &tmp1, &tmp1, &tmp2); |
252 | 3 | const BN_ULONG x_not_equal = ec_felem_non_zero_mask(group, &tmp1); |
253 | | |
254 | 3 | felem_mul(group, &Zb23, &Zb23, &b->Z); // Zb23 = Z_b^3 |
255 | 3 | felem_mul(group, &tmp1, &a->Y, &Zb23); // tmp1 = Y_a * Z_b^3 |
256 | 3 | felem_mul(group, &Za23, &Za23, &a->Z); // Za23 = Z_a^3 |
257 | 3 | felem_mul(group, &tmp2, &b->Y, &Za23); // tmp2 = Y_b * Z_a^3 |
258 | 3 | ec_felem_sub(group, &tmp1, &tmp1, &tmp2); |
259 | 3 | const BN_ULONG y_not_equal = ec_felem_non_zero_mask(group, &tmp1); |
260 | 3 | const BN_ULONG x_and_y_equal = ~(x_not_equal | y_not_equal); |
261 | | |
262 | 3 | const BN_ULONG a_not_infinity = ec_felem_non_zero_mask(group, &a->Z); |
263 | 3 | const BN_ULONG b_not_infinity = ec_felem_non_zero_mask(group, &b->Z); |
264 | 3 | const BN_ULONG a_and_b_infinity = ~(a_not_infinity | b_not_infinity); |
265 | | |
266 | 3 | const BN_ULONG equal = |
267 | 3 | a_and_b_infinity | (a_not_infinity & b_not_infinity & x_and_y_equal); |
268 | 3 | return equal & 1; |
269 | 3 | } |
270 | | |
271 | | int ec_affine_jacobian_equal(const EC_GROUP *group, const EC_AFFINE *a, |
272 | 0 | const EC_JACOBIAN *b) { |
273 | | // If |b| is not infinity, we have to decide whether |
274 | | // (X_a, Y_a) = (X_b/Z_b^2, Y_b/Z_b^3), |
275 | | // or equivalently, whether |
276 | | // (X_a*Z_b^2, Y_a*Z_b^3) = (X_b, Y_b). |
277 | |
|
278 | 0 | void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a, |
279 | 0 | const EC_FELEM *b) = group->meth->felem_mul; |
280 | 0 | void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) = |
281 | 0 | group->meth->felem_sqr; |
282 | |
|
283 | 0 | EC_FELEM tmp, Zb2; |
284 | 0 | felem_sqr(group, &Zb2, &b->Z); // Zb2 = Z_b^2 |
285 | 0 | felem_mul(group, &tmp, &a->X, &Zb2); // tmp = X_a * Z_b^2 |
286 | 0 | ec_felem_sub(group, &tmp, &tmp, &b->X); |
287 | 0 | const BN_ULONG x_not_equal = ec_felem_non_zero_mask(group, &tmp); |
288 | |
|
289 | 0 | felem_mul(group, &tmp, &a->Y, &Zb2); // tmp = Y_a * Z_b^2 |
290 | 0 | felem_mul(group, &tmp, &tmp, &b->Z); // tmp = Y_a * Z_b^3 |
291 | 0 | ec_felem_sub(group, &tmp, &tmp, &b->Y); |
292 | 0 | const BN_ULONG y_not_equal = ec_felem_non_zero_mask(group, &tmp); |
293 | 0 | const BN_ULONG x_and_y_equal = ~(x_not_equal | y_not_equal); |
294 | |
|
295 | 0 | const BN_ULONG b_not_infinity = ec_felem_non_zero_mask(group, &b->Z); |
296 | |
|
297 | 0 | const BN_ULONG equal = b_not_infinity & x_and_y_equal; |
298 | 0 | return equal & 1; |
299 | 0 | } |
300 | | |
301 | | int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_JACOBIAN *p, |
302 | 0 | const EC_SCALAR *r) { |
303 | 0 | if (ec_GFp_simple_is_at_infinity(group, p)) { |
304 | | // |ec_get_x_coordinate_as_scalar| will check this internally, but this way |
305 | | // we do not push to the error queue. |
306 | 0 | return 0; |
307 | 0 | } |
308 | | |
309 | 0 | EC_SCALAR x; |
310 | 0 | return ec_get_x_coordinate_as_scalar(group, &x, p) && |
311 | 0 | ec_scalar_equal_vartime(group, &x, r); |
312 | 0 | } |
313 | | |
314 | | void ec_GFp_simple_felem_to_bytes(const EC_GROUP *group, uint8_t *out, |
315 | 187 | size_t *out_len, const EC_FELEM *in) { |
316 | 187 | size_t len = BN_num_bytes(&group->field.N); |
317 | 187 | bn_words_to_big_endian(out, len, in->words, group->field.N.width); |
318 | 187 | *out_len = len; |
319 | 187 | } |
320 | | |
321 | | int ec_GFp_simple_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out, |
322 | 603 | const uint8_t *in, size_t len) { |
323 | 603 | if (len != BN_num_bytes(&group->field.N)) { |
324 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); |
325 | 0 | return 0; |
326 | 0 | } |
327 | | |
328 | 603 | bn_big_endian_to_words(out->words, group->field.N.width, in, len); |
329 | | |
330 | 603 | if (!bn_less_than_words(out->words, group->field.N.d, group->field.N.width)) { |
331 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); |
332 | 0 | return 0; |
333 | 0 | } |
334 | | |
335 | 603 | return 1; |
336 | 603 | } |