xref: /openssl/crypto/ec/ec2_smpl.c (revision 1567a821)
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_BN_LIB);
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_BN_LIB);
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_EC_LIB);
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 an 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