1 /* $OpenBSD: ec2_smpl.c,v 1.23 2021/09/08 17:29:21 tb Exp $ */
2 /* ====================================================================
3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
4 *
5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
7 * to the OpenSSL project.
8 *
9 * The ECC Code is licensed pursuant to the OpenSSL open source
10 * license provided below.
11 *
12 * The software is originally written by Sheueling Chang Shantz and
13 * Douglas Stebila of Sun Microsystems Laboratories.
14 *
15 */
16 /* ====================================================================
17 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
21 * are met:
22 *
23 * 1. Redistributions of source code must retain the above copyright
24 * notice, this list of conditions and the following disclaimer.
25 *
26 * 2. Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in
28 * the documentation and/or other materials provided with the
29 * distribution.
30 *
31 * 3. All advertising materials mentioning features or use of this
32 * software must display the following acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
35 *
36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
37 * endorse or promote products derived from this software without
38 * prior written permission. For written permission, please contact
39 * openssl-core@openssl.org.
40 *
41 * 5. Products derived from this software may not be called "OpenSSL"
42 * nor may "OpenSSL" appear in their names without prior written
43 * permission of the OpenSSL Project.
44 *
45 * 6. Redistributions of any form whatsoever must retain the following
46 * acknowledgment:
47 * "This product includes software developed by the OpenSSL Project
48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
49 *
50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
61 * OF THE POSSIBILITY OF SUCH DAMAGE.
62 * ====================================================================
63 *
64 * This product includes cryptographic software written by Eric Young
65 * (eay@cryptsoft.com). This product includes software written by Tim
66 * Hudson (tjh@cryptsoft.com).
67 *
68 */
69
70 #include <openssl/opensslconf.h>
71
72 #include <openssl/err.h>
73
74 #include "ec_lcl.h"
75
76 #ifndef OPENSSL_NO_EC2M
77
78 const EC_METHOD *
EC_GF2m_simple_method(void)79 EC_GF2m_simple_method(void)
80 {
81 static const EC_METHOD ret = {
82 .flags = EC_FLAGS_DEFAULT_OCT,
83 .field_type = NID_X9_62_characteristic_two_field,
84 .group_init = ec_GF2m_simple_group_init,
85 .group_finish = ec_GF2m_simple_group_finish,
86 .group_clear_finish = ec_GF2m_simple_group_clear_finish,
87 .group_copy = ec_GF2m_simple_group_copy,
88 .group_set_curve = ec_GF2m_simple_group_set_curve,
89 .group_get_curve = ec_GF2m_simple_group_get_curve,
90 .group_get_degree = ec_GF2m_simple_group_get_degree,
91 .group_order_bits = ec_group_simple_order_bits,
92 .group_check_discriminant =
93 ec_GF2m_simple_group_check_discriminant,
94 .point_init = ec_GF2m_simple_point_init,
95 .point_finish = ec_GF2m_simple_point_finish,
96 .point_clear_finish = ec_GF2m_simple_point_clear_finish,
97 .point_copy = ec_GF2m_simple_point_copy,
98 .point_set_to_infinity = ec_GF2m_simple_point_set_to_infinity,
99 .point_set_affine_coordinates =
100 ec_GF2m_simple_point_set_affine_coordinates,
101 .point_get_affine_coordinates =
102 ec_GF2m_simple_point_get_affine_coordinates,
103 .add = ec_GF2m_simple_add,
104 .dbl = ec_GF2m_simple_dbl,
105 .invert = ec_GF2m_simple_invert,
106 .is_at_infinity = ec_GF2m_simple_is_at_infinity,
107 .is_on_curve = ec_GF2m_simple_is_on_curve,
108 .point_cmp = ec_GF2m_simple_cmp,
109 .make_affine = ec_GF2m_simple_make_affine,
110 .points_make_affine = ec_GF2m_simple_points_make_affine,
111 .mul_generator_ct = ec_GFp_simple_mul_generator_ct,
112 .mul_single_ct = ec_GFp_simple_mul_single_ct,
113 .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
114 .precompute_mult = ec_GF2m_precompute_mult,
115 .have_precompute_mult = ec_GF2m_have_precompute_mult,
116 .field_mul = ec_GF2m_simple_field_mul,
117 .field_sqr = ec_GF2m_simple_field_sqr,
118 .field_div = ec_GF2m_simple_field_div,
119 .blind_coordinates = NULL,
120 };
121
122 return &ret;
123 }
124
125
126 /* Initialize a GF(2^m)-based EC_GROUP structure.
127 * Note that all other members are handled by EC_GROUP_new.
128 */
129 int
ec_GF2m_simple_group_init(EC_GROUP * group)130 ec_GF2m_simple_group_init(EC_GROUP * group)
131 {
132 BN_init(&group->field);
133 BN_init(&group->a);
134 BN_init(&group->b);
135 return 1;
136 }
137
138
139 /* Free a GF(2^m)-based EC_GROUP structure.
140 * Note that all other members are handled by EC_GROUP_free.
141 */
142 void
ec_GF2m_simple_group_finish(EC_GROUP * group)143 ec_GF2m_simple_group_finish(EC_GROUP * group)
144 {
145 BN_free(&group->field);
146 BN_free(&group->a);
147 BN_free(&group->b);
148 }
149
150
151 /* Clear and free a GF(2^m)-based EC_GROUP structure.
152 * Note that all other members are handled by EC_GROUP_clear_free.
153 */
154 void
ec_GF2m_simple_group_clear_finish(EC_GROUP * group)155 ec_GF2m_simple_group_clear_finish(EC_GROUP * group)
156 {
157 BN_clear_free(&group->field);
158 BN_clear_free(&group->a);
159 BN_clear_free(&group->b);
160 group->poly[0] = 0;
161 group->poly[1] = 0;
162 group->poly[2] = 0;
163 group->poly[3] = 0;
164 group->poly[4] = 0;
165 group->poly[5] = -1;
166 }
167
168
169 /* Copy a GF(2^m)-based EC_GROUP structure.
170 * Note that all other members are handled by EC_GROUP_copy.
171 */
172 int
ec_GF2m_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)173 ec_GF2m_simple_group_copy(EC_GROUP * dest, const EC_GROUP * src)
174 {
175 int i;
176
177 if (!BN_copy(&dest->field, &src->field))
178 return 0;
179 if (!BN_copy(&dest->a, &src->a))
180 return 0;
181 if (!BN_copy(&dest->b, &src->b))
182 return 0;
183 dest->poly[0] = src->poly[0];
184 dest->poly[1] = src->poly[1];
185 dest->poly[2] = src->poly[2];
186 dest->poly[3] = src->poly[3];
187 dest->poly[4] = src->poly[4];
188 dest->poly[5] = src->poly[5];
189 if (bn_wexpand(&dest->a, (int) (dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
190 return 0;
191 if (bn_wexpand(&dest->b, (int) (dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
192 return 0;
193 for (i = dest->a.top; i < dest->a.dmax; i++)
194 dest->a.d[i] = 0;
195 for (i = dest->b.top; i < dest->b.dmax; i++)
196 dest->b.d[i] = 0;
197 return 1;
198 }
199
200
201 /* Set the curve parameters of an EC_GROUP structure. */
202 int
ec_GF2m_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)203 ec_GF2m_simple_group_set_curve(EC_GROUP * group,
204 const BIGNUM * p, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
205 {
206 int ret = 0, i;
207
208 /* group->field */
209 if (!BN_copy(&group->field, p))
210 goto err;
211 i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1;
212 if ((i != 5) && (i != 3)) {
213 ECerror(EC_R_UNSUPPORTED_FIELD);
214 goto err;
215 }
216 /* group->a */
217 if (!BN_GF2m_mod_arr(&group->a, a, group->poly))
218 goto err;
219 if (bn_wexpand(&group->a, (int) (group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
220 goto err;
221 for (i = group->a.top; i < group->a.dmax; i++)
222 group->a.d[i] = 0;
223
224 /* group->b */
225 if (!BN_GF2m_mod_arr(&group->b, b, group->poly))
226 goto err;
227 if (bn_wexpand(&group->b, (int) (group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL)
228 goto err;
229 for (i = group->b.top; i < group->b.dmax; i++)
230 group->b.d[i] = 0;
231
232 ret = 1;
233 err:
234 return ret;
235 }
236
237
238 /* Get the curve parameters of an EC_GROUP structure.
239 * If p, a, or b are NULL then there values will not be set but the method will return with success.
240 */
241 int
ec_GF2m_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)242 ec_GF2m_simple_group_get_curve(const EC_GROUP *group,
243 BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
244 {
245 int ret = 0;
246
247 if (p != NULL) {
248 if (!BN_copy(p, &group->field))
249 return 0;
250 }
251 if (a != NULL) {
252 if (!BN_copy(a, &group->a))
253 goto err;
254 }
255 if (b != NULL) {
256 if (!BN_copy(b, &group->b))
257 goto err;
258 }
259 ret = 1;
260
261 err:
262 return ret;
263 }
264
265
266 /* Gets the degree of the field. For a curve over GF(2^m) this is the value m. */
267 int
ec_GF2m_simple_group_get_degree(const EC_GROUP * group)268 ec_GF2m_simple_group_get_degree(const EC_GROUP * group)
269 {
270 return BN_num_bits(&group->field) - 1;
271 }
272
273
274 /* Checks the discriminant of the curve.
275 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
276 */
277 int
ec_GF2m_simple_group_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)278 ec_GF2m_simple_group_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
279 {
280 int ret = 0;
281 BIGNUM *b;
282 BN_CTX *new_ctx = NULL;
283
284 if (ctx == NULL) {
285 ctx = new_ctx = BN_CTX_new();
286 if (ctx == NULL) {
287 ECerror(ERR_R_MALLOC_FAILURE);
288 goto err;
289 }
290 }
291 BN_CTX_start(ctx);
292 if ((b = BN_CTX_get(ctx)) == NULL)
293 goto err;
294
295 if (!BN_GF2m_mod_arr(b, &group->b, group->poly))
296 goto err;
297
298 /*
299 * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
300 * curve <=> b != 0 (mod p)
301 */
302 if (BN_is_zero(b))
303 goto err;
304
305 ret = 1;
306
307 err:
308 if (ctx != NULL)
309 BN_CTX_end(ctx);
310 BN_CTX_free(new_ctx);
311 return ret;
312 }
313
314
315 /* Initializes an EC_POINT. */
316 int
ec_GF2m_simple_point_init(EC_POINT * point)317 ec_GF2m_simple_point_init(EC_POINT * point)
318 {
319 BN_init(&point->X);
320 BN_init(&point->Y);
321 BN_init(&point->Z);
322 return 1;
323 }
324
325
326 /* Frees an EC_POINT. */
327 void
ec_GF2m_simple_point_finish(EC_POINT * point)328 ec_GF2m_simple_point_finish(EC_POINT * point)
329 {
330 BN_free(&point->X);
331 BN_free(&point->Y);
332 BN_free(&point->Z);
333 }
334
335
336 /* Clears and frees an EC_POINT. */
337 void
ec_GF2m_simple_point_clear_finish(EC_POINT * point)338 ec_GF2m_simple_point_clear_finish(EC_POINT * point)
339 {
340 BN_clear_free(&point->X);
341 BN_clear_free(&point->Y);
342 BN_clear_free(&point->Z);
343 point->Z_is_one = 0;
344 }
345
346
347 /* Copy the contents of one EC_POINT into another. Assumes dest is initialized. */
348 int
ec_GF2m_simple_point_copy(EC_POINT * dest,const EC_POINT * src)349 ec_GF2m_simple_point_copy(EC_POINT * dest, const EC_POINT * src)
350 {
351 if (!BN_copy(&dest->X, &src->X))
352 return 0;
353 if (!BN_copy(&dest->Y, &src->Y))
354 return 0;
355 if (!BN_copy(&dest->Z, &src->Z))
356 return 0;
357 dest->Z_is_one = src->Z_is_one;
358
359 return 1;
360 }
361
362
363 /* Set an EC_POINT to the point at infinity.
364 * A point at infinity is represented by having Z=0.
365 */
366 int
ec_GF2m_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)367 ec_GF2m_simple_point_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
368 {
369 point->Z_is_one = 0;
370 BN_zero(&point->Z);
371 return 1;
372 }
373
374
375 /* Set the coordinates of an EC_POINT using affine coordinates.
376 * Note that the simple implementation only uses affine coordinates.
377 */
378 int
ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)379 ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP * group, EC_POINT * point,
380 const BIGNUM * x, const BIGNUM * y, BN_CTX * ctx)
381 {
382 int ret = 0;
383 if (x == NULL || y == NULL) {
384 ECerror(ERR_R_PASSED_NULL_PARAMETER);
385 return 0;
386 }
387 if (!BN_copy(&point->X, x))
388 goto err;
389 BN_set_negative(&point->X, 0);
390 if (!BN_copy(&point->Y, y))
391 goto err;
392 BN_set_negative(&point->Y, 0);
393 if (!BN_copy(&point->Z, BN_value_one()))
394 goto err;
395 BN_set_negative(&point->Z, 0);
396 point->Z_is_one = 1;
397 ret = 1;
398
399 err:
400 return ret;
401 }
402
403
404 /* Gets the affine coordinates of an EC_POINT.
405 * Note that the simple implementation only uses affine coordinates.
406 */
407 int
ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)408 ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
409 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
410 {
411 int ret = 0;
412
413 if (EC_POINT_is_at_infinity(group, point) > 0) {
414 ECerror(EC_R_POINT_AT_INFINITY);
415 return 0;
416 }
417 if (BN_cmp(&point->Z, BN_value_one())) {
418 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
419 return 0;
420 }
421 if (x != NULL) {
422 if (!BN_copy(x, &point->X))
423 goto err;
424 BN_set_negative(x, 0);
425 }
426 if (y != NULL) {
427 if (!BN_copy(y, &point->Y))
428 goto err;
429 BN_set_negative(y, 0);
430 }
431 ret = 1;
432
433 err:
434 return ret;
435 }
436
437 /* Computes a + b and stores the result in r. r could be a or b, a could be b.
438 * Uses algorithm A.10.2 of IEEE P1363.
439 */
440 int
ec_GF2m_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)441 ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
442 const EC_POINT *b, BN_CTX *ctx)
443 {
444 BN_CTX *new_ctx = NULL;
445 BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
446 int ret = 0;
447
448 if (EC_POINT_is_at_infinity(group, a) > 0) {
449 if (!EC_POINT_copy(r, b))
450 return 0;
451 return 1;
452 }
453 if (EC_POINT_is_at_infinity(group, b) > 0) {
454 if (!EC_POINT_copy(r, a))
455 return 0;
456 return 1;
457 }
458 if (ctx == NULL) {
459 ctx = new_ctx = BN_CTX_new();
460 if (ctx == NULL)
461 return 0;
462 }
463 BN_CTX_start(ctx);
464 if ((x0 = BN_CTX_get(ctx)) == NULL)
465 goto err;
466 if ((y0 = BN_CTX_get(ctx)) == NULL)
467 goto err;
468 if ((x1 = BN_CTX_get(ctx)) == NULL)
469 goto err;
470 if ((y1 = BN_CTX_get(ctx)) == NULL)
471 goto err;
472 if ((x2 = BN_CTX_get(ctx)) == NULL)
473 goto err;
474 if ((y2 = BN_CTX_get(ctx)) == NULL)
475 goto err;
476 if ((s = BN_CTX_get(ctx)) == NULL)
477 goto err;
478 if ((t = BN_CTX_get(ctx)) == NULL)
479 goto err;
480
481 if (a->Z_is_one) {
482 if (!BN_copy(x0, &a->X))
483 goto err;
484 if (!BN_copy(y0, &a->Y))
485 goto err;
486 } else {
487 if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
488 goto err;
489 }
490 if (b->Z_is_one) {
491 if (!BN_copy(x1, &b->X))
492 goto err;
493 if (!BN_copy(y1, &b->Y))
494 goto err;
495 } else {
496 if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
497 goto err;
498 }
499
500
501 if (BN_GF2m_cmp(x0, x1)) {
502 if (!BN_GF2m_add(t, x0, x1))
503 goto err;
504 if (!BN_GF2m_add(s, y0, y1))
505 goto err;
506 if (!group->meth->field_div(group, s, s, t, ctx))
507 goto err;
508 if (!group->meth->field_sqr(group, x2, s, ctx))
509 goto err;
510 if (!BN_GF2m_add(x2, x2, &group->a))
511 goto err;
512 if (!BN_GF2m_add(x2, x2, s))
513 goto err;
514 if (!BN_GF2m_add(x2, x2, t))
515 goto err;
516 } else {
517 if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
518 if (!EC_POINT_set_to_infinity(group, r))
519 goto err;
520 ret = 1;
521 goto err;
522 }
523 if (!group->meth->field_div(group, s, y1, x1, ctx))
524 goto err;
525 if (!BN_GF2m_add(s, s, x1))
526 goto err;
527
528 if (!group->meth->field_sqr(group, x2, s, ctx))
529 goto err;
530 if (!BN_GF2m_add(x2, x2, s))
531 goto err;
532 if (!BN_GF2m_add(x2, x2, &group->a))
533 goto err;
534 }
535
536 if (!BN_GF2m_add(y2, x1, x2))
537 goto err;
538 if (!group->meth->field_mul(group, y2, y2, s, ctx))
539 goto err;
540 if (!BN_GF2m_add(y2, y2, x2))
541 goto err;
542 if (!BN_GF2m_add(y2, y2, y1))
543 goto err;
544
545 if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
546 goto err;
547
548 ret = 1;
549
550 err:
551 BN_CTX_end(ctx);
552 BN_CTX_free(new_ctx);
553 return ret;
554 }
555
556
557 /* Computes 2 * a and stores the result in r. r could be a.
558 * Uses algorithm A.10.2 of IEEE P1363.
559 */
560 int
ec_GF2m_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)561 ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
562 BN_CTX *ctx)
563 {
564 return ec_GF2m_simple_add(group, r, a, a, ctx);
565 }
566
567 int
ec_GF2m_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)568 ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
569 {
570 if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y))
571 /* point is its own inverse */
572 return 1;
573
574 if (!EC_POINT_make_affine(group, point, ctx))
575 return 0;
576 return BN_GF2m_add(&point->Y, &point->X, &point->Y);
577 }
578
579
580 /* Indicates whether the given point is the point at infinity. */
581 int
ec_GF2m_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)582 ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
583 {
584 return BN_is_zero(&point->Z);
585 }
586
587
588 /* Determines whether the given EC_POINT is an actual point on the curve defined
589 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
590 * y^2 + x*y = x^3 + a*x^2 + b.
591 */
592 int
ec_GF2m_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)593 ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
594 {
595 int ret = -1;
596 BN_CTX *new_ctx = NULL;
597 BIGNUM *lh, *y2;
598 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
599 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
600
601 if (EC_POINT_is_at_infinity(group, point) > 0)
602 return 1;
603
604 field_mul = group->meth->field_mul;
605 field_sqr = group->meth->field_sqr;
606
607 /* only support affine coordinates */
608 if (!point->Z_is_one)
609 return -1;
610
611 if (ctx == NULL) {
612 ctx = new_ctx = BN_CTX_new();
613 if (ctx == NULL)
614 return -1;
615 }
616 BN_CTX_start(ctx);
617 if ((y2 = BN_CTX_get(ctx)) == NULL)
618 goto err;
619 if ((lh = BN_CTX_get(ctx)) == NULL)
620 goto err;
621
622 /*
623 * We have a curve defined by a Weierstrass equation y^2 + x*y = x^3
624 * + a*x^2 + b. <=> x^3 + a*x^2 + x*y + b + y^2 = 0 <=> ((x + a) * x
625 * + y ) * x + b + y^2 = 0
626 */
627 if (!BN_GF2m_add(lh, &point->X, &group->a))
628 goto err;
629 if (!field_mul(group, lh, lh, &point->X, ctx))
630 goto err;
631 if (!BN_GF2m_add(lh, lh, &point->Y))
632 goto err;
633 if (!field_mul(group, lh, lh, &point->X, ctx))
634 goto err;
635 if (!BN_GF2m_add(lh, lh, &group->b))
636 goto err;
637 if (!field_sqr(group, y2, &point->Y, ctx))
638 goto err;
639 if (!BN_GF2m_add(lh, lh, y2))
640 goto err;
641 ret = BN_is_zero(lh);
642 err:
643 if (ctx)
644 BN_CTX_end(ctx);
645 BN_CTX_free(new_ctx);
646 return ret;
647 }
648
649
650 /* Indicates whether two points are equal.
651 * Return values:
652 * -1 error
653 * 0 equal (in affine coordinates)
654 * 1 not equal
655 */
656 int
ec_GF2m_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)657 ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
658 const EC_POINT *b, BN_CTX *ctx)
659 {
660 BIGNUM *aX, *aY, *bX, *bY;
661 BN_CTX *new_ctx = NULL;
662 int ret = -1;
663
664 if (EC_POINT_is_at_infinity(group, a) > 0) {
665 return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1;
666 }
667 if (EC_POINT_is_at_infinity(group, b) > 0)
668 return 1;
669
670 if (a->Z_is_one && b->Z_is_one) {
671 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
672 }
673 if (ctx == NULL) {
674 ctx = new_ctx = BN_CTX_new();
675 if (ctx == NULL)
676 return -1;
677 }
678 BN_CTX_start(ctx);
679 if ((aX = BN_CTX_get(ctx)) == NULL)
680 goto err;
681 if ((aY = BN_CTX_get(ctx)) == NULL)
682 goto err;
683 if ((bX = BN_CTX_get(ctx)) == NULL)
684 goto err;
685 if ((bY = BN_CTX_get(ctx)) == NULL)
686 goto err;
687
688 if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
689 goto err;
690 if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
691 goto err;
692 ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
693
694 err:
695 if (ctx)
696 BN_CTX_end(ctx);
697 BN_CTX_free(new_ctx);
698 return ret;
699 }
700
701
702 /* Forces the given EC_POINT to internally use affine coordinates. */
703 int
ec_GF2m_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)704 ec_GF2m_simple_make_affine(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
705 {
706 BN_CTX *new_ctx = NULL;
707 BIGNUM *x, *y;
708 int ret = 0;
709
710 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0)
711 return 1;
712
713 if (ctx == NULL) {
714 ctx = new_ctx = BN_CTX_new();
715 if (ctx == NULL)
716 return 0;
717 }
718 BN_CTX_start(ctx);
719 if ((x = BN_CTX_get(ctx)) == NULL)
720 goto err;
721 if ((y = BN_CTX_get(ctx)) == NULL)
722 goto err;
723
724 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
725 goto err;
726 if (!BN_copy(&point->X, x))
727 goto err;
728 if (!BN_copy(&point->Y, y))
729 goto err;
730 if (!BN_one(&point->Z))
731 goto err;
732
733 ret = 1;
734
735 err:
736 if (ctx)
737 BN_CTX_end(ctx);
738 BN_CTX_free(new_ctx);
739 return ret;
740 }
741
742
743 /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
744 int
ec_GF2m_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)745 ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
746 EC_POINT *points[], BN_CTX *ctx)
747 {
748 size_t i;
749
750 for (i = 0; i < num; i++) {
751 if (!group->meth->make_affine(group, points[i], ctx))
752 return 0;
753 }
754
755 return 1;
756 }
757
758
759 /* Wrapper to simple binary polynomial field multiplication implementation. */
760 int
ec_GF2m_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)761 ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
762 const BIGNUM *b, BN_CTX *ctx)
763 {
764 return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
765 }
766
767
768 /* Wrapper to simple binary polynomial field squaring implementation. */
769 int
ec_GF2m_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)770 ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
771 BN_CTX *ctx)
772 {
773 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
774 }
775
776
777 /* Wrapper to simple binary polynomial field division implementation. */
778 int
ec_GF2m_simple_field_div(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)779 ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
780 const BIGNUM *b, BN_CTX *ctx)
781 {
782 return BN_GF2m_mod_div(r, a, b, &group->field, ctx);
783 }
784
785 #endif
786