1 /*
2 * Copyright 2002-2021 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4 *
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 */
10
11 /*
12 * ECDSA low-level APIs are deprecated for public use, but still ok for
13 * internal use.
14 */
15 #include "internal/deprecated.h"
16
17 #include <openssl/err.h>
18
19 #include "crypto/bn.h"
20 #include "ec_local.h"
21
22 #ifndef OPENSSL_NO_EC2M
23
24 /*
25 * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
26 * are handled by EC_GROUP_new.
27 */
ossl_ec_GF2m_simple_group_init(EC_GROUP * group)28 int ossl_ec_GF2m_simple_group_init(EC_GROUP *group)
29 {
30 group->field = BN_new();
31 group->a = BN_new();
32 group->b = BN_new();
33
34 if (group->field == NULL || group->a == NULL || group->b == NULL) {
35 BN_free(group->field);
36 BN_free(group->a);
37 BN_free(group->b);
38 return 0;
39 }
40 return 1;
41 }
42
43 /*
44 * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
45 * handled by EC_GROUP_free.
46 */
ossl_ec_GF2m_simple_group_finish(EC_GROUP * group)47 void ossl_ec_GF2m_simple_group_finish(EC_GROUP *group)
48 {
49 BN_free(group->field);
50 BN_free(group->a);
51 BN_free(group->b);
52 }
53
54 /*
55 * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
56 * members are handled by EC_GROUP_clear_free.
57 */
ossl_ec_GF2m_simple_group_clear_finish(EC_GROUP * group)58 void ossl_ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
59 {
60 BN_clear_free(group->field);
61 BN_clear_free(group->a);
62 BN_clear_free(group->b);
63 group->poly[0] = 0;
64 group->poly[1] = 0;
65 group->poly[2] = 0;
66 group->poly[3] = 0;
67 group->poly[4] = 0;
68 group->poly[5] = -1;
69 }
70
71 /*
72 * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
73 * handled by EC_GROUP_copy.
74 */
ossl_ec_GF2m_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)75 int ossl_ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
76 {
77 if (!BN_copy(dest->field, src->field))
78 return 0;
79 if (!BN_copy(dest->a, src->a))
80 return 0;
81 if (!BN_copy(dest->b, src->b))
82 return 0;
83 dest->poly[0] = src->poly[0];
84 dest->poly[1] = src->poly[1];
85 dest->poly[2] = src->poly[2];
86 dest->poly[3] = src->poly[3];
87 dest->poly[4] = src->poly[4];
88 dest->poly[5] = src->poly[5];
89 if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
90 return 0;
91 if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
92 return 0;
93 bn_set_all_zero(dest->a);
94 bn_set_all_zero(dest->b);
95 return 1;
96 }
97
98 /* Set the curve parameters of an EC_GROUP structure. */
ossl_ec_GF2m_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)99 int ossl_ec_GF2m_simple_group_set_curve(EC_GROUP *group,
100 const BIGNUM *p, const BIGNUM *a,
101 const BIGNUM *b, BN_CTX *ctx)
102 {
103 int ret = 0, i;
104
105 /* group->field */
106 if (!BN_copy(group->field, p))
107 goto err;
108 i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
109 if ((i != 5) && (i != 3)) {
110 ERR_raise(ERR_LIB_EC, EC_R_UNSUPPORTED_FIELD);
111 goto err;
112 }
113
114 /* group->a */
115 if (!BN_GF2m_mod_arr(group->a, a, group->poly))
116 goto err;
117 if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
118 == NULL)
119 goto err;
120 bn_set_all_zero(group->a);
121
122 /* group->b */
123 if (!BN_GF2m_mod_arr(group->b, b, group->poly))
124 goto err;
125 if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
126 == NULL)
127 goto err;
128 bn_set_all_zero(group->b);
129
130 ret = 1;
131 err:
132 return ret;
133 }
134
135 /*
136 * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
137 * then there values will not be set but the method will return with success.
138 */
ossl_ec_GF2m_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)139 int ossl_ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
140 BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
141 {
142 int ret = 0;
143
144 if (p != NULL) {
145 if (!BN_copy(p, group->field))
146 return 0;
147 }
148
149 if (a != NULL) {
150 if (!BN_copy(a, group->a))
151 goto err;
152 }
153
154 if (b != NULL) {
155 if (!BN_copy(b, group->b))
156 goto err;
157 }
158
159 ret = 1;
160
161 err:
162 return ret;
163 }
164
165 /*
166 * Gets the degree of the field. For a curve over GF(2^m) this is the value
167 * m.
168 */
ossl_ec_GF2m_simple_group_get_degree(const EC_GROUP * group)169 int ossl_ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
170 {
171 return BN_num_bits(group->field) - 1;
172 }
173
174 /*
175 * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
176 * elliptic curve <=> b != 0 (mod p)
177 */
ossl_ec_GF2m_simple_group_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)178 int ossl_ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
179 BN_CTX *ctx)
180 {
181 int ret = 0;
182 BIGNUM *b;
183 #ifndef FIPS_MODULE
184 BN_CTX *new_ctx = NULL;
185
186 if (ctx == NULL) {
187 ctx = new_ctx = BN_CTX_new();
188 if (ctx == NULL) {
189 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
190 goto err;
191 }
192 }
193 #endif
194 BN_CTX_start(ctx);
195 b = BN_CTX_get(ctx);
196 if (b == NULL)
197 goto err;
198
199 if (!BN_GF2m_mod_arr(b, group->b, group->poly))
200 goto err;
201
202 /*
203 * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
204 * curve <=> b != 0 (mod p)
205 */
206 if (BN_is_zero(b))
207 goto err;
208
209 ret = 1;
210
211 err:
212 BN_CTX_end(ctx);
213 #ifndef FIPS_MODULE
214 BN_CTX_free(new_ctx);
215 #endif
216 return ret;
217 }
218
219 /* Initializes an EC_POINT. */
ossl_ec_GF2m_simple_point_init(EC_POINT * point)220 int ossl_ec_GF2m_simple_point_init(EC_POINT *point)
221 {
222 point->X = BN_new();
223 point->Y = BN_new();
224 point->Z = BN_new();
225
226 if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
227 BN_free(point->X);
228 BN_free(point->Y);
229 BN_free(point->Z);
230 return 0;
231 }
232 return 1;
233 }
234
235 /* Frees an EC_POINT. */
ossl_ec_GF2m_simple_point_finish(EC_POINT * point)236 void ossl_ec_GF2m_simple_point_finish(EC_POINT *point)
237 {
238 BN_free(point->X);
239 BN_free(point->Y);
240 BN_free(point->Z);
241 }
242
243 /* Clears and frees an EC_POINT. */
ossl_ec_GF2m_simple_point_clear_finish(EC_POINT * point)244 void ossl_ec_GF2m_simple_point_clear_finish(EC_POINT *point)
245 {
246 BN_clear_free(point->X);
247 BN_clear_free(point->Y);
248 BN_clear_free(point->Z);
249 point->Z_is_one = 0;
250 }
251
252 /*
253 * Copy the contents of one EC_POINT into another. Assumes dest is
254 * initialized.
255 */
ossl_ec_GF2m_simple_point_copy(EC_POINT * dest,const EC_POINT * src)256 int ossl_ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
257 {
258 if (!BN_copy(dest->X, src->X))
259 return 0;
260 if (!BN_copy(dest->Y, src->Y))
261 return 0;
262 if (!BN_copy(dest->Z, src->Z))
263 return 0;
264 dest->Z_is_one = src->Z_is_one;
265 dest->curve_name = src->curve_name;
266
267 return 1;
268 }
269
270 /*
271 * Set an EC_POINT to the point at infinity. A point at infinity is
272 * represented by having Z=0.
273 */
ossl_ec_GF2m_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)274 int ossl_ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
275 EC_POINT *point)
276 {
277 point->Z_is_one = 0;
278 BN_zero(point->Z);
279 return 1;
280 }
281
282 /*
283 * Set the coordinates of an EC_POINT using affine coordinates. Note that
284 * the simple implementation only uses affine coordinates.
285 */
ossl_ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)286 int ossl_ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
287 EC_POINT *point,
288 const BIGNUM *x,
289 const BIGNUM *y,
290 BN_CTX *ctx)
291 {
292 int ret = 0;
293 if (x == NULL || y == NULL) {
294 ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER);
295 return 0;
296 }
297
298 if (!BN_copy(point->X, x))
299 goto err;
300 BN_set_negative(point->X, 0);
301 if (!BN_copy(point->Y, y))
302 goto err;
303 BN_set_negative(point->Y, 0);
304 if (!BN_copy(point->Z, BN_value_one()))
305 goto err;
306 BN_set_negative(point->Z, 0);
307 point->Z_is_one = 1;
308 ret = 1;
309
310 err:
311 return ret;
312 }
313
314 /*
315 * Gets the affine coordinates of an EC_POINT. Note that the simple
316 * implementation only uses affine coordinates.
317 */
ossl_ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)318 int ossl_ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
319 const EC_POINT *point,
320 BIGNUM *x, BIGNUM *y,
321 BN_CTX *ctx)
322 {
323 int ret = 0;
324
325 if (EC_POINT_is_at_infinity(group, point)) {
326 ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
327 return 0;
328 }
329
330 if (BN_cmp(point->Z, BN_value_one())) {
331 ERR_raise(ERR_LIB_EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
332 return 0;
333 }
334 if (x != NULL) {
335 if (!BN_copy(x, point->X))
336 goto err;
337 BN_set_negative(x, 0);
338 }
339 if (y != NULL) {
340 if (!BN_copy(y, point->Y))
341 goto err;
342 BN_set_negative(y, 0);
343 }
344 ret = 1;
345
346 err:
347 return ret;
348 }
349
350 /*
351 * Computes a + b and stores the result in r. r could be a or b, a could be
352 * b. Uses algorithm A.10.2 of IEEE P1363.
353 */
ossl_ec_GF2m_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)354 int ossl_ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r,
355 const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
356 {
357 BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
358 int ret = 0;
359 #ifndef FIPS_MODULE
360 BN_CTX *new_ctx = NULL;
361 #endif
362
363 if (EC_POINT_is_at_infinity(group, a)) {
364 if (!EC_POINT_copy(r, b))
365 return 0;
366 return 1;
367 }
368
369 if (EC_POINT_is_at_infinity(group, b)) {
370 if (!EC_POINT_copy(r, a))
371 return 0;
372 return 1;
373 }
374
375 #ifndef FIPS_MODULE
376 if (ctx == NULL) {
377 ctx = new_ctx = BN_CTX_new();
378 if (ctx == NULL)
379 return 0;
380 }
381 #endif
382
383 BN_CTX_start(ctx);
384 x0 = BN_CTX_get(ctx);
385 y0 = BN_CTX_get(ctx);
386 x1 = BN_CTX_get(ctx);
387 y1 = BN_CTX_get(ctx);
388 x2 = BN_CTX_get(ctx);
389 y2 = BN_CTX_get(ctx);
390 s = BN_CTX_get(ctx);
391 t = BN_CTX_get(ctx);
392 if (t == NULL)
393 goto err;
394
395 if (a->Z_is_one) {
396 if (!BN_copy(x0, a->X))
397 goto err;
398 if (!BN_copy(y0, a->Y))
399 goto err;
400 } else {
401 if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
402 goto err;
403 }
404 if (b->Z_is_one) {
405 if (!BN_copy(x1, b->X))
406 goto err;
407 if (!BN_copy(y1, b->Y))
408 goto err;
409 } else {
410 if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
411 goto err;
412 }
413
414 if (BN_GF2m_cmp(x0, x1)) {
415 if (!BN_GF2m_add(t, x0, x1))
416 goto err;
417 if (!BN_GF2m_add(s, y0, y1))
418 goto err;
419 if (!group->meth->field_div(group, s, s, t, ctx))
420 goto err;
421 if (!group->meth->field_sqr(group, x2, s, ctx))
422 goto err;
423 if (!BN_GF2m_add(x2, x2, group->a))
424 goto err;
425 if (!BN_GF2m_add(x2, x2, s))
426 goto err;
427 if (!BN_GF2m_add(x2, x2, t))
428 goto err;
429 } else {
430 if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
431 if (!EC_POINT_set_to_infinity(group, r))
432 goto err;
433 ret = 1;
434 goto err;
435 }
436 if (!group->meth->field_div(group, s, y1, x1, ctx))
437 goto err;
438 if (!BN_GF2m_add(s, s, x1))
439 goto err;
440
441 if (!group->meth->field_sqr(group, x2, s, ctx))
442 goto err;
443 if (!BN_GF2m_add(x2, x2, s))
444 goto err;
445 if (!BN_GF2m_add(x2, x2, group->a))
446 goto err;
447 }
448
449 if (!BN_GF2m_add(y2, x1, x2))
450 goto err;
451 if (!group->meth->field_mul(group, y2, y2, s, ctx))
452 goto err;
453 if (!BN_GF2m_add(y2, y2, x2))
454 goto err;
455 if (!BN_GF2m_add(y2, y2, y1))
456 goto err;
457
458 if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
459 goto err;
460
461 ret = 1;
462
463 err:
464 BN_CTX_end(ctx);
465 #ifndef FIPS_MODULE
466 BN_CTX_free(new_ctx);
467 #endif
468 return ret;
469 }
470
471 /*
472 * Computes 2 * a and stores the result in r. r could be a. Uses algorithm
473 * A.10.2 of IEEE P1363.
474 */
ossl_ec_GF2m_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)475 int ossl_ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r,
476 const EC_POINT *a, BN_CTX *ctx)
477 {
478 return ossl_ec_GF2m_simple_add(group, r, a, a, ctx);
479 }
480
ossl_ec_GF2m_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)481 int ossl_ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point,
482 BN_CTX *ctx)
483 {
484 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
485 /* point is its own inverse */
486 return 1;
487
488 if (group->meth->make_affine == NULL
489 || !group->meth->make_affine(group, point, ctx))
490 return 0;
491 return BN_GF2m_add(point->Y, point->X, point->Y);
492 }
493
494 /* Indicates whether the given point is the point at infinity. */
ossl_ec_GF2m_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)495 int ossl_ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
496 const EC_POINT *point)
497 {
498 return BN_is_zero(point->Z);
499 }
500
501 /*-
502 * Determines whether the given EC_POINT is an actual point on the curve defined
503 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
504 * y^2 + x*y = x^3 + a*x^2 + b.
505 */
ossl_ec_GF2m_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)506 int ossl_ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
507 BN_CTX *ctx)
508 {
509 int ret = -1;
510 BIGNUM *lh, *y2;
511 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *,
512 const BIGNUM *, BN_CTX *);
513 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
514 #ifndef FIPS_MODULE
515 BN_CTX *new_ctx = NULL;
516 #endif
517
518 if (EC_POINT_is_at_infinity(group, point))
519 return 1;
520
521 field_mul = group->meth->field_mul;
522 field_sqr = group->meth->field_sqr;
523
524 /* only support affine coordinates */
525 if (!point->Z_is_one)
526 return -1;
527
528 #ifndef FIPS_MODULE
529 if (ctx == NULL) {
530 ctx = new_ctx = BN_CTX_new();
531 if (ctx == NULL)
532 return -1;
533 }
534 #endif
535
536 BN_CTX_start(ctx);
537 y2 = BN_CTX_get(ctx);
538 lh = BN_CTX_get(ctx);
539 if (lh == NULL)
540 goto err;
541
542 /*-
543 * We have a curve defined by a Weierstrass equation
544 * y^2 + x*y = x^3 + a*x^2 + b.
545 * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
546 * <=> ((x + a) * x + y) * x + b + y^2 = 0
547 */
548 if (!BN_GF2m_add(lh, point->X, group->a))
549 goto err;
550 if (!field_mul(group, lh, lh, point->X, ctx))
551 goto err;
552 if (!BN_GF2m_add(lh, lh, point->Y))
553 goto err;
554 if (!field_mul(group, lh, lh, point->X, ctx))
555 goto err;
556 if (!BN_GF2m_add(lh, lh, group->b))
557 goto err;
558 if (!field_sqr(group, y2, point->Y, ctx))
559 goto err;
560 if (!BN_GF2m_add(lh, lh, y2))
561 goto err;
562 ret = BN_is_zero(lh);
563
564 err:
565 BN_CTX_end(ctx);
566 #ifndef FIPS_MODULE
567 BN_CTX_free(new_ctx);
568 #endif
569 return ret;
570 }
571
572 /*-
573 * Indicates whether two points are equal.
574 * Return values:
575 * -1 error
576 * 0 equal (in affine coordinates)
577 * 1 not equal
578 */
ossl_ec_GF2m_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)579 int ossl_ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
580 const EC_POINT *b, BN_CTX *ctx)
581 {
582 BIGNUM *aX, *aY, *bX, *bY;
583 int ret = -1;
584 #ifndef FIPS_MODULE
585 BN_CTX *new_ctx = NULL;
586 #endif
587
588 if (EC_POINT_is_at_infinity(group, a)) {
589 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
590 }
591
592 if (EC_POINT_is_at_infinity(group, b))
593 return 1;
594
595 if (a->Z_is_one && b->Z_is_one) {
596 return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
597 }
598
599 #ifndef FIPS_MODULE
600 if (ctx == NULL) {
601 ctx = new_ctx = BN_CTX_new();
602 if (ctx == NULL)
603 return -1;
604 }
605 #endif
606
607 BN_CTX_start(ctx);
608 aX = BN_CTX_get(ctx);
609 aY = BN_CTX_get(ctx);
610 bX = BN_CTX_get(ctx);
611 bY = BN_CTX_get(ctx);
612 if (bY == NULL)
613 goto err;
614
615 if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
616 goto err;
617 if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
618 goto err;
619 ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
620
621 err:
622 BN_CTX_end(ctx);
623 #ifndef FIPS_MODULE
624 BN_CTX_free(new_ctx);
625 #endif
626 return ret;
627 }
628
629 /* Forces the given EC_POINT to internally use affine coordinates. */
ossl_ec_GF2m_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)630 int ossl_ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
631 BN_CTX *ctx)
632 {
633 BIGNUM *x, *y;
634 int ret = 0;
635 #ifndef FIPS_MODULE
636 BN_CTX *new_ctx = NULL;
637 #endif
638
639 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
640 return 1;
641
642 #ifndef FIPS_MODULE
643 if (ctx == NULL) {
644 ctx = new_ctx = BN_CTX_new();
645 if (ctx == NULL)
646 return 0;
647 }
648 #endif
649
650 BN_CTX_start(ctx);
651 x = BN_CTX_get(ctx);
652 y = BN_CTX_get(ctx);
653 if (y == NULL)
654 goto err;
655
656 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
657 goto err;
658 if (!BN_copy(point->X, x))
659 goto err;
660 if (!BN_copy(point->Y, y))
661 goto err;
662 if (!BN_one(point->Z))
663 goto err;
664 point->Z_is_one = 1;
665
666 ret = 1;
667
668 err:
669 BN_CTX_end(ctx);
670 #ifndef FIPS_MODULE
671 BN_CTX_free(new_ctx);
672 #endif
673 return ret;
674 }
675
676 /*
677 * Forces each of the EC_POINTs in the given array to use affine coordinates.
678 */
ossl_ec_GF2m_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)679 int ossl_ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
680 EC_POINT *points[], BN_CTX *ctx)
681 {
682 size_t i;
683
684 for (i = 0; i < num; i++) {
685 if (!group->meth->make_affine(group, points[i], ctx))
686 return 0;
687 }
688
689 return 1;
690 }
691
692 /* Wrapper to simple binary polynomial field multiplication implementation. */
ossl_ec_GF2m_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)693 int ossl_ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
694 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
695 {
696 return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
697 }
698
699 /* Wrapper to simple binary polynomial field squaring implementation. */
ossl_ec_GF2m_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)700 int ossl_ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
701 const BIGNUM *a, BN_CTX *ctx)
702 {
703 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
704 }
705
706 /* Wrapper to simple binary polynomial field division implementation. */
ossl_ec_GF2m_simple_field_div(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)707 int ossl_ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
708 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
709 {
710 return BN_GF2m_mod_div(r, a, b, group->field, ctx);
711 }
712
713 /*-
714 * Lopez-Dahab ladder, pre step.
715 * See e.g. "Guide to ECC" Alg 3.40.
716 * Modified to blind s and r independently.
717 * s:= p, r := 2p
718 */
ec_GF2m_simple_ladder_pre(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)719 static int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
720 EC_POINT *r, EC_POINT *s,
721 EC_POINT *p, BN_CTX *ctx)
722 {
723 /* if p is not affine, something is wrong */
724 if (p->Z_is_one == 0)
725 return 0;
726
727 /* s blinding: make sure lambda (s->Z here) is not zero */
728 do {
729 if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
730 BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx)) {
731 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
732 return 0;
733 }
734 } while (BN_is_zero(s->Z));
735
736 /* if field_encode defined convert between representations */
737 if ((group->meth->field_encode != NULL
738 && !group->meth->field_encode(group, s->Z, s->Z, ctx))
739 || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
740 return 0;
741
742 /* r blinding: make sure lambda (r->Y here for storage) is not zero */
743 do {
744 if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
745 BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx)) {
746 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
747 return 0;
748 }
749 } while (BN_is_zero(r->Y));
750
751 if ((group->meth->field_encode != NULL
752 && !group->meth->field_encode(group, r->Y, r->Y, ctx))
753 || !group->meth->field_sqr(group, r->Z, p->X, ctx)
754 || !group->meth->field_sqr(group, r->X, r->Z, ctx)
755 || !BN_GF2m_add(r->X, r->X, group->b)
756 || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
757 || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
758 return 0;
759
760 s->Z_is_one = 0;
761 r->Z_is_one = 0;
762
763 return 1;
764 }
765
766 /*-
767 * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
768 * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
769 * s := r + s, r := 2r
770 */
ec_GF2m_simple_ladder_step(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)771 static int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
772 EC_POINT *r, EC_POINT *s,
773 EC_POINT *p, BN_CTX *ctx)
774 {
775 if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
776 || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
777 || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
778 || !group->meth->field_sqr(group, r->Z, r->X, ctx)
779 || !BN_GF2m_add(s->Z, r->Y, s->X)
780 || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
781 || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
782 || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
783 || !BN_GF2m_add(s->X, s->X, r->Y)
784 || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
785 || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
786 || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
787 || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
788 || !BN_GF2m_add(r->X, r->Y, s->Y))
789 return 0;
790
791 return 1;
792 }
793
794 /*-
795 * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
796 * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
797 * without Precomputation" (Lopez and Dahab, CHES 1999),
798 * Appendix Alg Mxy.
799 */
ec_GF2m_simple_ladder_post(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)800 static int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
801 EC_POINT *r, EC_POINT *s,
802 EC_POINT *p, BN_CTX *ctx)
803 {
804 int ret = 0;
805 BIGNUM *t0, *t1, *t2 = NULL;
806
807 if (BN_is_zero(r->Z))
808 return EC_POINT_set_to_infinity(group, r);
809
810 if (BN_is_zero(s->Z)) {
811 if (!EC_POINT_copy(r, p)
812 || !EC_POINT_invert(group, r, ctx)) {
813 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
814 return 0;
815 }
816 return 1;
817 }
818
819 BN_CTX_start(ctx);
820 t0 = BN_CTX_get(ctx);
821 t1 = BN_CTX_get(ctx);
822 t2 = BN_CTX_get(ctx);
823 if (t2 == NULL) {
824 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
825 goto err;
826 }
827
828 if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
829 || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
830 || !BN_GF2m_add(t1, r->X, t1)
831 || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
832 || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
833 || !BN_GF2m_add(t2, t2, s->X)
834 || !group->meth->field_mul(group, t1, t1, t2, ctx)
835 || !group->meth->field_sqr(group, t2, p->X, ctx)
836 || !BN_GF2m_add(t2, p->Y, t2)
837 || !group->meth->field_mul(group, t2, t2, t0, ctx)
838 || !BN_GF2m_add(t1, t2, t1)
839 || !group->meth->field_mul(group, t2, p->X, t0, ctx)
840 || !group->meth->field_inv(group, t2, t2, ctx)
841 || !group->meth->field_mul(group, t1, t1, t2, ctx)
842 || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
843 || !BN_GF2m_add(t2, p->X, r->X)
844 || !group->meth->field_mul(group, t2, t2, t1, ctx)
845 || !BN_GF2m_add(r->Y, p->Y, t2)
846 || !BN_one(r->Z))
847 goto err;
848
849 r->Z_is_one = 1;
850
851 /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
852 BN_set_negative(r->X, 0);
853 BN_set_negative(r->Y, 0);
854
855 ret = 1;
856
857 err:
858 BN_CTX_end(ctx);
859 return ret;
860 }
861
ec_GF2m_simple_points_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,size_t num,const EC_POINT * points[],const BIGNUM * scalars[],BN_CTX * ctx)862 static int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
863 const BIGNUM *scalar, size_t num,
864 const EC_POINT *points[],
865 const BIGNUM *scalars[],
866 BN_CTX *ctx)
867 {
868 int ret = 0;
869 EC_POINT *t = NULL;
870
871 /*-
872 * We limit use of the ladder only to the following cases:
873 * - r := scalar * G
874 * Fixed point mul: scalar != NULL && num == 0;
875 * - r := scalars[0] * points[0]
876 * Variable point mul: scalar == NULL && num == 1;
877 * - r := scalar * G + scalars[0] * points[0]
878 * used, e.g., in ECDSA verification: scalar != NULL && num == 1
879 *
880 * In any other case (num > 1) we use the default wNAF implementation.
881 *
882 * We also let the default implementation handle degenerate cases like group
883 * order or cofactor set to 0.
884 */
885 if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
886 return ossl_ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
887
888 if (scalar != NULL && num == 0)
889 /* Fixed point multiplication */
890 return ossl_ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
891
892 if (scalar == NULL && num == 1)
893 /* Variable point multiplication */
894 return ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
895
896 /*-
897 * Double point multiplication:
898 * r := scalar * G + scalars[0] * points[0]
899 */
900
901 if ((t = EC_POINT_new(group)) == NULL) {
902 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
903 return 0;
904 }
905
906 if (!ossl_ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
907 || !ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
908 || !EC_POINT_add(group, r, t, r, ctx))
909 goto err;
910
911 ret = 1;
912
913 err:
914 EC_POINT_free(t);
915 return ret;
916 }
917
918 /*-
919 * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
920 * If a is zero (or equivalent), you'll get an EC_R_CANNOT_INVERT error.
921 * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
922 */
ec_GF2m_simple_field_inv(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)923 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
924 const BIGNUM *a, BN_CTX *ctx)
925 {
926 int ret;
927
928 if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
929 ERR_raise(ERR_LIB_EC, EC_R_CANNOT_INVERT);
930 return ret;
931 }
932
EC_GF2m_simple_method(void)933 const EC_METHOD *EC_GF2m_simple_method(void)
934 {
935 static const EC_METHOD ret = {
936 EC_FLAGS_DEFAULT_OCT,
937 NID_X9_62_characteristic_two_field,
938 ossl_ec_GF2m_simple_group_init,
939 ossl_ec_GF2m_simple_group_finish,
940 ossl_ec_GF2m_simple_group_clear_finish,
941 ossl_ec_GF2m_simple_group_copy,
942 ossl_ec_GF2m_simple_group_set_curve,
943 ossl_ec_GF2m_simple_group_get_curve,
944 ossl_ec_GF2m_simple_group_get_degree,
945 ossl_ec_group_simple_order_bits,
946 ossl_ec_GF2m_simple_group_check_discriminant,
947 ossl_ec_GF2m_simple_point_init,
948 ossl_ec_GF2m_simple_point_finish,
949 ossl_ec_GF2m_simple_point_clear_finish,
950 ossl_ec_GF2m_simple_point_copy,
951 ossl_ec_GF2m_simple_point_set_to_infinity,
952 ossl_ec_GF2m_simple_point_set_affine_coordinates,
953 ossl_ec_GF2m_simple_point_get_affine_coordinates,
954 0, /* point_set_compressed_coordinates */
955 0, /* point2oct */
956 0, /* oct2point */
957 ossl_ec_GF2m_simple_add,
958 ossl_ec_GF2m_simple_dbl,
959 ossl_ec_GF2m_simple_invert,
960 ossl_ec_GF2m_simple_is_at_infinity,
961 ossl_ec_GF2m_simple_is_on_curve,
962 ossl_ec_GF2m_simple_cmp,
963 ossl_ec_GF2m_simple_make_affine,
964 ossl_ec_GF2m_simple_points_make_affine,
965 ec_GF2m_simple_points_mul,
966 0, /* precompute_mult */
967 0, /* have_precompute_mult */
968 ossl_ec_GF2m_simple_field_mul,
969 ossl_ec_GF2m_simple_field_sqr,
970 ossl_ec_GF2m_simple_field_div,
971 ec_GF2m_simple_field_inv,
972 0, /* field_encode */
973 0, /* field_decode */
974 0, /* field_set_to_one */
975 ossl_ec_key_simple_priv2oct,
976 ossl_ec_key_simple_oct2priv,
977 0, /* set private */
978 ossl_ec_key_simple_generate_key,
979 ossl_ec_key_simple_check_key,
980 ossl_ec_key_simple_generate_public_key,
981 0, /* keycopy */
982 0, /* keyfinish */
983 ossl_ecdh_simple_compute_key,
984 ossl_ecdsa_simple_sign_setup,
985 ossl_ecdsa_simple_sign_sig,
986 ossl_ecdsa_simple_verify_sig,
987 0, /* field_inverse_mod_ord */
988 0, /* blind_coordinates */
989 ec_GF2m_simple_ladder_pre,
990 ec_GF2m_simple_ladder_step,
991 ec_GF2m_simple_ladder_post
992 };
993
994 return &ret;
995 }
996
997 #endif
998