summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ecp_methods.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/ec/ecp_methods.c')
-rw-r--r--src/lib/libcrypto/ec/ecp_methods.c1656
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
89int
90ec_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
99void
100ec_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
107int
108ec_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
122static int
123ec_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
134static int
135ec_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
146static int
147ec_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
163int
164ec_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
205int
206ec_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
221int
222ec_GFp_simple_group_get_degree(const EC_GROUP *group)
223{
224 return BN_num_bits(&group->field);
225}
226
227int
228ec_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
284int
285ec_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
295void
296ec_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
304int
305ec_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
318int
319ec_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
326int
327ec_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
358int
359ec_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
377int
378ec_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
390int
391ec_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
471int
472ec_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
569int
570ec_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
751int
752ec_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
885int
886ec_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
895int
896ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
897{
898 return BN_is_zero(&point->Z);
899}
900
901int
902ec_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
998int
999ec_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
1094int
1095ec_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
1126int
1127ec_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
1295int
1296ec_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
1301int
1302ec_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 */
1314int
1315ec_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 */
1402static int
1403ec_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
1589int
1590ec_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
1596int
1597ec_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
1603int
1604ec_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
1611static 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
1651const EC_METHOD *
1652EC_GFp_simple_method(void)
1653{
1654 return &ec_GFp_simple_method;
1655}
1656LCRYPTO_ALIAS(EC_GFp_simple_method);
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-11-28 11:06:04 +0000