diff options
Diffstat (limited to 'src/lib/libcrypto/ec/ecp_methods.c')
-rw-r--r-- | src/lib/libcrypto/ec/ecp_methods.c | 1656 |
1 files changed, 1656 insertions, 0 deletions
diff --git a/src/lib/libcrypto/ec/ecp_methods.c b/src/lib/libcrypto/ec/ecp_methods.c new file mode 100644 index 0000000000..3dc7091850 --- /dev/null +++ b/src/lib/libcrypto/ec/ecp_methods.c | |||
@@ -0,0 +1,1656 @@ | |||
1 | /* $OpenBSD: ecp_methods.c,v 1.1 2024/11/12 10:25:16 tb Exp $ */ | ||
2 | /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> | ||
3 | * for the OpenSSL project. | ||
4 | * Includes code written by Bodo Moeller for the OpenSSL project. | ||
5 | */ | ||
6 | /* ==================================================================== | ||
7 | * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. | ||
8 | * | ||
9 | * Redistribution and use in source and binary forms, with or without | ||
10 | * modification, are permitted provided that the following conditions | ||
11 | * are met: | ||
12 | * | ||
13 | * 1. Redistributions of source code must retain the above copyright | ||
14 | * notice, this list of conditions and the following disclaimer. | ||
15 | * | ||
16 | * 2. Redistributions in binary form must reproduce the above copyright | ||
17 | * notice, this list of conditions and the following disclaimer in | ||
18 | * the documentation and/or other materials provided with the | ||
19 | * distribution. | ||
20 | * | ||
21 | * 3. All advertising materials mentioning features or use of this | ||
22 | * software must display the following acknowledgment: | ||
23 | * "This product includes software developed by the OpenSSL Project | ||
24 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | ||
25 | * | ||
26 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | ||
27 | * endorse or promote products derived from this software without | ||
28 | * prior written permission. For written permission, please contact | ||
29 | * openssl-core@openssl.org. | ||
30 | * | ||
31 | * 5. Products derived from this software may not be called "OpenSSL" | ||
32 | * nor may "OpenSSL" appear in their names without prior written | ||
33 | * permission of the OpenSSL Project. | ||
34 | * | ||
35 | * 6. Redistributions of any form whatsoever must retain the following | ||
36 | * acknowledgment: | ||
37 | * "This product includes software developed by the OpenSSL Project | ||
38 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | ||
39 | * | ||
40 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | ||
41 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
42 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | ||
43 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | ||
44 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||
45 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
46 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | ||
47 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | ||
49 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
50 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | ||
51 | * OF THE POSSIBILITY OF SUCH DAMAGE. | ||
52 | * ==================================================================== | ||
53 | * | ||
54 | * This product includes cryptographic software written by Eric Young | ||
55 | * (eay@cryptsoft.com). This product includes software written by Tim | ||
56 | * Hudson (tjh@cryptsoft.com). | ||
57 | * | ||
58 | */ | ||
59 | /* ==================================================================== | ||
60 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | ||
61 | * Portions of this software developed by SUN MICROSYSTEMS, INC., | ||
62 | * and contributed to the OpenSSL project. | ||
63 | */ | ||
64 | |||
65 | #include <stdlib.h> | ||
66 | |||
67 | #include <openssl/bn.h> | ||
68 | #include <openssl/ec.h> | ||
69 | #include <openssl/err.h> | ||
70 | #include <openssl/objects.h> | ||
71 | |||
72 | #include "bn_local.h" | ||
73 | #include "ec_local.h" | ||
74 | |||
75 | /* | ||
76 | * Most method functions in this file are designed to work with | ||
77 | * non-trivial representations of field elements if necessary | ||
78 | * (see ecp_mont.c): while standard modular addition and subtraction | ||
79 | * are used, the field_mul and field_sqr methods will be used for | ||
80 | * multiplication, and field_encode and field_decode (if defined) | ||
81 | * will be used for converting between representations. | ||
82 | * | ||
83 | * Functions ec_GFp_simple_points_make_affine() and | ||
84 | * ec_GFp_simple_point_get_affine_coordinates() specifically assume | ||
85 | * that if a non-trivial representation is used, it is a Montgomery | ||
86 | * representation (i.e. 'encoding' means multiplying by some factor R). | ||
87 | */ | ||
88 | |||
89 | int | ||
90 | ec_GFp_simple_group_init(EC_GROUP *group) | ||
91 | { | ||
92 | BN_init(&group->field); | ||
93 | BN_init(&group->a); | ||
94 | BN_init(&group->b); | ||
95 | group->a_is_minus3 = 0; | ||
96 | return 1; | ||
97 | } | ||
98 | |||
99 | void | ||
100 | ec_GFp_simple_group_finish(EC_GROUP *group) | ||
101 | { | ||
102 | BN_free(&group->field); | ||
103 | BN_free(&group->a); | ||
104 | BN_free(&group->b); | ||
105 | } | ||
106 | |||
107 | int | ||
108 | ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) | ||
109 | { | ||
110 | if (!bn_copy(&dest->field, &src->field)) | ||
111 | return 0; | ||
112 | if (!bn_copy(&dest->a, &src->a)) | ||
113 | return 0; | ||
114 | if (!bn_copy(&dest->b, &src->b)) | ||
115 | return 0; | ||
116 | |||
117 | dest->a_is_minus3 = src->a_is_minus3; | ||
118 | |||
119 | return 1; | ||
120 | } | ||
121 | |||
122 | static int | ||
123 | ec_decode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx) | ||
124 | { | ||
125 | if (bn == NULL) | ||
126 | return 1; | ||
127 | |||
128 | if (group->meth->field_decode != NULL) | ||
129 | return group->meth->field_decode(group, bn, x, ctx); | ||
130 | |||
131 | return bn_copy(bn, x); | ||
132 | } | ||
133 | |||
134 | static int | ||
135 | ec_encode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx) | ||
136 | { | ||
137 | if (!BN_nnmod(bn, x, &group->field, ctx)) | ||
138 | return 0; | ||
139 | |||
140 | if (group->meth->field_encode != NULL) | ||
141 | return group->meth->field_encode(group, bn, bn, ctx); | ||
142 | |||
143 | return 1; | ||
144 | } | ||
145 | |||
146 | static int | ||
147 | ec_encode_z_coordinate(const EC_GROUP *group, BIGNUM *bn, int *is_one, | ||
148 | const BIGNUM *z, BN_CTX *ctx) | ||
149 | { | ||
150 | if (!BN_nnmod(bn, z, &group->field, ctx)) | ||
151 | return 0; | ||
152 | |||
153 | *is_one = BN_is_one(bn); | ||
154 | if (*is_one && group->meth->field_set_to_one != NULL) | ||
155 | return group->meth->field_set_to_one(group, bn, ctx); | ||
156 | |||
157 | if (group->meth->field_encode != NULL) | ||
158 | return group->meth->field_encode(group, bn, bn, ctx); | ||
159 | |||
160 | return 1; | ||
161 | } | ||
162 | |||
163 | int | ||
164 | ec_GFp_simple_group_set_curve(EC_GROUP *group, | ||
165 | const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | ||
166 | { | ||
167 | BIGNUM *a_plus_3; | ||
168 | int ret = 0; | ||
169 | |||
170 | /* p must be a prime > 3 */ | ||
171 | if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { | ||
172 | ECerror(EC_R_INVALID_FIELD); | ||
173 | return 0; | ||
174 | } | ||
175 | |||
176 | BN_CTX_start(ctx); | ||
177 | |||
178 | if ((a_plus_3 = BN_CTX_get(ctx)) == NULL) | ||
179 | goto err; | ||
180 | |||
181 | if (!bn_copy(&group->field, p)) | ||
182 | goto err; | ||
183 | BN_set_negative(&group->field, 0); | ||
184 | |||
185 | if (!ec_encode_scalar(group, &group->a, a, ctx)) | ||
186 | goto err; | ||
187 | if (!ec_encode_scalar(group, &group->b, b, ctx)) | ||
188 | goto err; | ||
189 | |||
190 | if (!BN_set_word(a_plus_3, 3)) | ||
191 | goto err; | ||
192 | if (!BN_mod_add(a_plus_3, a_plus_3, a, &group->field, ctx)) | ||
193 | goto err; | ||
194 | |||
195 | group->a_is_minus3 = BN_is_zero(a_plus_3); | ||
196 | |||
197 | ret = 1; | ||
198 | |||
199 | err: | ||
200 | BN_CTX_end(ctx); | ||
201 | |||
202 | return ret; | ||
203 | } | ||
204 | |||
205 | int | ||
206 | ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, | ||
207 | BIGNUM *b, BN_CTX *ctx) | ||
208 | { | ||
209 | if (p != NULL) { | ||
210 | if (!bn_copy(p, &group->field)) | ||
211 | return 0; | ||
212 | } | ||
213 | if (!ec_decode_scalar(group, a, &group->a, ctx)) | ||
214 | return 0; | ||
215 | if (!ec_decode_scalar(group, b, &group->b, ctx)) | ||
216 | return 0; | ||
217 | |||
218 | return 1; | ||
219 | } | ||
220 | |||
221 | int | ||
222 | ec_GFp_simple_group_get_degree(const EC_GROUP *group) | ||
223 | { | ||
224 | return BN_num_bits(&group->field); | ||
225 | } | ||
226 | |||
227 | int | ||
228 | ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) | ||
229 | { | ||
230 | BIGNUM *p, *a, *b, *discriminant; | ||
231 | int ret = 0; | ||
232 | |||
233 | BN_CTX_start(ctx); | ||
234 | |||
235 | if ((p = BN_CTX_get(ctx)) == NULL) | ||
236 | goto err; | ||
237 | if ((a = BN_CTX_get(ctx)) == NULL) | ||
238 | goto err; | ||
239 | if ((b = BN_CTX_get(ctx)) == NULL) | ||
240 | goto err; | ||
241 | if ((discriminant = BN_CTX_get(ctx)) == NULL) | ||
242 | goto err; | ||
243 | |||
244 | if (!EC_GROUP_get_curve(group, p, a, b, ctx)) | ||
245 | goto err; | ||
246 | |||
247 | /* | ||
248 | * Check that the discriminant 4a^3 + 27b^2 is non-zero modulo p. | ||
249 | */ | ||
250 | |||
251 | if (BN_is_zero(a) && BN_is_zero(b)) | ||
252 | goto err; | ||
253 | if (BN_is_zero(a) || BN_is_zero(b)) | ||
254 | goto done; | ||
255 | |||
256 | /* Compute the discriminant: first 4a^3, then 27b^2, then their sum. */ | ||
257 | if (!BN_mod_sqr(discriminant, a, p, ctx)) | ||
258 | goto err; | ||
259 | if (!BN_mod_mul(discriminant, discriminant, a, p, ctx)) | ||
260 | goto err; | ||
261 | if (!BN_lshift(discriminant, discriminant, 2)) | ||
262 | goto err; | ||
263 | |||
264 | if (!BN_mod_sqr(b, b, p, ctx)) | ||
265 | goto err; | ||
266 | if (!BN_mul_word(b, 27)) | ||
267 | goto err; | ||
268 | |||
269 | if (!BN_mod_add(discriminant, discriminant, b, p, ctx)) | ||
270 | goto err; | ||
271 | |||
272 | if (BN_is_zero(discriminant)) | ||
273 | goto err; | ||
274 | |||
275 | done: | ||
276 | ret = 1; | ||
277 | |||
278 | err: | ||
279 | BN_CTX_end(ctx); | ||
280 | |||
281 | return ret; | ||
282 | } | ||
283 | |||
284 | int | ||
285 | ec_GFp_simple_point_init(EC_POINT * point) | ||
286 | { | ||
287 | BN_init(&point->X); | ||
288 | BN_init(&point->Y); | ||
289 | BN_init(&point->Z); | ||
290 | point->Z_is_one = 0; | ||
291 | |||
292 | return 1; | ||
293 | } | ||
294 | |||
295 | void | ||
296 | ec_GFp_simple_point_finish(EC_POINT *point) | ||
297 | { | ||
298 | BN_free(&point->X); | ||
299 | BN_free(&point->Y); | ||
300 | BN_free(&point->Z); | ||
301 | point->Z_is_one = 0; | ||
302 | } | ||
303 | |||
304 | int | ||
305 | ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) | ||
306 | { | ||
307 | if (!bn_copy(&dest->X, &src->X)) | ||
308 | return 0; | ||
309 | if (!bn_copy(&dest->Y, &src->Y)) | ||
310 | return 0; | ||
311 | if (!bn_copy(&dest->Z, &src->Z)) | ||
312 | return 0; | ||
313 | dest->Z_is_one = src->Z_is_one; | ||
314 | |||
315 | return 1; | ||
316 | } | ||
317 | |||
318 | int | ||
319 | ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) | ||
320 | { | ||
321 | point->Z_is_one = 0; | ||
322 | BN_zero(&point->Z); | ||
323 | return 1; | ||
324 | } | ||
325 | |||
326 | int | ||
327 | ec_GFp_simple_set_Jprojective_coordinates(const EC_GROUP *group, | ||
328 | EC_POINT *point, const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, | ||
329 | BN_CTX *ctx) | ||
330 | { | ||
331 | int ret = 0; | ||
332 | |||
333 | /* | ||
334 | * Setting individual coordinates allows the creation of bad points. | ||
335 | * EC_POINT_set_Jprojective_coordinates() checks at the API boundary. | ||
336 | */ | ||
337 | |||
338 | if (x != NULL) { | ||
339 | if (!ec_encode_scalar(group, &point->X, x, ctx)) | ||
340 | goto err; | ||
341 | } | ||
342 | if (y != NULL) { | ||
343 | if (!ec_encode_scalar(group, &point->Y, y, ctx)) | ||
344 | goto err; | ||
345 | } | ||
346 | if (z != NULL) { | ||
347 | if (!ec_encode_z_coordinate(group, &point->Z, &point->Z_is_one, | ||
348 | z, ctx)) | ||
349 | goto err; | ||
350 | } | ||
351 | |||
352 | ret = 1; | ||
353 | |||
354 | err: | ||
355 | return ret; | ||
356 | } | ||
357 | |||
358 | int | ||
359 | ec_GFp_simple_get_Jprojective_coordinates(const EC_GROUP *group, | ||
360 | const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) | ||
361 | { | ||
362 | int ret = 0; | ||
363 | |||
364 | if (!ec_decode_scalar(group, x, &point->X, ctx)) | ||
365 | goto err; | ||
366 | if (!ec_decode_scalar(group, y, &point->Y, ctx)) | ||
367 | goto err; | ||
368 | if (!ec_decode_scalar(group, z, &point->Z, ctx)) | ||
369 | goto err; | ||
370 | |||
371 | ret = 1; | ||
372 | |||
373 | err: | ||
374 | return ret; | ||
375 | } | ||
376 | |||
377 | int | ||
378 | ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, | ||
379 | const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) | ||
380 | { | ||
381 | if (x == NULL || y == NULL) { | ||
382 | /* unlike for projective coordinates, we do not tolerate this */ | ||
383 | ECerror(ERR_R_PASSED_NULL_PARAMETER); | ||
384 | return 0; | ||
385 | } | ||
386 | return EC_POINT_set_Jprojective_coordinates(group, point, x, y, | ||
387 | BN_value_one(), ctx); | ||
388 | } | ||
389 | |||
390 | int | ||
391 | ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, | ||
392 | const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx) | ||
393 | { | ||
394 | BIGNUM *z, *Z, *Z_1, *Z_2, *Z_3; | ||
395 | int ret = 0; | ||
396 | |||
397 | BN_CTX_start(ctx); | ||
398 | |||
399 | if ((z = BN_CTX_get(ctx)) == NULL) | ||
400 | goto err; | ||
401 | if ((Z = BN_CTX_get(ctx)) == NULL) | ||
402 | goto err; | ||
403 | if ((Z_1 = BN_CTX_get(ctx)) == NULL) | ||
404 | goto err; | ||
405 | if ((Z_2 = BN_CTX_get(ctx)) == NULL) | ||
406 | goto err; | ||
407 | if ((Z_3 = BN_CTX_get(ctx)) == NULL) | ||
408 | goto err; | ||
409 | |||
410 | /* Convert from projective coordinates (X, Y, Z) into (X/Z^2, Y/Z^3). */ | ||
411 | |||
412 | if (!ec_decode_scalar(group, z, &point->Z, ctx)) | ||
413 | goto err; | ||
414 | |||
415 | if (BN_is_one(z)) { | ||
416 | if (!ec_decode_scalar(group, x, &point->X, ctx)) | ||
417 | goto err; | ||
418 | if (!ec_decode_scalar(group, y, &point->Y, ctx)) | ||
419 | goto err; | ||
420 | goto done; | ||
421 | } | ||
422 | |||
423 | if (BN_mod_inverse_ct(Z_1, z, &group->field, ctx) == NULL) { | ||
424 | ECerror(ERR_R_BN_LIB); | ||
425 | goto err; | ||
426 | } | ||
427 | if (group->meth->field_encode == NULL) { | ||
428 | /* field_sqr works on standard representation */ | ||
429 | if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) | ||
430 | goto err; | ||
431 | } else { | ||
432 | if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) | ||
433 | goto err; | ||
434 | } | ||
435 | |||
436 | if (x != NULL) { | ||
437 | /* | ||
438 | * in the Montgomery case, field_mul will cancel out | ||
439 | * Montgomery factor in X: | ||
440 | */ | ||
441 | if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) | ||
442 | goto err; | ||
443 | } | ||
444 | if (y != NULL) { | ||
445 | if (group->meth->field_encode == NULL) { | ||
446 | /* field_mul works on standard representation */ | ||
447 | if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) | ||
448 | goto err; | ||
449 | } else { | ||
450 | if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) | ||
451 | goto err; | ||
452 | } | ||
453 | |||
454 | /* | ||
455 | * in the Montgomery case, field_mul will cancel out | ||
456 | * Montgomery factor in Y: | ||
457 | */ | ||
458 | if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) | ||
459 | goto err; | ||
460 | } | ||
461 | |||
462 | done: | ||
463 | ret = 1; | ||
464 | |||
465 | err: | ||
466 | BN_CTX_end(ctx); | ||
467 | |||
468 | return ret; | ||
469 | } | ||
470 | |||
471 | int | ||
472 | ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, | ||
473 | EC_POINT *point, const BIGNUM *in_x, int y_bit, BN_CTX *ctx) | ||
474 | { | ||
475 | const BIGNUM *p = &group->field, *a = &group->a, *b = &group->b; | ||
476 | BIGNUM *w, *x, *y; | ||
477 | int ret = 0; | ||
478 | |||
479 | y_bit = (y_bit != 0); | ||
480 | |||
481 | BN_CTX_start(ctx); | ||
482 | |||
483 | if ((w = BN_CTX_get(ctx)) == NULL) | ||
484 | goto err; | ||
485 | if ((x = BN_CTX_get(ctx)) == NULL) | ||
486 | goto err; | ||
487 | if ((y = BN_CTX_get(ctx)) == NULL) | ||
488 | goto err; | ||
489 | |||
490 | /* | ||
491 | * Weierstrass equation: y^2 = x^3 + ax + b, so y is one of the | ||
492 | * square roots of x^3 + ax + b. The y-bit indicates which one. | ||
493 | */ | ||
494 | |||
495 | /* XXX - should we not insist on 0 <= x < p instead? */ | ||
496 | if (!BN_nnmod(x, in_x, p, ctx)) | ||
497 | goto err; | ||
498 | |||
499 | if (group->meth->field_encode != NULL) { | ||
500 | if (!group->meth->field_encode(group, x, x, ctx)) | ||
501 | goto err; | ||
502 | } | ||
503 | |||
504 | /* y = x^3 */ | ||
505 | if (!group->meth->field_sqr(group, y, x, ctx)) | ||
506 | goto err; | ||
507 | if (!group->meth->field_mul(group, y, y, x, ctx)) | ||
508 | goto err; | ||
509 | |||
510 | /* y += ax */ | ||
511 | if (group->a_is_minus3) { | ||
512 | if (!BN_mod_lshift1_quick(w, x, p)) | ||
513 | goto err; | ||
514 | if (!BN_mod_add_quick(w, w, x, p)) | ||
515 | goto err; | ||
516 | if (!BN_mod_sub_quick(y, y, w, p)) | ||
517 | goto err; | ||
518 | } else { | ||
519 | if (!group->meth->field_mul(group, w, a, x, ctx)) | ||
520 | goto err; | ||
521 | if (!BN_mod_add_quick(y, y, w, p)) | ||
522 | goto err; | ||
523 | } | ||
524 | |||
525 | /* y += b */ | ||
526 | if (!BN_mod_add_quick(y, y, b, p)) | ||
527 | goto err; | ||
528 | |||
529 | if (group->meth->field_decode != NULL) { | ||
530 | if (!group->meth->field_decode(group, x, x, ctx)) | ||
531 | goto err; | ||
532 | if (!group->meth->field_decode(group, y, y, ctx)) | ||
533 | goto err; | ||
534 | } | ||
535 | |||
536 | if (!BN_mod_sqrt(y, y, p, ctx)) { | ||
537 | ECerror(EC_R_INVALID_COMPRESSED_POINT); | ||
538 | goto err; | ||
539 | } | ||
540 | |||
541 | if (y_bit == BN_is_odd(y)) | ||
542 | goto done; | ||
543 | |||
544 | if (BN_is_zero(y)) { | ||
545 | ECerror(EC_R_INVALID_COMPRESSION_BIT); | ||
546 | goto err; | ||
547 | } | ||
548 | if (!BN_usub(y, &group->field, y)) | ||
549 | goto err; | ||
550 | |||
551 | if (y_bit != BN_is_odd(y)) { | ||
552 | /* Can only happen if p is even and should not be reachable. */ | ||
553 | ECerror(ERR_R_INTERNAL_ERROR); | ||
554 | goto err; | ||
555 | } | ||
556 | |||
557 | done: | ||
558 | if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) | ||
559 | goto err; | ||
560 | |||
561 | ret = 1; | ||
562 | |||
563 | err: | ||
564 | BN_CTX_end(ctx); | ||
565 | |||
566 | return ret; | ||
567 | } | ||
568 | |||
569 | int | ||
570 | ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) | ||
571 | { | ||
572 | int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); | ||
573 | int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | ||
574 | BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; | ||
575 | const BIGNUM *p; | ||
576 | int ret = 0; | ||
577 | |||
578 | if (a == b) | ||
579 | return EC_POINT_dbl(group, r, a, ctx); | ||
580 | if (EC_POINT_is_at_infinity(group, a)) | ||
581 | return EC_POINT_copy(r, b); | ||
582 | if (EC_POINT_is_at_infinity(group, b)) | ||
583 | return EC_POINT_copy(r, a); | ||
584 | |||
585 | field_mul = group->meth->field_mul; | ||
586 | field_sqr = group->meth->field_sqr; | ||
587 | p = &group->field; | ||
588 | |||
589 | BN_CTX_start(ctx); | ||
590 | |||
591 | if ((n0 = BN_CTX_get(ctx)) == NULL) | ||
592 | goto end; | ||
593 | if ((n1 = BN_CTX_get(ctx)) == NULL) | ||
594 | goto end; | ||
595 | if ((n2 = BN_CTX_get(ctx)) == NULL) | ||
596 | goto end; | ||
597 | if ((n3 = BN_CTX_get(ctx)) == NULL) | ||
598 | goto end; | ||
599 | if ((n4 = BN_CTX_get(ctx)) == NULL) | ||
600 | goto end; | ||
601 | if ((n5 = BN_CTX_get(ctx)) == NULL) | ||
602 | goto end; | ||
603 | if ((n6 = BN_CTX_get(ctx)) == NULL) | ||
604 | goto end; | ||
605 | |||
606 | /* | ||
607 | * Note that in this function we must not read components of 'a' or | ||
608 | * 'b' once we have written the corresponding components of 'r'. ('r' | ||
609 | * might be one of 'a' or 'b'.) | ||
610 | */ | ||
611 | |||
612 | /* n1, n2 */ | ||
613 | if (b->Z_is_one) { | ||
614 | if (!bn_copy(n1, &a->X)) | ||
615 | goto end; | ||
616 | if (!bn_copy(n2, &a->Y)) | ||
617 | goto end; | ||
618 | /* n1 = X_a */ | ||
619 | /* n2 = Y_a */ | ||
620 | } else { | ||
621 | if (!field_sqr(group, n0, &b->Z, ctx)) | ||
622 | goto end; | ||
623 | if (!field_mul(group, n1, &a->X, n0, ctx)) | ||
624 | goto end; | ||
625 | /* n1 = X_a * Z_b^2 */ | ||
626 | |||
627 | if (!field_mul(group, n0, n0, &b->Z, ctx)) | ||
628 | goto end; | ||
629 | if (!field_mul(group, n2, &a->Y, n0, ctx)) | ||
630 | goto end; | ||
631 | /* n2 = Y_a * Z_b^3 */ | ||
632 | } | ||
633 | |||
634 | /* n3, n4 */ | ||
635 | if (a->Z_is_one) { | ||
636 | if (!bn_copy(n3, &b->X)) | ||
637 | goto end; | ||
638 | if (!bn_copy(n4, &b->Y)) | ||
639 | goto end; | ||
640 | /* n3 = X_b */ | ||
641 | /* n4 = Y_b */ | ||
642 | } else { | ||
643 | if (!field_sqr(group, n0, &a->Z, ctx)) | ||
644 | goto end; | ||
645 | if (!field_mul(group, n3, &b->X, n0, ctx)) | ||
646 | goto end; | ||
647 | /* n3 = X_b * Z_a^2 */ | ||
648 | |||
649 | if (!field_mul(group, n0, n0, &a->Z, ctx)) | ||
650 | goto end; | ||
651 | if (!field_mul(group, n4, &b->Y, n0, ctx)) | ||
652 | goto end; | ||
653 | /* n4 = Y_b * Z_a^3 */ | ||
654 | } | ||
655 | |||
656 | /* n5, n6 */ | ||
657 | if (!BN_mod_sub_quick(n5, n1, n3, p)) | ||
658 | goto end; | ||
659 | if (!BN_mod_sub_quick(n6, n2, n4, p)) | ||
660 | goto end; | ||
661 | /* n5 = n1 - n3 */ | ||
662 | /* n6 = n2 - n4 */ | ||
663 | |||
664 | if (BN_is_zero(n5)) { | ||
665 | if (BN_is_zero(n6)) { | ||
666 | /* a is the same point as b */ | ||
667 | BN_CTX_end(ctx); | ||
668 | ret = EC_POINT_dbl(group, r, a, ctx); | ||
669 | ctx = NULL; | ||
670 | goto end; | ||
671 | } else { | ||
672 | /* a is the inverse of b */ | ||
673 | BN_zero(&r->Z); | ||
674 | r->Z_is_one = 0; | ||
675 | ret = 1; | ||
676 | goto end; | ||
677 | } | ||
678 | } | ||
679 | /* 'n7', 'n8' */ | ||
680 | if (!BN_mod_add_quick(n1, n1, n3, p)) | ||
681 | goto end; | ||
682 | if (!BN_mod_add_quick(n2, n2, n4, p)) | ||
683 | goto end; | ||
684 | /* 'n7' = n1 + n3 */ | ||
685 | /* 'n8' = n2 + n4 */ | ||
686 | |||
687 | /* Z_r */ | ||
688 | if (a->Z_is_one && b->Z_is_one) { | ||
689 | if (!bn_copy(&r->Z, n5)) | ||
690 | goto end; | ||
691 | } else { | ||
692 | if (a->Z_is_one) { | ||
693 | if (!bn_copy(n0, &b->Z)) | ||
694 | goto end; | ||
695 | } else if (b->Z_is_one) { | ||
696 | if (!bn_copy(n0, &a->Z)) | ||
697 | goto end; | ||
698 | } else { | ||
699 | if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) | ||
700 | goto end; | ||
701 | } | ||
702 | if (!field_mul(group, &r->Z, n0, n5, ctx)) | ||
703 | goto end; | ||
704 | } | ||
705 | r->Z_is_one = 0; | ||
706 | /* Z_r = Z_a * Z_b * n5 */ | ||
707 | |||
708 | /* X_r */ | ||
709 | if (!field_sqr(group, n0, n6, ctx)) | ||
710 | goto end; | ||
711 | if (!field_sqr(group, n4, n5, ctx)) | ||
712 | goto end; | ||
713 | if (!field_mul(group, n3, n1, n4, ctx)) | ||
714 | goto end; | ||
715 | if (!BN_mod_sub_quick(&r->X, n0, n3, p)) | ||
716 | goto end; | ||
717 | /* X_r = n6^2 - n5^2 * 'n7' */ | ||
718 | |||
719 | /* 'n9' */ | ||
720 | if (!BN_mod_lshift1_quick(n0, &r->X, p)) | ||
721 | goto end; | ||
722 | if (!BN_mod_sub_quick(n0, n3, n0, p)) | ||
723 | goto end; | ||
724 | /* n9 = n5^2 * 'n7' - 2 * X_r */ | ||
725 | |||
726 | /* Y_r */ | ||
727 | if (!field_mul(group, n0, n0, n6, ctx)) | ||
728 | goto end; | ||
729 | if (!field_mul(group, n5, n4, n5, ctx)) | ||
730 | goto end; /* now n5 is n5^3 */ | ||
731 | if (!field_mul(group, n1, n2, n5, ctx)) | ||
732 | goto end; | ||
733 | if (!BN_mod_sub_quick(n0, n0, n1, p)) | ||
734 | goto end; | ||
735 | if (BN_is_odd(n0)) | ||
736 | if (!BN_add(n0, n0, p)) | ||
737 | goto end; | ||
738 | /* now 0 <= n0 < 2*p, and n0 is even */ | ||
739 | if (!BN_rshift1(&r->Y, n0)) | ||
740 | goto end; | ||
741 | /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ | ||
742 | |||
743 | ret = 1; | ||
744 | |||
745 | end: | ||
746 | BN_CTX_end(ctx); | ||
747 | |||
748 | return ret; | ||
749 | } | ||
750 | |||
751 | int | ||
752 | ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) | ||
753 | { | ||
754 | int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); | ||
755 | int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | ||
756 | const BIGNUM *p; | ||
757 | BIGNUM *n0, *n1, *n2, *n3; | ||
758 | int ret = 0; | ||
759 | |||
760 | if (EC_POINT_is_at_infinity(group, a)) | ||
761 | return EC_POINT_set_to_infinity(group, r); | ||
762 | |||
763 | field_mul = group->meth->field_mul; | ||
764 | field_sqr = group->meth->field_sqr; | ||
765 | p = &group->field; | ||
766 | |||
767 | BN_CTX_start(ctx); | ||
768 | |||
769 | if ((n0 = BN_CTX_get(ctx)) == NULL) | ||
770 | goto err; | ||
771 | if ((n1 = BN_CTX_get(ctx)) == NULL) | ||
772 | goto err; | ||
773 | if ((n2 = BN_CTX_get(ctx)) == NULL) | ||
774 | goto err; | ||
775 | if ((n3 = BN_CTX_get(ctx)) == NULL) | ||
776 | goto err; | ||
777 | |||
778 | /* | ||
779 | * Note that in this function we must not read components of 'a' once | ||
780 | * we have written the corresponding components of 'r'. ('r' might | ||
781 | * the same as 'a'.) | ||
782 | */ | ||
783 | |||
784 | /* n1 */ | ||
785 | if (a->Z_is_one) { | ||
786 | if (!field_sqr(group, n0, &a->X, ctx)) | ||
787 | goto err; | ||
788 | if (!BN_mod_lshift1_quick(n1, n0, p)) | ||
789 | goto err; | ||
790 | if (!BN_mod_add_quick(n0, n0, n1, p)) | ||
791 | goto err; | ||
792 | if (!BN_mod_add_quick(n1, n0, &group->a, p)) | ||
793 | goto err; | ||
794 | /* n1 = 3 * X_a^2 + a_curve */ | ||
795 | } else if (group->a_is_minus3) { | ||
796 | if (!field_sqr(group, n1, &a->Z, ctx)) | ||
797 | goto err; | ||
798 | if (!BN_mod_add_quick(n0, &a->X, n1, p)) | ||
799 | goto err; | ||
800 | if (!BN_mod_sub_quick(n2, &a->X, n1, p)) | ||
801 | goto err; | ||
802 | if (!field_mul(group, n1, n0, n2, ctx)) | ||
803 | goto err; | ||
804 | if (!BN_mod_lshift1_quick(n0, n1, p)) | ||
805 | goto err; | ||
806 | if (!BN_mod_add_quick(n1, n0, n1, p)) | ||
807 | goto err; | ||
808 | /* | ||
809 | * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 * | ||
810 | * Z_a^4 | ||
811 | */ | ||
812 | } else { | ||
813 | if (!field_sqr(group, n0, &a->X, ctx)) | ||
814 | goto err; | ||
815 | if (!BN_mod_lshift1_quick(n1, n0, p)) | ||
816 | goto err; | ||
817 | if (!BN_mod_add_quick(n0, n0, n1, p)) | ||
818 | goto err; | ||
819 | if (!field_sqr(group, n1, &a->Z, ctx)) | ||
820 | goto err; | ||
821 | if (!field_sqr(group, n1, n1, ctx)) | ||
822 | goto err; | ||
823 | if (!field_mul(group, n1, n1, &group->a, ctx)) | ||
824 | goto err; | ||
825 | if (!BN_mod_add_quick(n1, n1, n0, p)) | ||
826 | goto err; | ||
827 | /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ | ||
828 | } | ||
829 | |||
830 | /* Z_r */ | ||
831 | if (a->Z_is_one) { | ||
832 | if (!bn_copy(n0, &a->Y)) | ||
833 | goto err; | ||
834 | } else { | ||
835 | if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) | ||
836 | goto err; | ||
837 | } | ||
838 | if (!BN_mod_lshift1_quick(&r->Z, n0, p)) | ||
839 | goto err; | ||
840 | r->Z_is_one = 0; | ||
841 | /* Z_r = 2 * Y_a * Z_a */ | ||
842 | |||
843 | /* n2 */ | ||
844 | if (!field_sqr(group, n3, &a->Y, ctx)) | ||
845 | goto err; | ||
846 | if (!field_mul(group, n2, &a->X, n3, ctx)) | ||
847 | goto err; | ||
848 | if (!BN_mod_lshift_quick(n2, n2, 2, p)) | ||
849 | goto err; | ||
850 | /* n2 = 4 * X_a * Y_a^2 */ | ||
851 | |||
852 | /* X_r */ | ||
853 | if (!BN_mod_lshift1_quick(n0, n2, p)) | ||
854 | goto err; | ||
855 | if (!field_sqr(group, &r->X, n1, ctx)) | ||
856 | goto err; | ||
857 | if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) | ||
858 | goto err; | ||
859 | /* X_r = n1^2 - 2 * n2 */ | ||
860 | |||
861 | /* n3 */ | ||
862 | if (!field_sqr(group, n0, n3, ctx)) | ||
863 | goto err; | ||
864 | if (!BN_mod_lshift_quick(n3, n0, 3, p)) | ||
865 | goto err; | ||
866 | /* n3 = 8 * Y_a^4 */ | ||
867 | |||
868 | /* Y_r */ | ||
869 | if (!BN_mod_sub_quick(n0, n2, &r->X, p)) | ||
870 | goto err; | ||
871 | if (!field_mul(group, n0, n1, n0, ctx)) | ||
872 | goto err; | ||
873 | if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) | ||
874 | goto err; | ||
875 | /* Y_r = n1 * (n2 - X_r) - n3 */ | ||
876 | |||
877 | ret = 1; | ||
878 | |||
879 | err: | ||
880 | BN_CTX_end(ctx); | ||
881 | |||
882 | return ret; | ||
883 | } | ||
884 | |||
885 | int | ||
886 | ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) | ||
887 | { | ||
888 | if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) | ||
889 | /* point is its own inverse */ | ||
890 | return 1; | ||
891 | |||
892 | return BN_usub(&point->Y, &group->field, &point->Y); | ||
893 | } | ||
894 | |||
895 | int | ||
896 | ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) | ||
897 | { | ||
898 | return BN_is_zero(&point->Z); | ||
899 | } | ||
900 | |||
901 | int | ||
902 | ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) | ||
903 | { | ||
904 | int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); | ||
905 | int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | ||
906 | const BIGNUM *p; | ||
907 | BIGNUM *rh, *tmp, *Z4, *Z6; | ||
908 | int ret = -1; | ||
909 | |||
910 | if (EC_POINT_is_at_infinity(group, point)) | ||
911 | return 1; | ||
912 | |||
913 | field_mul = group->meth->field_mul; | ||
914 | field_sqr = group->meth->field_sqr; | ||
915 | p = &group->field; | ||
916 | |||
917 | BN_CTX_start(ctx); | ||
918 | |||
919 | if ((rh = BN_CTX_get(ctx)) == NULL) | ||
920 | goto err; | ||
921 | if ((tmp = BN_CTX_get(ctx)) == NULL) | ||
922 | goto err; | ||
923 | if ((Z4 = BN_CTX_get(ctx)) == NULL) | ||
924 | goto err; | ||
925 | if ((Z6 = BN_CTX_get(ctx)) == NULL) | ||
926 | goto err; | ||
927 | |||
928 | /* | ||
929 | * We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x | ||
930 | * + b. The point to consider is given in Jacobian projective | ||
931 | * coordinates where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). | ||
932 | * Substituting this and multiplying by Z^6 transforms the above | ||
933 | * equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up | ||
934 | * the right-hand side in 'rh'. | ||
935 | */ | ||
936 | |||
937 | /* rh := X^2 */ | ||
938 | if (!field_sqr(group, rh, &point->X, ctx)) | ||
939 | goto err; | ||
940 | |||
941 | if (!point->Z_is_one) { | ||
942 | if (!field_sqr(group, tmp, &point->Z, ctx)) | ||
943 | goto err; | ||
944 | if (!field_sqr(group, Z4, tmp, ctx)) | ||
945 | goto err; | ||
946 | if (!field_mul(group, Z6, Z4, tmp, ctx)) | ||
947 | goto err; | ||
948 | |||
949 | /* rh := (rh + a*Z^4)*X */ | ||
950 | if (group->a_is_minus3) { | ||
951 | if (!BN_mod_lshift1_quick(tmp, Z4, p)) | ||
952 | goto err; | ||
953 | if (!BN_mod_add_quick(tmp, tmp, Z4, p)) | ||
954 | goto err; | ||
955 | if (!BN_mod_sub_quick(rh, rh, tmp, p)) | ||
956 | goto err; | ||
957 | if (!field_mul(group, rh, rh, &point->X, ctx)) | ||
958 | goto err; | ||
959 | } else { | ||
960 | if (!field_mul(group, tmp, Z4, &group->a, ctx)) | ||
961 | goto err; | ||
962 | if (!BN_mod_add_quick(rh, rh, tmp, p)) | ||
963 | goto err; | ||
964 | if (!field_mul(group, rh, rh, &point->X, ctx)) | ||
965 | goto err; | ||
966 | } | ||
967 | |||
968 | /* rh := rh + b*Z^6 */ | ||
969 | if (!field_mul(group, tmp, &group->b, Z6, ctx)) | ||
970 | goto err; | ||
971 | if (!BN_mod_add_quick(rh, rh, tmp, p)) | ||
972 | goto err; | ||
973 | } else { | ||
974 | /* point->Z_is_one */ | ||
975 | |||
976 | /* rh := (rh + a)*X */ | ||
977 | if (!BN_mod_add_quick(rh, rh, &group->a, p)) | ||
978 | goto err; | ||
979 | if (!field_mul(group, rh, rh, &point->X, ctx)) | ||
980 | goto err; | ||
981 | /* rh := rh + b */ | ||
982 | if (!BN_mod_add_quick(rh, rh, &group->b, p)) | ||
983 | goto err; | ||
984 | } | ||
985 | |||
986 | /* 'lh' := Y^2 */ | ||
987 | if (!field_sqr(group, tmp, &point->Y, ctx)) | ||
988 | goto err; | ||
989 | |||
990 | ret = (0 == BN_ucmp(tmp, rh)); | ||
991 | |||
992 | err: | ||
993 | BN_CTX_end(ctx); | ||
994 | |||
995 | return ret; | ||
996 | } | ||
997 | |||
998 | int | ||
999 | ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) | ||
1000 | { | ||
1001 | /* | ||
1002 | * return values: -1 error 0 equal (in affine coordinates) 1 | ||
1003 | * not equal | ||
1004 | */ | ||
1005 | |||
1006 | int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); | ||
1007 | int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | ||
1008 | BIGNUM *tmp1, *tmp2, *Za23, *Zb23; | ||
1009 | const BIGNUM *tmp1_, *tmp2_; | ||
1010 | int ret = -1; | ||
1011 | |||
1012 | if (EC_POINT_is_at_infinity(group, a)) | ||
1013 | return !EC_POINT_is_at_infinity(group, b); | ||
1014 | |||
1015 | if (EC_POINT_is_at_infinity(group, b)) | ||
1016 | return 1; | ||
1017 | |||
1018 | if (a->Z_is_one && b->Z_is_one) | ||
1019 | return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; | ||
1020 | |||
1021 | field_mul = group->meth->field_mul; | ||
1022 | field_sqr = group->meth->field_sqr; | ||
1023 | |||
1024 | BN_CTX_start(ctx); | ||
1025 | |||
1026 | if ((tmp1 = BN_CTX_get(ctx)) == NULL) | ||
1027 | goto end; | ||
1028 | if ((tmp2 = BN_CTX_get(ctx)) == NULL) | ||
1029 | goto end; | ||
1030 | if ((Za23 = BN_CTX_get(ctx)) == NULL) | ||
1031 | goto end; | ||
1032 | if ((Zb23 = BN_CTX_get(ctx)) == NULL) | ||
1033 | goto end; | ||
1034 | |||
1035 | /* | ||
1036 | * We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, | ||
1037 | * Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) = | ||
1038 | * (X_b*Z_a^2, Y_b*Z_a^3). | ||
1039 | */ | ||
1040 | |||
1041 | if (!b->Z_is_one) { | ||
1042 | if (!field_sqr(group, Zb23, &b->Z, ctx)) | ||
1043 | goto end; | ||
1044 | if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) | ||
1045 | goto end; | ||
1046 | tmp1_ = tmp1; | ||
1047 | } else | ||
1048 | tmp1_ = &a->X; | ||
1049 | if (!a->Z_is_one) { | ||
1050 | if (!field_sqr(group, Za23, &a->Z, ctx)) | ||
1051 | goto end; | ||
1052 | if (!field_mul(group, tmp2, &b->X, Za23, ctx)) | ||
1053 | goto end; | ||
1054 | tmp2_ = tmp2; | ||
1055 | } else | ||
1056 | tmp2_ = &b->X; | ||
1057 | |||
1058 | /* compare X_a*Z_b^2 with X_b*Z_a^2 */ | ||
1059 | if (BN_cmp(tmp1_, tmp2_) != 0) { | ||
1060 | ret = 1; /* points differ */ | ||
1061 | goto end; | ||
1062 | } | ||
1063 | if (!b->Z_is_one) { | ||
1064 | if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) | ||
1065 | goto end; | ||
1066 | if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) | ||
1067 | goto end; | ||
1068 | /* tmp1_ = tmp1 */ | ||
1069 | } else | ||
1070 | tmp1_ = &a->Y; | ||
1071 | if (!a->Z_is_one) { | ||
1072 | if (!field_mul(group, Za23, Za23, &a->Z, ctx)) | ||
1073 | goto end; | ||
1074 | if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) | ||
1075 | goto end; | ||
1076 | /* tmp2_ = tmp2 */ | ||
1077 | } else | ||
1078 | tmp2_ = &b->Y; | ||
1079 | |||
1080 | /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ | ||
1081 | if (BN_cmp(tmp1_, tmp2_) != 0) { | ||
1082 | ret = 1; /* points differ */ | ||
1083 | goto end; | ||
1084 | } | ||
1085 | /* points are equal */ | ||
1086 | ret = 0; | ||
1087 | |||
1088 | end: | ||
1089 | BN_CTX_end(ctx); | ||
1090 | |||
1091 | return ret; | ||
1092 | } | ||
1093 | |||
1094 | int | ||
1095 | ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) | ||
1096 | { | ||
1097 | BIGNUM *x, *y; | ||
1098 | int ret = 0; | ||
1099 | |||
1100 | if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) | ||
1101 | return 1; | ||
1102 | |||
1103 | BN_CTX_start(ctx); | ||
1104 | |||
1105 | if ((x = BN_CTX_get(ctx)) == NULL) | ||
1106 | goto err; | ||
1107 | if ((y = BN_CTX_get(ctx)) == NULL) | ||
1108 | goto err; | ||
1109 | |||
1110 | if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) | ||
1111 | goto err; | ||
1112 | if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) | ||
1113 | goto err; | ||
1114 | if (!point->Z_is_one) { | ||
1115 | ECerror(ERR_R_INTERNAL_ERROR); | ||
1116 | goto err; | ||
1117 | } | ||
1118 | ret = 1; | ||
1119 | |||
1120 | err: | ||
1121 | BN_CTX_end(ctx); | ||
1122 | |||
1123 | return ret; | ||
1124 | } | ||
1125 | |||
1126 | int | ||
1127 | ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx) | ||
1128 | { | ||
1129 | BIGNUM *tmp0, *tmp1; | ||
1130 | size_t pow2 = 0; | ||
1131 | BIGNUM **heap = NULL; | ||
1132 | size_t i; | ||
1133 | int ret = 0; | ||
1134 | |||
1135 | if (num == 0) | ||
1136 | return 1; | ||
1137 | |||
1138 | BN_CTX_start(ctx); | ||
1139 | |||
1140 | if ((tmp0 = BN_CTX_get(ctx)) == NULL) | ||
1141 | goto err; | ||
1142 | if ((tmp1 = BN_CTX_get(ctx)) == NULL) | ||
1143 | goto err; | ||
1144 | |||
1145 | /* | ||
1146 | * Before converting the individual points, compute inverses of all Z | ||
1147 | * values. Modular inversion is rather slow, but luckily we can do | ||
1148 | * with a single explicit inversion, plus about 3 multiplications per | ||
1149 | * input value. | ||
1150 | */ | ||
1151 | |||
1152 | pow2 = 1; | ||
1153 | while (num > pow2) | ||
1154 | pow2 <<= 1; | ||
1155 | /* | ||
1156 | * Now pow2 is the smallest power of 2 satifsying pow2 >= num. We | ||
1157 | * need twice that. | ||
1158 | */ | ||
1159 | pow2 <<= 1; | ||
1160 | |||
1161 | heap = reallocarray(NULL, pow2, sizeof heap[0]); | ||
1162 | if (heap == NULL) | ||
1163 | goto err; | ||
1164 | |||
1165 | /* | ||
1166 | * The array is used as a binary tree, exactly as in heapsort: | ||
1167 | * | ||
1168 | * heap[1] heap[2] heap[3] heap[4] heap[5] | ||
1169 | * heap[6] heap[7] heap[8]heap[9] heap[10]heap[11] | ||
1170 | * heap[12]heap[13] heap[14] heap[15] | ||
1171 | * | ||
1172 | * We put the Z's in the last line; then we set each other node to the | ||
1173 | * product of its two child-nodes (where empty or 0 entries are | ||
1174 | * treated as ones); then we invert heap[1]; then we invert each | ||
1175 | * other node by replacing it by the product of its parent (after | ||
1176 | * inversion) and its sibling (before inversion). | ||
1177 | */ | ||
1178 | heap[0] = NULL; | ||
1179 | for (i = pow2 / 2 - 1; i > 0; i--) | ||
1180 | heap[i] = NULL; | ||
1181 | for (i = 0; i < num; i++) | ||
1182 | heap[pow2 / 2 + i] = &points[i]->Z; | ||
1183 | for (i = pow2 / 2 + num; i < pow2; i++) | ||
1184 | heap[i] = NULL; | ||
1185 | |||
1186 | /* set each node to the product of its children */ | ||
1187 | for (i = pow2 / 2 - 1; i > 0; i--) { | ||
1188 | heap[i] = BN_new(); | ||
1189 | if (heap[i] == NULL) | ||
1190 | goto err; | ||
1191 | |||
1192 | if (heap[2 * i] != NULL) { | ||
1193 | if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) { | ||
1194 | if (!bn_copy(heap[i], heap[2 * i])) | ||
1195 | goto err; | ||
1196 | } else { | ||
1197 | if (BN_is_zero(heap[2 * i])) { | ||
1198 | if (!bn_copy(heap[i], heap[2 * i + 1])) | ||
1199 | goto err; | ||
1200 | } else { | ||
1201 | if (!group->meth->field_mul(group, heap[i], | ||
1202 | heap[2 * i], heap[2 * i + 1], ctx)) | ||
1203 | goto err; | ||
1204 | } | ||
1205 | } | ||
1206 | } | ||
1207 | } | ||
1208 | |||
1209 | /* invert heap[1] */ | ||
1210 | if (!BN_is_zero(heap[1])) { | ||
1211 | if (BN_mod_inverse_ct(heap[1], heap[1], &group->field, ctx) == NULL) { | ||
1212 | ECerror(ERR_R_BN_LIB); | ||
1213 | goto err; | ||
1214 | } | ||
1215 | } | ||
1216 | if (group->meth->field_encode != NULL) { | ||
1217 | /* | ||
1218 | * in the Montgomery case, we just turned R*H (representing | ||
1219 | * H) into 1/(R*H), but we need R*(1/H) (representing | ||
1220 | * 1/H); i.e. we have need to multiply by the Montgomery | ||
1221 | * factor twice | ||
1222 | */ | ||
1223 | if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) | ||
1224 | goto err; | ||
1225 | if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) | ||
1226 | goto err; | ||
1227 | } | ||
1228 | /* set other heap[i]'s to their inverses */ | ||
1229 | for (i = 2; i < pow2 / 2 + num; i += 2) { | ||
1230 | /* i is even */ | ||
1231 | if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) { | ||
1232 | if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx)) | ||
1233 | goto err; | ||
1234 | if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx)) | ||
1235 | goto err; | ||
1236 | if (!bn_copy(heap[i], tmp0)) | ||
1237 | goto err; | ||
1238 | if (!bn_copy(heap[i + 1], tmp1)) | ||
1239 | goto err; | ||
1240 | } else { | ||
1241 | if (!bn_copy(heap[i], heap[i / 2])) | ||
1242 | goto err; | ||
1243 | } | ||
1244 | } | ||
1245 | |||
1246 | /* | ||
1247 | * we have replaced all non-zero Z's by their inverses, now fix up | ||
1248 | * all the points | ||
1249 | */ | ||
1250 | for (i = 0; i < num; i++) { | ||
1251 | EC_POINT *p = points[i]; | ||
1252 | |||
1253 | if (!BN_is_zero(&p->Z)) { | ||
1254 | /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ | ||
1255 | |||
1256 | if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) | ||
1257 | goto err; | ||
1258 | if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) | ||
1259 | goto err; | ||
1260 | |||
1261 | if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) | ||
1262 | goto err; | ||
1263 | if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) | ||
1264 | goto err; | ||
1265 | |||
1266 | if (group->meth->field_set_to_one != NULL) { | ||
1267 | if (!group->meth->field_set_to_one(group, &p->Z, ctx)) | ||
1268 | goto err; | ||
1269 | } else { | ||
1270 | if (!BN_one(&p->Z)) | ||
1271 | goto err; | ||
1272 | } | ||
1273 | p->Z_is_one = 1; | ||
1274 | } | ||
1275 | } | ||
1276 | |||
1277 | ret = 1; | ||
1278 | |||
1279 | err: | ||
1280 | BN_CTX_end(ctx); | ||
1281 | |||
1282 | if (heap != NULL) { | ||
1283 | /* | ||
1284 | * heap[pow2/2] .. heap[pow2-1] have not been allocated | ||
1285 | * locally! | ||
1286 | */ | ||
1287 | for (i = pow2 / 2 - 1; i > 0; i--) { | ||
1288 | BN_free(heap[i]); | ||
1289 | } | ||
1290 | free(heap); | ||
1291 | } | ||
1292 | return ret; | ||
1293 | } | ||
1294 | |||
1295 | int | ||
1296 | ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | ||
1297 | { | ||
1298 | return BN_mod_mul(r, a, b, &group->field, ctx); | ||
1299 | } | ||
1300 | |||
1301 | int | ||
1302 | ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) | ||
1303 | { | ||
1304 | return BN_mod_sqr(r, a, &group->field, ctx); | ||
1305 | } | ||
1306 | |||
1307 | /* | ||
1308 | * Apply randomization of EC point projective coordinates: | ||
1309 | * | ||
1310 | * (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z) | ||
1311 | * | ||
1312 | * where lambda is in the interval [1, group->field). | ||
1313 | */ | ||
1314 | int | ||
1315 | ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx) | ||
1316 | { | ||
1317 | BIGNUM *lambda = NULL; | ||
1318 | BIGNUM *tmp = NULL; | ||
1319 | int ret = 0; | ||
1320 | |||
1321 | BN_CTX_start(ctx); | ||
1322 | if ((lambda = BN_CTX_get(ctx)) == NULL) | ||
1323 | goto err; | ||
1324 | if ((tmp = BN_CTX_get(ctx)) == NULL) | ||
1325 | goto err; | ||
1326 | |||
1327 | /* Generate lambda in [1, group->field). */ | ||
1328 | if (!bn_rand_interval(lambda, 1, &group->field)) | ||
1329 | goto err; | ||
1330 | |||
1331 | if (group->meth->field_encode != NULL && | ||
1332 | !group->meth->field_encode(group, lambda, lambda, ctx)) | ||
1333 | goto err; | ||
1334 | |||
1335 | /* Z = lambda * Z */ | ||
1336 | if (!group->meth->field_mul(group, &p->Z, lambda, &p->Z, ctx)) | ||
1337 | goto err; | ||
1338 | |||
1339 | /* tmp = lambda^2 */ | ||
1340 | if (!group->meth->field_sqr(group, tmp, lambda, ctx)) | ||
1341 | goto err; | ||
1342 | |||
1343 | /* X = lambda^2 * X */ | ||
1344 | if (!group->meth->field_mul(group, &p->X, tmp, &p->X, ctx)) | ||
1345 | goto err; | ||
1346 | |||
1347 | /* tmp = lambda^3 */ | ||
1348 | if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx)) | ||
1349 | goto err; | ||
1350 | |||
1351 | /* Y = lambda^3 * Y */ | ||
1352 | if (!group->meth->field_mul(group, &p->Y, tmp, &p->Y, ctx)) | ||
1353 | goto err; | ||
1354 | |||
1355 | /* Disable optimized arithmetics after replacing Z by lambda * Z. */ | ||
1356 | p->Z_is_one = 0; | ||
1357 | |||
1358 | ret = 1; | ||
1359 | |||
1360 | err: | ||
1361 | BN_CTX_end(ctx); | ||
1362 | return ret; | ||
1363 | } | ||
1364 | |||
1365 | #define EC_POINT_BN_set_flags(P, flags) do { \ | ||
1366 | BN_set_flags(&(P)->X, (flags)); \ | ||
1367 | BN_set_flags(&(P)->Y, (flags)); \ | ||
1368 | BN_set_flags(&(P)->Z, (flags)); \ | ||
1369 | } while(0) | ||
1370 | |||
1371 | #define EC_POINT_CSWAP(c, a, b, w, t) do { \ | ||
1372 | if (!BN_swap_ct(c, &(a)->X, &(b)->X, w) || \ | ||
1373 | !BN_swap_ct(c, &(a)->Y, &(b)->Y, w) || \ | ||
1374 | !BN_swap_ct(c, &(a)->Z, &(b)->Z, w)) \ | ||
1375 | goto err; \ | ||
1376 | t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \ | ||
1377 | (a)->Z_is_one ^= (t); \ | ||
1378 | (b)->Z_is_one ^= (t); \ | ||
1379 | } while(0) | ||
1380 | |||
1381 | /* | ||
1382 | * This function computes (in constant time) a point multiplication over the | ||
1383 | * EC group. | ||
1384 | * | ||
1385 | * At a high level, it is Montgomery ladder with conditional swaps. | ||
1386 | * | ||
1387 | * It performs either a fixed point multiplication | ||
1388 | * (scalar * generator) | ||
1389 | * when point is NULL, or a variable point multiplication | ||
1390 | * (scalar * point) | ||
1391 | * when point is not NULL. | ||
1392 | * | ||
1393 | * scalar should be in the range [0,n) otherwise all constant time bets are off. | ||
1394 | * | ||
1395 | * NB: This says nothing about EC_POINT_add and EC_POINT_dbl, | ||
1396 | * which of course are not constant time themselves. | ||
1397 | * | ||
1398 | * The product is stored in r. | ||
1399 | * | ||
1400 | * Returns 1 on success, 0 otherwise. | ||
1401 | */ | ||
1402 | static int | ||
1403 | ec_GFp_simple_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, | ||
1404 | const EC_POINT *point, BN_CTX *ctx) | ||
1405 | { | ||
1406 | int i, cardinality_bits, group_top, kbit, pbit, Z_is_one; | ||
1407 | EC_POINT *s = NULL; | ||
1408 | BIGNUM *k = NULL; | ||
1409 | BIGNUM *lambda = NULL; | ||
1410 | BIGNUM *cardinality = NULL; | ||
1411 | int ret = 0; | ||
1412 | |||
1413 | BN_CTX_start(ctx); | ||
1414 | |||
1415 | if ((s = EC_POINT_new(group)) == NULL) | ||
1416 | goto err; | ||
1417 | |||
1418 | if (point == NULL) { | ||
1419 | if (!EC_POINT_copy(s, group->generator)) | ||
1420 | goto err; | ||
1421 | } else { | ||
1422 | if (!EC_POINT_copy(s, point)) | ||
1423 | goto err; | ||
1424 | } | ||
1425 | |||
1426 | EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME); | ||
1427 | |||
1428 | if ((cardinality = BN_CTX_get(ctx)) == NULL) | ||
1429 | goto err; | ||
1430 | if ((lambda = BN_CTX_get(ctx)) == NULL) | ||
1431 | goto err; | ||
1432 | if ((k = BN_CTX_get(ctx)) == NULL) | ||
1433 | goto err; | ||
1434 | if (!BN_mul(cardinality, &group->order, &group->cofactor, ctx)) | ||
1435 | goto err; | ||
1436 | |||
1437 | /* | ||
1438 | * Group cardinalities are often on a word boundary. | ||
1439 | * So when we pad the scalar, some timing diff might | ||
1440 | * pop if it needs to be expanded due to carries. | ||
1441 | * So expand ahead of time. | ||
1442 | */ | ||
1443 | cardinality_bits = BN_num_bits(cardinality); | ||
1444 | group_top = cardinality->top; | ||
1445 | if (!bn_wexpand(k, group_top + 2) || | ||
1446 | !bn_wexpand(lambda, group_top + 2)) | ||
1447 | goto err; | ||
1448 | |||
1449 | if (!bn_copy(k, scalar)) | ||
1450 | goto err; | ||
1451 | |||
1452 | BN_set_flags(k, BN_FLG_CONSTTIME); | ||
1453 | |||
1454 | if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) { | ||
1455 | /* | ||
1456 | * This is an unusual input, and we don't guarantee | ||
1457 | * constant-timeness | ||
1458 | */ | ||
1459 | if (!BN_nnmod(k, k, cardinality, ctx)) | ||
1460 | goto err; | ||
1461 | } | ||
1462 | |||
1463 | if (!BN_add(lambda, k, cardinality)) | ||
1464 | goto err; | ||
1465 | BN_set_flags(lambda, BN_FLG_CONSTTIME); | ||
1466 | if (!BN_add(k, lambda, cardinality)) | ||
1467 | goto err; | ||
1468 | /* | ||
1469 | * lambda := scalar + cardinality | ||
1470 | * k := scalar + 2*cardinality | ||
1471 | */ | ||
1472 | kbit = BN_is_bit_set(lambda, cardinality_bits); | ||
1473 | if (!BN_swap_ct(kbit, k, lambda, group_top + 2)) | ||
1474 | goto err; | ||
1475 | |||
1476 | group_top = group->field.top; | ||
1477 | if (!bn_wexpand(&s->X, group_top) || | ||
1478 | !bn_wexpand(&s->Y, group_top) || | ||
1479 | !bn_wexpand(&s->Z, group_top) || | ||
1480 | !bn_wexpand(&r->X, group_top) || | ||
1481 | !bn_wexpand(&r->Y, group_top) || | ||
1482 | !bn_wexpand(&r->Z, group_top)) | ||
1483 | goto err; | ||
1484 | |||
1485 | /* | ||
1486 | * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD | ||
1487 | * implements it. | ||
1488 | */ | ||
1489 | if (!ec_point_blind_coordinates(group, s, ctx)) | ||
1490 | goto err; | ||
1491 | |||
1492 | /* top bit is a 1, in a fixed pos */ | ||
1493 | if (!EC_POINT_copy(r, s)) | ||
1494 | goto err; | ||
1495 | |||
1496 | EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); | ||
1497 | |||
1498 | if (!EC_POINT_dbl(group, s, s, ctx)) | ||
1499 | goto err; | ||
1500 | |||
1501 | pbit = 0; | ||
1502 | |||
1503 | /* | ||
1504 | * The ladder step, with branches, is | ||
1505 | * | ||
1506 | * k[i] == 0: S = add(R, S), R = dbl(R) | ||
1507 | * k[i] == 1: R = add(S, R), S = dbl(S) | ||
1508 | * | ||
1509 | * Swapping R, S conditionally on k[i] leaves you with state | ||
1510 | * | ||
1511 | * k[i] == 0: T, U = R, S | ||
1512 | * k[i] == 1: T, U = S, R | ||
1513 | * | ||
1514 | * Then perform the ECC ops. | ||
1515 | * | ||
1516 | * U = add(T, U) | ||
1517 | * T = dbl(T) | ||
1518 | * | ||
1519 | * Which leaves you with state | ||
1520 | * | ||
1521 | * k[i] == 0: U = add(R, S), T = dbl(R) | ||
1522 | * k[i] == 1: U = add(S, R), T = dbl(S) | ||
1523 | * | ||
1524 | * Swapping T, U conditionally on k[i] leaves you with state | ||
1525 | * | ||
1526 | * k[i] == 0: R, S = T, U | ||
1527 | * k[i] == 1: R, S = U, T | ||
1528 | * | ||
1529 | * Which leaves you with state | ||
1530 | * | ||
1531 | * k[i] == 0: S = add(R, S), R = dbl(R) | ||
1532 | * k[i] == 1: R = add(S, R), S = dbl(S) | ||
1533 | * | ||
1534 | * So we get the same logic, but instead of a branch it's a | ||
1535 | * conditional swap, followed by ECC ops, then another conditional swap. | ||
1536 | * | ||
1537 | * Optimization: The end of iteration i and start of i-1 looks like | ||
1538 | * | ||
1539 | * ... | ||
1540 | * CSWAP(k[i], R, S) | ||
1541 | * ECC | ||
1542 | * CSWAP(k[i], R, S) | ||
1543 | * (next iteration) | ||
1544 | * CSWAP(k[i-1], R, S) | ||
1545 | * ECC | ||
1546 | * CSWAP(k[i-1], R, S) | ||
1547 | * ... | ||
1548 | * | ||
1549 | * So instead of two contiguous swaps, you can merge the condition | ||
1550 | * bits and do a single swap. | ||
1551 | * | ||
1552 | * k[i] k[i-1] Outcome | ||
1553 | * 0 0 No Swap | ||
1554 | * 0 1 Swap | ||
1555 | * 1 0 Swap | ||
1556 | * 1 1 No Swap | ||
1557 | * | ||
1558 | * This is XOR. pbit tracks the previous bit of k. | ||
1559 | */ | ||
1560 | |||
1561 | for (i = cardinality_bits - 1; i >= 0; i--) { | ||
1562 | kbit = BN_is_bit_set(k, i) ^ pbit; | ||
1563 | EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); | ||
1564 | if (!EC_POINT_add(group, s, r, s, ctx)) | ||
1565 | goto err; | ||
1566 | if (!EC_POINT_dbl(group, r, r, ctx)) | ||
1567 | goto err; | ||
1568 | /* | ||
1569 | * pbit logic merges this cswap with that of the | ||
1570 | * next iteration | ||
1571 | */ | ||
1572 | pbit ^= kbit; | ||
1573 | } | ||
1574 | /* one final cswap to move the right value into r */ | ||
1575 | EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); | ||
1576 | |||
1577 | ret = 1; | ||
1578 | |||
1579 | err: | ||
1580 | EC_POINT_free(s); | ||
1581 | BN_CTX_end(ctx); | ||
1582 | |||
1583 | return ret; | ||
1584 | } | ||
1585 | |||
1586 | #undef EC_POINT_BN_set_flags | ||
1587 | #undef EC_POINT_CSWAP | ||
1588 | |||
1589 | int | ||
1590 | ec_GFp_simple_mul_generator_ct(const EC_GROUP *group, EC_POINT *r, | ||
1591 | const BIGNUM *scalar, BN_CTX *ctx) | ||
1592 | { | ||
1593 | return ec_GFp_simple_mul_ct(group, r, scalar, NULL, ctx); | ||
1594 | } | ||
1595 | |||
1596 | int | ||
1597 | ec_GFp_simple_mul_single_ct(const EC_GROUP *group, EC_POINT *r, | ||
1598 | const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx) | ||
1599 | { | ||
1600 | return ec_GFp_simple_mul_ct(group, r, scalar, point, ctx); | ||
1601 | } | ||
1602 | |||
1603 | int | ||
1604 | ec_GFp_simple_mul_double_nonct(const EC_GROUP *group, EC_POINT *r, | ||
1605 | const BIGNUM *g_scalar, const BIGNUM *p_scalar, const EC_POINT *point, | ||
1606 | BN_CTX *ctx) | ||
1607 | { | ||
1608 | return ec_wNAF_mul(group, r, g_scalar, 1, &point, &p_scalar, ctx); | ||
1609 | } | ||
1610 | |||
1611 | static const EC_METHOD ec_GFp_simple_method = { | ||
1612 | .field_type = NID_X9_62_prime_field, | ||
1613 | .group_init = ec_GFp_simple_group_init, | ||
1614 | .group_finish = ec_GFp_simple_group_finish, | ||
1615 | .group_copy = ec_GFp_simple_group_copy, | ||
1616 | .group_set_curve = ec_GFp_simple_group_set_curve, | ||
1617 | .group_get_curve = ec_GFp_simple_group_get_curve, | ||
1618 | .group_get_degree = ec_GFp_simple_group_get_degree, | ||
1619 | .group_order_bits = ec_group_simple_order_bits, | ||
1620 | .group_check_discriminant = ec_GFp_simple_group_check_discriminant, | ||
1621 | .point_init = ec_GFp_simple_point_init, | ||
1622 | .point_finish = ec_GFp_simple_point_finish, | ||
1623 | .point_copy = ec_GFp_simple_point_copy, | ||
1624 | .point_set_to_infinity = ec_GFp_simple_point_set_to_infinity, | ||
1625 | .point_set_Jprojective_coordinates = | ||
1626 | ec_GFp_simple_set_Jprojective_coordinates, | ||
1627 | .point_get_Jprojective_coordinates = | ||
1628 | ec_GFp_simple_get_Jprojective_coordinates, | ||
1629 | .point_set_affine_coordinates = | ||
1630 | ec_GFp_simple_point_set_affine_coordinates, | ||
1631 | .point_get_affine_coordinates = | ||
1632 | ec_GFp_simple_point_get_affine_coordinates, | ||
1633 | .point_set_compressed_coordinates = | ||
1634 | ec_GFp_simple_set_compressed_coordinates, | ||
1635 | .add = ec_GFp_simple_add, | ||
1636 | .dbl = ec_GFp_simple_dbl, | ||
1637 | .invert = ec_GFp_simple_invert, | ||
1638 | .is_at_infinity = ec_GFp_simple_is_at_infinity, | ||
1639 | .is_on_curve = ec_GFp_simple_is_on_curve, | ||
1640 | .point_cmp = ec_GFp_simple_cmp, | ||
1641 | .make_affine = ec_GFp_simple_make_affine, | ||
1642 | .points_make_affine = ec_GFp_simple_points_make_affine, | ||
1643 | .mul_generator_ct = ec_GFp_simple_mul_generator_ct, | ||
1644 | .mul_single_ct = ec_GFp_simple_mul_single_ct, | ||
1645 | .mul_double_nonct = ec_GFp_simple_mul_double_nonct, | ||
1646 | .field_mul = ec_GFp_simple_field_mul, | ||
1647 | .field_sqr = ec_GFp_simple_field_sqr, | ||
1648 | .blind_coordinates = ec_GFp_simple_blind_coordinates, | ||
1649 | }; | ||
1650 | |||
1651 | const EC_METHOD * | ||
1652 | EC_GFp_simple_method(void) | ||
1653 | { | ||
1654 | return &ec_GFp_simple_method; | ||
1655 | } | ||
1656 | LCRYPTO_ALIAS(EC_GFp_simple_method); | ||