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