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.c1327
1 files changed, 0 insertions, 1327 deletions
diff --git a/src/lib/libcrypto/ec/ecp_methods.c b/src/lib/libcrypto/ec/ecp_methods.c
deleted file mode 100644
index ced85ceb1e..0000000000
--- a/src/lib/libcrypto/ec/ecp_methods.c
+++ /dev/null
@@ -1,1327 +0,0 @@
1/* $OpenBSD: ecp_methods.c,v 1.45 2025/03/24 13:07:04 jsing 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 non-trivial
77 * representations of field elements if necessary: while standard modular
78 * addition and subtraction are used, the field_mul and field_sqr methods will
79 * be used for multiplication, and field_encode and field_decode (if defined)
80 * will be used for converting between representations.
81 *
82 * The functions ec_points_make_affine() and ec_point_get_affine_coordinates()
83 * assume that if a non-trivial representation is used, it is a Montgomery
84 * representation (i.e. 'encoding' means multiplying by some factor R).
85 */
86
87static inline int
88ec_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
89 BN_CTX *ctx)
90{
91 return group->meth->field_mul(group, r, a, b, ctx);
92}
93
94static inline int
95ec_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
96{
97 return group->meth->field_sqr(group, r, a, ctx);
98}
99
100static int
101ec_decode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx)
102{
103 if (bn == NULL)
104 return 1;
105
106 if (group->meth->field_decode != NULL)
107 return group->meth->field_decode(group, bn, x, ctx);
108
109 return bn_copy(bn, x);
110}
111
112static int
113ec_encode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx)
114{
115 if (!BN_nnmod(bn, x, group->p, ctx))
116 return 0;
117
118 if (group->meth->field_encode != NULL)
119 return group->meth->field_encode(group, bn, bn, ctx);
120
121 return 1;
122}
123
124static int
125ec_group_set_curve(EC_GROUP *group,
126 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
127{
128 BIGNUM *a_plus_3;
129 int ret = 0;
130
131 /* p must be a prime > 3 */
132 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
133 ECerror(EC_R_INVALID_FIELD);
134 return 0;
135 }
136
137 BN_CTX_start(ctx);
138
139 if ((a_plus_3 = BN_CTX_get(ctx)) == NULL)
140 goto err;
141
142 if (!bn_copy(group->p, p))
143 goto err;
144 BN_set_negative(group->p, 0);
145
146 if (!ec_encode_scalar(group, group->a, a, ctx))
147 goto err;
148 if (!ec_encode_scalar(group, group->b, b, ctx))
149 goto err;
150
151 if (!BN_set_word(a_plus_3, 3))
152 goto err;
153 if (!BN_mod_add(a_plus_3, a_plus_3, a, group->p, ctx))
154 goto err;
155
156 group->a_is_minus3 = BN_is_zero(a_plus_3);
157
158 ret = 1;
159
160 err:
161 BN_CTX_end(ctx);
162
163 return ret;
164}
165
166static int
167ec_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b,
168 BN_CTX *ctx)
169{
170 if (p != NULL) {
171 if (!bn_copy(p, group->p))
172 return 0;
173 }
174 if (!ec_decode_scalar(group, a, group->a, ctx))
175 return 0;
176 if (!ec_decode_scalar(group, b, group->b, ctx))
177 return 0;
178
179 return 1;
180}
181
182static int
183ec_point_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
184{
185 BIGNUM *rh, *tmp, *Z4, *Z6;
186 int ret = -1;
187
188 if (EC_POINT_is_at_infinity(group, point))
189 return 1;
190
191 BN_CTX_start(ctx);
192
193 if ((rh = BN_CTX_get(ctx)) == NULL)
194 goto err;
195 if ((tmp = BN_CTX_get(ctx)) == NULL)
196 goto err;
197 if ((Z4 = BN_CTX_get(ctx)) == NULL)
198 goto err;
199 if ((Z6 = BN_CTX_get(ctx)) == NULL)
200 goto err;
201
202 /*
203 * The curve is defined by a Weierstrass equation y^2 = x^3 + a*x + b.
204 * The point is given in Jacobian projective coordinates where (X, Y, Z)
205 * represents (x, y) = (X/Z^2, Y/Z^3). Substituting this and multiplying
206 * by Z^6 transforms the above into Y^2 = X^3 + a*X*Z^4 + b*Z^6.
207 */
208
209 /* rh := X^2 */
210 if (!ec_field_sqr(group, rh, point->X, ctx))
211 goto err;
212
213 if (!point->Z_is_one) {
214 if (!ec_field_sqr(group, tmp, point->Z, ctx))
215 goto err;
216 if (!ec_field_sqr(group, Z4, tmp, ctx))
217 goto err;
218 if (!ec_field_mul(group, Z6, Z4, tmp, ctx))
219 goto err;
220
221 /* rh := (rh + a*Z^4)*X */
222 if (group->a_is_minus3) {
223 if (!BN_mod_lshift1_quick(tmp, Z4, group->p))
224 goto err;
225 if (!BN_mod_add_quick(tmp, tmp, Z4, group->p))
226 goto err;
227 if (!BN_mod_sub_quick(rh, rh, tmp, group->p))
228 goto err;
229 if (!ec_field_mul(group, rh, rh, point->X, ctx))
230 goto err;
231 } else {
232 if (!ec_field_mul(group, tmp, Z4, group->a, ctx))
233 goto err;
234 if (!BN_mod_add_quick(rh, rh, tmp, group->p))
235 goto err;
236 if (!ec_field_mul(group, rh, rh, point->X, ctx))
237 goto err;
238 }
239
240 /* rh := rh + b*Z^6 */
241 if (!ec_field_mul(group, tmp, group->b, Z6, ctx))
242 goto err;
243 if (!BN_mod_add_quick(rh, rh, tmp, group->p))
244 goto err;
245 } else {
246 /* point->Z_is_one */
247
248 /* rh := (rh + a)*X */
249 if (!BN_mod_add_quick(rh, rh, group->a, group->p))
250 goto err;
251 if (!ec_field_mul(group, rh, rh, point->X, ctx))
252 goto err;
253 /* rh := rh + b */
254 if (!BN_mod_add_quick(rh, rh, group->b, group->p))
255 goto err;
256 }
257
258 /* 'lh' := Y^2 */
259 if (!ec_field_sqr(group, tmp, point->Y, ctx))
260 goto err;
261
262 ret = (0 == BN_ucmp(tmp, rh));
263
264 err:
265 BN_CTX_end(ctx);
266
267 return ret;
268}
269
270/*
271 * Returns -1 on error, 0 if the points are equal, 1 if the points are distinct.
272 */
273
274static int
275ec_point_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
276 BN_CTX *ctx)
277{
278 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
279 const BIGNUM *tmp1_, *tmp2_;
280 int ret = -1;
281
282 if (EC_POINT_is_at_infinity(group, a) && EC_POINT_is_at_infinity(group, b))
283 return 0;
284 if (EC_POINT_is_at_infinity(group, a) || EC_POINT_is_at_infinity(group, b))
285 return 1;
286
287 if (a->Z_is_one && b->Z_is_one)
288 return BN_cmp(a->X, b->X) != 0 || BN_cmp(a->Y, b->Y) != 0;
289
290 BN_CTX_start(ctx);
291
292 if ((tmp1 = BN_CTX_get(ctx)) == NULL)
293 goto end;
294 if ((tmp2 = BN_CTX_get(ctx)) == NULL)
295 goto end;
296 if ((Za23 = BN_CTX_get(ctx)) == NULL)
297 goto end;
298 if ((Zb23 = BN_CTX_get(ctx)) == NULL)
299 goto end;
300
301 /*
302 * Decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), or
303 * equivalently, (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
304 */
305
306 if (!b->Z_is_one) {
307 if (!ec_field_sqr(group, Zb23, b->Z, ctx))
308 goto end;
309 if (!ec_field_mul(group, tmp1, a->X, Zb23, ctx))
310 goto end;
311 tmp1_ = tmp1;
312 } else
313 tmp1_ = a->X;
314 if (!a->Z_is_one) {
315 if (!ec_field_sqr(group, Za23, a->Z, ctx))
316 goto end;
317 if (!ec_field_mul(group, tmp2, b->X, Za23, ctx))
318 goto end;
319 tmp2_ = tmp2;
320 } else
321 tmp2_ = b->X;
322
323 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
324 if (BN_cmp(tmp1_, tmp2_) != 0) {
325 ret = 1; /* points differ */
326 goto end;
327 }
328 if (!b->Z_is_one) {
329 if (!ec_field_mul(group, Zb23, Zb23, b->Z, ctx))
330 goto end;
331 if (!ec_field_mul(group, tmp1, a->Y, Zb23, ctx))
332 goto end;
333 /* tmp1_ = tmp1 */
334 } else
335 tmp1_ = a->Y;
336 if (!a->Z_is_one) {
337 if (!ec_field_mul(group, Za23, Za23, a->Z, ctx))
338 goto end;
339 if (!ec_field_mul(group, tmp2, b->Y, Za23, ctx))
340 goto end;
341 /* tmp2_ = tmp2 */
342 } else
343 tmp2_ = b->Y;
344
345 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
346 if (BN_cmp(tmp1_, tmp2_) != 0) {
347 ret = 1; /* points differ */
348 goto end;
349 }
350 /* points are equal */
351 ret = 0;
352
353 end:
354 BN_CTX_end(ctx);
355
356 return ret;
357}
358
359static int
360ec_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
361 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
362{
363 int ret = 0;
364
365 if (x == NULL || y == NULL) {
366 ECerror(ERR_R_PASSED_NULL_PARAMETER);
367 goto err;
368 }
369
370 if (!ec_encode_scalar(group, point->X, x, ctx))
371 goto err;
372 if (!ec_encode_scalar(group, point->Y, y, ctx))
373 goto err;
374 if (!ec_encode_scalar(group, point->Z, BN_value_one(), ctx))
375 goto err;
376 point->Z_is_one = 1;
377
378 ret = 1;
379
380 err:
381 return ret;
382}
383
384static int
385ec_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
386 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
387{
388 BIGNUM *z, *Z, *Z_1, *Z_2, *Z_3;
389 int ret = 0;
390
391 BN_CTX_start(ctx);
392
393 if ((z = BN_CTX_get(ctx)) == NULL)
394 goto err;
395 if ((Z = BN_CTX_get(ctx)) == NULL)
396 goto err;
397 if ((Z_1 = BN_CTX_get(ctx)) == NULL)
398 goto err;
399 if ((Z_2 = BN_CTX_get(ctx)) == NULL)
400 goto err;
401 if ((Z_3 = BN_CTX_get(ctx)) == NULL)
402 goto err;
403
404 /*
405 * Convert from Jacobian projective coordinates (X, Y, Z) into
406 * (X/Z^2, Y/Z^3).
407 */
408
409 if (!ec_decode_scalar(group, z, point->Z, ctx))
410 goto err;
411
412 if (BN_is_one(z)) {
413 if (!ec_decode_scalar(group, x, point->X, ctx))
414 goto err;
415 if (!ec_decode_scalar(group, y, point->Y, ctx))
416 goto err;
417 goto done;
418 }
419
420 if (BN_mod_inverse_ct(Z_1, z, group->p, ctx) == NULL) {
421 ECerror(ERR_R_BN_LIB);
422 goto err;
423 }
424 if (group->meth->field_encode == NULL) {
425 /* field_sqr works on standard representation */
426 if (!ec_field_sqr(group, Z_2, Z_1, ctx))
427 goto err;
428 } else {
429 if (!BN_mod_sqr(Z_2, Z_1, group->p, ctx))
430 goto err;
431 }
432
433 if (x != NULL) {
434 /*
435 * in the Montgomery case, field_mul will cancel out
436 * Montgomery factor in X:
437 */
438 if (!ec_field_mul(group, x, point->X, Z_2, ctx))
439 goto err;
440 }
441 if (y != NULL) {
442 if (group->meth->field_encode == NULL) {
443 /* field_mul works on standard representation */
444 if (!ec_field_mul(group, Z_3, Z_2, Z_1, ctx))
445 goto err;
446 } else {
447 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->p, ctx))
448 goto err;
449 }
450
451 /*
452 * in the Montgomery case, field_mul will cancel out
453 * Montgomery factor in Y:
454 */
455 if (!ec_field_mul(group, y, point->Y, Z_3, ctx))
456 goto err;
457 }
458
459 done:
460 ret = 1;
461
462 err:
463 BN_CTX_end(ctx);
464
465 return ret;
466}
467
468static int
469ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT **points,
470 BN_CTX *ctx)
471{
472 BIGNUM **prod_Z = NULL;
473 BIGNUM *one, *tmp, *tmp_Z;
474 size_t i;
475 int ret = 0;
476
477 if (num == 0)
478 return 1;
479
480 BN_CTX_start(ctx);
481
482 if ((one = BN_CTX_get(ctx)) == NULL)
483 goto err;
484 if ((tmp = BN_CTX_get(ctx)) == NULL)
485 goto err;
486 if ((tmp_Z = BN_CTX_get(ctx)) == NULL)
487 goto err;
488
489 if (!ec_encode_scalar(group, one, BN_value_one(), ctx))
490 goto err;
491
492 if ((prod_Z = calloc(num, sizeof *prod_Z)) == NULL)
493 goto err;
494 for (i = 0; i < num; i++) {
495 if ((prod_Z[i] = BN_CTX_get(ctx)) == NULL)
496 goto err;
497 }
498
499 /*
500 * Set prod_Z[i] to the product of points[0]->Z, ..., points[i]->Z,
501 * skipping any zero-valued inputs (pretend that they're 1).
502 */
503
504 if (!BN_is_zero(points[0]->Z)) {
505 if (!bn_copy(prod_Z[0], points[0]->Z))
506 goto err;
507 } else {
508 if (!bn_copy(prod_Z[0], one))
509 goto err;
510 }
511
512 for (i = 1; i < num; i++) {
513 if (!BN_is_zero(points[i]->Z)) {
514 if (!ec_field_mul(group, prod_Z[i],
515 prod_Z[i - 1], points[i]->Z, ctx))
516 goto err;
517 } else {
518 if (!bn_copy(prod_Z[i], prod_Z[i - 1]))
519 goto err;
520 }
521 }
522
523 /*
524 * Now use a single explicit inversion to replace every non-zero
525 * points[i]->Z by its inverse.
526 */
527 if (!BN_mod_inverse_nonct(tmp, prod_Z[num - 1], group->p, ctx)) {
528 ECerror(ERR_R_BN_LIB);
529 goto err;
530 }
531
532 if (group->meth->field_encode != NULL) {
533 /*
534 * In the Montgomery case we just turned R*H (representing H)
535 * into 1/(R*H), but we need R*(1/H) (representing 1/H); i.e.,
536 * we need to multiply by the Montgomery factor twice.
537 */
538 if (!group->meth->field_encode(group, tmp, tmp, ctx))
539 goto err;
540 if (!group->meth->field_encode(group, tmp, tmp, ctx))
541 goto err;
542 }
543
544 for (i = num - 1; i > 0; i--) {
545 /*
546 * Loop invariant: tmp is the product of the inverses of
547 * points[0]->Z, ..., points[i]->Z (zero-valued inputs skipped).
548 */
549 if (BN_is_zero(points[i]->Z))
550 continue;
551
552 /* Set tmp_Z to the inverse of points[i]->Z. */
553 if (!ec_field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
554 goto err;
555 /* Adjust tmp to satisfy loop invariant. */
556 if (!ec_field_mul(group, tmp, tmp, points[i]->Z, ctx))
557 goto err;
558 /* Replace points[i]->Z by its inverse. */
559 if (!bn_copy(points[i]->Z, tmp_Z))
560 goto err;
561 }
562
563 if (!BN_is_zero(points[0]->Z)) {
564 /* Replace points[0]->Z by its inverse. */
565 if (!bn_copy(points[0]->Z, tmp))
566 goto err;
567 }
568
569 /* Finally, fix up the X and Y coordinates for all points. */
570 for (i = 0; i < num; i++) {
571 EC_POINT *p = points[i];
572
573 if (BN_is_zero(p->Z))
574 continue;
575
576 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
577
578 if (!ec_field_sqr(group, tmp, p->Z, ctx))
579 goto err;
580 if (!ec_field_mul(group, p->X, p->X, tmp, ctx))
581 goto err;
582
583 if (!ec_field_mul(group, tmp, tmp, p->Z, ctx))
584 goto err;
585 if (!ec_field_mul(group, p->Y, p->Y, tmp, ctx))
586 goto err;
587
588 if (!bn_copy(p->Z, one))
589 goto err;
590 p->Z_is_one = 1;
591 }
592
593 ret = 1;
594
595 err:
596 BN_CTX_end(ctx);
597 free(prod_Z);
598
599 return ret;
600}
601
602static int
603ec_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b,
604 BN_CTX *ctx)
605{
606 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
607 int ret = 0;
608
609 if (a == b)
610 return EC_POINT_dbl(group, r, a, ctx);
611 if (EC_POINT_is_at_infinity(group, a))
612 return EC_POINT_copy(r, b);
613 if (EC_POINT_is_at_infinity(group, b))
614 return EC_POINT_copy(r, a);
615
616 BN_CTX_start(ctx);
617
618 if ((n0 = BN_CTX_get(ctx)) == NULL)
619 goto end;
620 if ((n1 = BN_CTX_get(ctx)) == NULL)
621 goto end;
622 if ((n2 = BN_CTX_get(ctx)) == NULL)
623 goto end;
624 if ((n3 = BN_CTX_get(ctx)) == NULL)
625 goto end;
626 if ((n4 = BN_CTX_get(ctx)) == NULL)
627 goto end;
628 if ((n5 = BN_CTX_get(ctx)) == NULL)
629 goto end;
630 if ((n6 = BN_CTX_get(ctx)) == NULL)
631 goto end;
632
633 /*
634 * Note that in this function we must not read components of 'a' or
635 * 'b' once we have written the corresponding components of 'r'. ('r'
636 * might be one of 'a' or 'b'.)
637 */
638
639 /* n1, n2 */
640 if (b->Z_is_one) {
641 if (!bn_copy(n1, a->X))
642 goto end;
643 if (!bn_copy(n2, a->Y))
644 goto end;
645 /* n1 = X_a */
646 /* n2 = Y_a */
647 } else {
648 if (!ec_field_sqr(group, n0, b->Z, ctx))
649 goto end;
650 if (!ec_field_mul(group, n1, a->X, n0, ctx))
651 goto end;
652 /* n1 = X_a * Z_b^2 */
653
654 if (!ec_field_mul(group, n0, n0, b->Z, ctx))
655 goto end;
656 if (!ec_field_mul(group, n2, a->Y, n0, ctx))
657 goto end;
658 /* n2 = Y_a * Z_b^3 */
659 }
660
661 /* n3, n4 */
662 if (a->Z_is_one) {
663 if (!bn_copy(n3, b->X))
664 goto end;
665 if (!bn_copy(n4, b->Y))
666 goto end;
667 /* n3 = X_b */
668 /* n4 = Y_b */
669 } else {
670 if (!ec_field_sqr(group, n0, a->Z, ctx))
671 goto end;
672 if (!ec_field_mul(group, n3, b->X, n0, ctx))
673 goto end;
674 /* n3 = X_b * Z_a^2 */
675
676 if (!ec_field_mul(group, n0, n0, a->Z, ctx))
677 goto end;
678 if (!ec_field_mul(group, n4, b->Y, n0, ctx))
679 goto end;
680 /* n4 = Y_b * Z_a^3 */
681 }
682
683 /* n5, n6 */
684 if (!BN_mod_sub_quick(n5, n1, n3, group->p))
685 goto end;
686 if (!BN_mod_sub_quick(n6, n2, n4, group->p))
687 goto end;
688 /* n5 = n1 - n3 */
689 /* n6 = n2 - n4 */
690
691 if (BN_is_zero(n5)) {
692 if (BN_is_zero(n6)) {
693 /* a is the same point as b */
694 BN_CTX_end(ctx);
695 ret = EC_POINT_dbl(group, r, a, ctx);
696 ctx = NULL;
697 goto end;
698 } else {
699 /* a is the inverse of b */
700 BN_zero(r->Z);
701 r->Z_is_one = 0;
702 ret = 1;
703 goto end;
704 }
705 }
706 /* 'n7', 'n8' */
707 if (!BN_mod_add_quick(n1, n1, n3, group->p))
708 goto end;
709 if (!BN_mod_add_quick(n2, n2, n4, group->p))
710 goto end;
711 /* 'n7' = n1 + n3 */
712 /* 'n8' = n2 + n4 */
713
714 /* Z_r */
715 if (a->Z_is_one && b->Z_is_one) {
716 if (!bn_copy(r->Z, n5))
717 goto end;
718 } else {
719 if (a->Z_is_one) {
720 if (!bn_copy(n0, b->Z))
721 goto end;
722 } else if (b->Z_is_one) {
723 if (!bn_copy(n0, a->Z))
724 goto end;
725 } else {
726 if (!ec_field_mul(group, n0, a->Z, b->Z, ctx))
727 goto end;
728 }
729 if (!ec_field_mul(group, r->Z, n0, n5, ctx))
730 goto end;
731 }
732 r->Z_is_one = 0;
733 /* Z_r = Z_a * Z_b * n5 */
734
735 /* X_r */
736 if (!ec_field_sqr(group, n0, n6, ctx))
737 goto end;
738 if (!ec_field_sqr(group, n4, n5, ctx))
739 goto end;
740 if (!ec_field_mul(group, n3, n1, n4, ctx))
741 goto end;
742 if (!BN_mod_sub_quick(r->X, n0, n3, group->p))
743 goto end;
744 /* X_r = n6^2 - n5^2 * 'n7' */
745
746 /* 'n9' */
747 if (!BN_mod_lshift1_quick(n0, r->X, group->p))
748 goto end;
749 if (!BN_mod_sub_quick(n0, n3, n0, group->p))
750 goto end;
751 /* n9 = n5^2 * 'n7' - 2 * X_r */
752
753 /* Y_r */
754 if (!ec_field_mul(group, n0, n0, n6, ctx))
755 goto end;
756 if (!ec_field_mul(group, n5, n4, n5, ctx))
757 goto end; /* now n5 is n5^3 */
758 if (!ec_field_mul(group, n1, n2, n5, ctx))
759 goto end;
760 if (!BN_mod_sub_quick(n0, n0, n1, group->p))
761 goto end;
762 if (BN_is_odd(n0))
763 if (!BN_add(n0, n0, group->p))
764 goto end;
765 /* now 0 <= n0 < 2*p, and n0 is even */
766 if (!BN_rshift1(r->Y, n0))
767 goto end;
768 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
769
770 ret = 1;
771
772 end:
773 BN_CTX_end(ctx);
774
775 return ret;
776}
777
778static int
779ec_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
780{
781 BIGNUM *n0, *n1, *n2, *n3;
782 int ret = 0;
783
784 if (EC_POINT_is_at_infinity(group, a))
785 return EC_POINT_set_to_infinity(group, r);
786
787 BN_CTX_start(ctx);
788
789 if ((n0 = BN_CTX_get(ctx)) == NULL)
790 goto err;
791 if ((n1 = BN_CTX_get(ctx)) == NULL)
792 goto err;
793 if ((n2 = BN_CTX_get(ctx)) == NULL)
794 goto err;
795 if ((n3 = BN_CTX_get(ctx)) == NULL)
796 goto err;
797
798 /*
799 * Note that in this function we must not read components of 'a' once
800 * we have written the corresponding components of 'r'. ('r' might
801 * the same as 'a'.)
802 */
803
804 /* n1 */
805 if (a->Z_is_one) {
806 if (!ec_field_sqr(group, n0, a->X, ctx))
807 goto err;
808 if (!BN_mod_lshift1_quick(n1, n0, group->p))
809 goto err;
810 if (!BN_mod_add_quick(n0, n0, n1, group->p))
811 goto err;
812 if (!BN_mod_add_quick(n1, n0, group->a, group->p))
813 goto err;
814 /* n1 = 3 * X_a^2 + a_curve */
815 } else if (group->a_is_minus3) {
816 if (!ec_field_sqr(group, n1, a->Z, ctx))
817 goto err;
818 if (!BN_mod_add_quick(n0, a->X, n1, group->p))
819 goto err;
820 if (!BN_mod_sub_quick(n2, a->X, n1, group->p))
821 goto err;
822 if (!ec_field_mul(group, n1, n0, n2, ctx))
823 goto err;
824 if (!BN_mod_lshift1_quick(n0, n1, group->p))
825 goto err;
826 if (!BN_mod_add_quick(n1, n0, n1, group->p))
827 goto err;
828 /*
829 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 *
830 * Z_a^4
831 */
832 } else {
833 if (!ec_field_sqr(group, n0, a->X, ctx))
834 goto err;
835 if (!BN_mod_lshift1_quick(n1, n0, group->p))
836 goto err;
837 if (!BN_mod_add_quick(n0, n0, n1, group->p))
838 goto err;
839 if (!ec_field_sqr(group, n1, a->Z, ctx))
840 goto err;
841 if (!ec_field_sqr(group, n1, n1, ctx))
842 goto err;
843 if (!ec_field_mul(group, n1, n1, group->a, ctx))
844 goto err;
845 if (!BN_mod_add_quick(n1, n1, n0, group->p))
846 goto err;
847 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
848 }
849
850 /* Z_r */
851 if (a->Z_is_one) {
852 if (!bn_copy(n0, a->Y))
853 goto err;
854 } else {
855 if (!ec_field_mul(group, n0, a->Y, a->Z, ctx))
856 goto err;
857 }
858 if (!BN_mod_lshift1_quick(r->Z, n0, group->p))
859 goto err;
860 r->Z_is_one = 0;
861 /* Z_r = 2 * Y_a * Z_a */
862
863 /* n2 */
864 if (!ec_field_sqr(group, n3, a->Y, ctx))
865 goto err;
866 if (!ec_field_mul(group, n2, a->X, n3, ctx))
867 goto err;
868 if (!BN_mod_lshift_quick(n2, n2, 2, group->p))
869 goto err;
870 /* n2 = 4 * X_a * Y_a^2 */
871
872 /* X_r */
873 if (!BN_mod_lshift1_quick(n0, n2, group->p))
874 goto err;
875 if (!ec_field_sqr(group, r->X, n1, ctx))
876 goto err;
877 if (!BN_mod_sub_quick(r->X, r->X, n0, group->p))
878 goto err;
879 /* X_r = n1^2 - 2 * n2 */
880
881 /* n3 */
882 if (!ec_field_sqr(group, n0, n3, ctx))
883 goto err;
884 if (!BN_mod_lshift_quick(n3, n0, 3, group->p))
885 goto err;
886 /* n3 = 8 * Y_a^4 */
887
888 /* Y_r */
889 if (!BN_mod_sub_quick(n0, n2, r->X, group->p))
890 goto err;
891 if (!ec_field_mul(group, n0, n1, n0, ctx))
892 goto err;
893 if (!BN_mod_sub_quick(r->Y, n0, n3, group->p))
894 goto err;
895 /* Y_r = n1 * (n2 - X_r) - n3 */
896
897 ret = 1;
898
899 err:
900 BN_CTX_end(ctx);
901
902 return ret;
903}
904
905static int
906ec_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
907{
908 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
909 /* point is its own inverse */
910 return 1;
911
912 return BN_usub(point->Y, group->p, point->Y);
913}
914
915/*
916 * Apply randomization of EC point Jacobian projective coordinates:
917 *
918 * (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z)
919 *
920 * where lambda is in the interval [1, p).
921 */
922static int
923ec_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
924{
925 BIGNUM *lambda = NULL;
926 BIGNUM *tmp = NULL;
927 int ret = 0;
928
929 BN_CTX_start(ctx);
930 if ((lambda = BN_CTX_get(ctx)) == NULL)
931 goto err;
932 if ((tmp = BN_CTX_get(ctx)) == NULL)
933 goto err;
934
935 /* Generate lambda in [1, p). */
936 if (!bn_rand_interval(lambda, 1, group->p))
937 goto err;
938
939 if (group->meth->field_encode != NULL &&
940 !group->meth->field_encode(group, lambda, lambda, ctx))
941 goto err;
942
943 /* Z = lambda * Z */
944 if (!ec_field_mul(group, p->Z, lambda, p->Z, ctx))
945 goto err;
946
947 /* tmp = lambda^2 */
948 if (!ec_field_sqr(group, tmp, lambda, ctx))
949 goto err;
950
951 /* X = lambda^2 * X */
952 if (!ec_field_mul(group, p->X, tmp, p->X, ctx))
953 goto err;
954
955 /* tmp = lambda^3 */
956 if (!ec_field_mul(group, tmp, tmp, lambda, ctx))
957 goto err;
958
959 /* Y = lambda^3 * Y */
960 if (!ec_field_mul(group, p->Y, tmp, p->Y, ctx))
961 goto err;
962
963 /* Disable optimized arithmetics after replacing Z by lambda * Z. */
964 p->Z_is_one = 0;
965
966 ret = 1;
967
968 err:
969 BN_CTX_end(ctx);
970 return ret;
971}
972
973#define EC_POINT_BN_set_flags(P, flags) do { \
974 BN_set_flags((P)->X, (flags)); \
975 BN_set_flags((P)->Y, (flags)); \
976 BN_set_flags((P)->Z, (flags)); \
977} while(0)
978
979#define EC_POINT_CSWAP(c, a, b, w, t) do { \
980 if (!BN_swap_ct(c, (a)->X, (b)->X, w) || \
981 !BN_swap_ct(c, (a)->Y, (b)->Y, w) || \
982 !BN_swap_ct(c, (a)->Z, (b)->Z, w)) \
983 goto err; \
984 t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \
985 (a)->Z_is_one ^= (t); \
986 (b)->Z_is_one ^= (t); \
987} while(0)
988
989/*
990 * This function computes (in constant time) a point multiplication over the
991 * EC group.
992 *
993 * At a high level, it is Montgomery ladder with conditional swaps.
994 *
995 * It performs either a fixed point multiplication
996 * (scalar * generator)
997 * when point is NULL, or a variable point multiplication
998 * (scalar * point)
999 * when point is not NULL.
1000 *
1001 * scalar should be in the range [0,n) otherwise all constant time bets are off.
1002 *
1003 * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
1004 * which of course are not constant time themselves.
1005 *
1006 * The product is stored in r.
1007 *
1008 * Returns 1 on success, 0 otherwise.
1009 */
1010static int
1011ec_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1012 const EC_POINT *point, BN_CTX *ctx)
1013{
1014 int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
1015 EC_POINT *s = NULL;
1016 BIGNUM *k = NULL;
1017 BIGNUM *lambda = NULL;
1018 BIGNUM *cardinality = NULL;
1019 int ret = 0;
1020
1021 BN_CTX_start(ctx);
1022
1023 if ((s = EC_POINT_dup(point, group)) == NULL)
1024 goto err;
1025
1026 EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME);
1027
1028 if ((cardinality = BN_CTX_get(ctx)) == NULL)
1029 goto err;
1030 if ((lambda = BN_CTX_get(ctx)) == NULL)
1031 goto err;
1032 if ((k = BN_CTX_get(ctx)) == NULL)
1033 goto err;
1034 if (!BN_mul(cardinality, group->order, group->cofactor, ctx))
1035 goto err;
1036
1037 /*
1038 * Group cardinalities are often on a word boundary.
1039 * So when we pad the scalar, some timing diff might
1040 * pop if it needs to be expanded due to carries.
1041 * So expand ahead of time.
1042 */
1043 cardinality_bits = BN_num_bits(cardinality);
1044 group_top = cardinality->top;
1045 if (!bn_wexpand(k, group_top + 2) ||
1046 !bn_wexpand(lambda, group_top + 2))
1047 goto err;
1048
1049 if (!bn_copy(k, scalar))
1050 goto err;
1051
1052 BN_set_flags(k, BN_FLG_CONSTTIME);
1053
1054 if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) {
1055 /*
1056 * This is an unusual input, and we don't guarantee
1057 * constant-timeness
1058 */
1059 if (!BN_nnmod(k, k, cardinality, ctx))
1060 goto err;
1061 }
1062
1063 if (!BN_add(lambda, k, cardinality))
1064 goto err;
1065 BN_set_flags(lambda, BN_FLG_CONSTTIME);
1066 if (!BN_add(k, lambda, cardinality))
1067 goto err;
1068 /*
1069 * lambda := scalar + cardinality
1070 * k := scalar + 2*cardinality
1071 */
1072 kbit = BN_is_bit_set(lambda, cardinality_bits);
1073 if (!BN_swap_ct(kbit, k, lambda, group_top + 2))
1074 goto err;
1075
1076 group_top = group->p->top;
1077 if (!bn_wexpand(s->X, group_top) ||
1078 !bn_wexpand(s->Y, group_top) ||
1079 !bn_wexpand(s->Z, group_top) ||
1080 !bn_wexpand(r->X, group_top) ||
1081 !bn_wexpand(r->Y, group_top) ||
1082 !bn_wexpand(r->Z, group_top))
1083 goto err;
1084
1085 /*
1086 * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD
1087 * implements it.
1088 */
1089 if (!ec_blind_coordinates(group, s, ctx))
1090 goto err;
1091
1092 /* top bit is a 1, in a fixed pos */
1093 if (!EC_POINT_copy(r, s))
1094 goto err;
1095
1096 EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
1097
1098 if (!EC_POINT_dbl(group, s, s, ctx))
1099 goto err;
1100
1101 pbit = 0;
1102
1103 /*
1104 * The ladder step, with branches, is
1105 *
1106 * k[i] == 0: S = add(R, S), R = dbl(R)
1107 * k[i] == 1: R = add(S, R), S = dbl(S)
1108 *
1109 * Swapping R, S conditionally on k[i] leaves you with state
1110 *
1111 * k[i] == 0: T, U = R, S
1112 * k[i] == 1: T, U = S, R
1113 *
1114 * Then perform the ECC ops.
1115 *
1116 * U = add(T, U)
1117 * T = dbl(T)
1118 *
1119 * Which leaves you with state
1120 *
1121 * k[i] == 0: U = add(R, S), T = dbl(R)
1122 * k[i] == 1: U = add(S, R), T = dbl(S)
1123 *
1124 * Swapping T, U conditionally on k[i] leaves you with state
1125 *
1126 * k[i] == 0: R, S = T, U
1127 * k[i] == 1: R, S = U, T
1128 *
1129 * Which leaves you with state
1130 *
1131 * k[i] == 0: S = add(R, S), R = dbl(R)
1132 * k[i] == 1: R = add(S, R), S = dbl(S)
1133 *
1134 * So we get the same logic, but instead of a branch it's a
1135 * conditional swap, followed by ECC ops, then another conditional swap.
1136 *
1137 * Optimization: The end of iteration i and start of i-1 looks like
1138 *
1139 * ...
1140 * CSWAP(k[i], R, S)
1141 * ECC
1142 * CSWAP(k[i], R, S)
1143 * (next iteration)
1144 * CSWAP(k[i-1], R, S)
1145 * ECC
1146 * CSWAP(k[i-1], R, S)
1147 * ...
1148 *
1149 * So instead of two contiguous swaps, you can merge the condition
1150 * bits and do a single swap.
1151 *
1152 * k[i] k[i-1] Outcome
1153 * 0 0 No Swap
1154 * 0 1 Swap
1155 * 1 0 Swap
1156 * 1 1 No Swap
1157 *
1158 * This is XOR. pbit tracks the previous bit of k.
1159 */
1160
1161 for (i = cardinality_bits - 1; i >= 0; i--) {
1162 kbit = BN_is_bit_set(k, i) ^ pbit;
1163 EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
1164 if (!EC_POINT_add(group, s, r, s, ctx))
1165 goto err;
1166 if (!EC_POINT_dbl(group, r, r, ctx))
1167 goto err;
1168 /*
1169 * pbit logic merges this cswap with that of the
1170 * next iteration
1171 */
1172 pbit ^= kbit;
1173 }
1174 /* one final cswap to move the right value into r */
1175 EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
1176
1177 ret = 1;
1178
1179 err:
1180 EC_POINT_free(s);
1181 BN_CTX_end(ctx);
1182
1183 return ret;
1184}
1185
1186#undef EC_POINT_BN_set_flags
1187#undef EC_POINT_CSWAP
1188
1189static int
1190ec_mul_single_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1191 const EC_POINT *point, BN_CTX *ctx)
1192{
1193 return ec_mul_ct(group, r, scalar, point, ctx);
1194}
1195
1196static int
1197ec_mul_double_nonct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar1,
1198 const EC_POINT *point1, const BIGNUM *scalar2, const EC_POINT *point2,
1199 BN_CTX *ctx)
1200{
1201 return ec_wnaf_mul(group, r, scalar1, point1, scalar2, point2, ctx);
1202}
1203
1204static int
1205ec_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1206 const BIGNUM *b, BN_CTX *ctx)
1207{
1208 return BN_mod_mul(r, a, b, group->p, ctx);
1209}
1210
1211static int
1212ec_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1213{
1214 return BN_mod_sqr(r, a, group->p, ctx);
1215}
1216
1217static int
1218ec_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
1219 const BIGNUM *b, BN_CTX *ctx)
1220{
1221 BN_MONT_CTX_free(group->mont_ctx);
1222 if ((group->mont_ctx = BN_MONT_CTX_create(p, ctx)) == NULL)
1223 goto err;
1224
1225 if (!ec_group_set_curve(group, p, a, b, ctx))
1226 goto err;
1227
1228 return 1;
1229
1230 err:
1231 BN_MONT_CTX_free(group->mont_ctx);
1232 group->mont_ctx = NULL;
1233
1234 return 0;
1235}
1236
1237static int
1238ec_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1239 const BIGNUM *b, BN_CTX *ctx)
1240{
1241 if (group->mont_ctx == NULL) {
1242 ECerror(EC_R_NOT_INITIALIZED);
1243 return 0;
1244 }
1245 return BN_mod_mul_montgomery(r, a, b, group->mont_ctx, ctx);
1246}
1247
1248static int
1249ec_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1250 BN_CTX *ctx)
1251{
1252 if (group->mont_ctx == NULL) {
1253 ECerror(EC_R_NOT_INITIALIZED);
1254 return 0;
1255 }
1256 return BN_mod_mul_montgomery(r, a, a, group->mont_ctx, ctx);
1257}
1258
1259static int
1260ec_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1261 BN_CTX *ctx)
1262{
1263 if (group->mont_ctx == NULL) {
1264 ECerror(EC_R_NOT_INITIALIZED);
1265 return 0;
1266 }
1267 return BN_to_montgomery(r, a, group->mont_ctx, ctx);
1268}
1269
1270static int
1271ec_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1272 BN_CTX *ctx)
1273{
1274 if (group->mont_ctx == NULL) {
1275 ECerror(EC_R_NOT_INITIALIZED);
1276 return 0;
1277 }
1278 return BN_from_montgomery(r, a, group->mont_ctx, ctx);
1279}
1280
1281static const EC_METHOD ec_GFp_simple_method = {
1282 .group_set_curve = ec_group_set_curve,
1283 .group_get_curve = ec_group_get_curve,
1284 .point_is_on_curve = ec_point_is_on_curve,
1285 .point_cmp = ec_point_cmp,
1286 .point_set_affine_coordinates = ec_point_set_affine_coordinates,
1287 .point_get_affine_coordinates = ec_point_get_affine_coordinates,
1288 .points_make_affine = ec_points_make_affine,
1289 .add = ec_add,
1290 .dbl = ec_dbl,
1291 .invert = ec_invert,
1292 .mul_single_ct = ec_mul_single_ct,
1293 .mul_double_nonct = ec_mul_double_nonct,
1294 .field_mul = ec_simple_field_mul,
1295 .field_sqr = ec_simple_field_sqr,
1296};
1297
1298const EC_METHOD *
1299EC_GFp_simple_method(void)
1300{
1301 return &ec_GFp_simple_method;
1302}
1303
1304static const EC_METHOD ec_GFp_mont_method = {
1305 .group_set_curve = ec_mont_group_set_curve,
1306 .group_get_curve = ec_group_get_curve,
1307 .point_is_on_curve = ec_point_is_on_curve,
1308 .point_cmp = ec_point_cmp,
1309 .point_set_affine_coordinates = ec_point_set_affine_coordinates,
1310 .point_get_affine_coordinates = ec_point_get_affine_coordinates,
1311 .points_make_affine = ec_points_make_affine,
1312 .add = ec_add,
1313 .dbl = ec_dbl,
1314 .invert = ec_invert,
1315 .mul_single_ct = ec_mul_single_ct,
1316 .mul_double_nonct = ec_mul_double_nonct,
1317 .field_mul = ec_mont_field_mul,
1318 .field_sqr = ec_mont_field_sqr,
1319 .field_encode = ec_mont_field_encode,
1320 .field_decode = ec_mont_field_decode,
1321};
1322
1323const EC_METHOD *
1324EC_GFp_mont_method(void)
1325{
1326 return &ec_GFp_mont_method;
1327}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-06 15:17:15 +0000