Branch data Line data Source code
1 : : /* crypto/ec/ec2_smpl.c */
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 : : #define OPENSSL_FIPSAPI
71 : :
72 : : #include <openssl/err.h>
73 : :
74 : : #include "ec_lcl.h"
75 : :
76 : : #ifndef OPENSSL_NO_EC2M
77 : :
78 : :
79 : 1475 : const EC_METHOD *EC_GF2m_simple_method(void)
80 : : {
81 : : static const EC_METHOD ret = {
82 : : EC_FLAGS_DEFAULT_OCT,
83 : : NID_X9_62_characteristic_two_field,
84 : : ec_GF2m_simple_group_init,
85 : : ec_GF2m_simple_group_finish,
86 : : ec_GF2m_simple_group_clear_finish,
87 : : ec_GF2m_simple_group_copy,
88 : : ec_GF2m_simple_group_set_curve,
89 : : ec_GF2m_simple_group_get_curve,
90 : : ec_GF2m_simple_group_get_degree,
91 : : ec_GF2m_simple_group_check_discriminant,
92 : : ec_GF2m_simple_point_init,
93 : : ec_GF2m_simple_point_finish,
94 : : ec_GF2m_simple_point_clear_finish,
95 : : ec_GF2m_simple_point_copy,
96 : : ec_GF2m_simple_point_set_to_infinity,
97 : : 0 /* set_Jprojective_coordinates_GFp */,
98 : : 0 /* get_Jprojective_coordinates_GFp */,
99 : : ec_GF2m_simple_point_set_affine_coordinates,
100 : : ec_GF2m_simple_point_get_affine_coordinates,
101 : : 0,0,0,
102 : : ec_GF2m_simple_add,
103 : : ec_GF2m_simple_dbl,
104 : : ec_GF2m_simple_invert,
105 : : ec_GF2m_simple_is_at_infinity,
106 : : ec_GF2m_simple_is_on_curve,
107 : : ec_GF2m_simple_cmp,
108 : : ec_GF2m_simple_make_affine,
109 : : ec_GF2m_simple_points_make_affine,
110 : :
111 : : /* the following three method functions are defined in ec2_mult.c */
112 : : ec_GF2m_simple_mul,
113 : : ec_GF2m_precompute_mult,
114 : : ec_GF2m_have_precompute_mult,
115 : :
116 : : ec_GF2m_simple_field_mul,
117 : : ec_GF2m_simple_field_sqr,
118 : : ec_GF2m_simple_field_div,
119 : : 0 /* field_encode */,
120 : : 0 /* field_decode */,
121 : : 0 /* field_set_to_one */ };
122 : :
123 : 1475 : return &ret;
124 : : }
125 : :
126 : :
127 : : /* Initialize a GF(2^m)-based EC_GROUP structure.
128 : : * Note that all other members are handled by EC_GROUP_new.
129 : : */
130 : 4894 : int ec_GF2m_simple_group_init(EC_GROUP *group)
131 : : {
132 : 4894 : BN_init(&group->field);
133 : 4894 : BN_init(&group->a);
134 : 4894 : BN_init(&group->b);
135 : 4894 : 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 : 4894 : void ec_GF2m_simple_group_finish(EC_GROUP *group)
143 : : {
144 : 4894 : BN_free(&group->field);
145 : 4894 : BN_free(&group->a);
146 : 4894 : BN_free(&group->b);
147 : 4894 : }
148 : :
149 : :
150 : : /* Clear and free a GF(2^m)-based EC_GROUP structure.
151 : : * Note that all other members are handled by EC_GROUP_clear_free.
152 : : */
153 : 0 : void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
154 : : {
155 : 0 : BN_clear_free(&group->field);
156 : 0 : BN_clear_free(&group->a);
157 : 0 : BN_clear_free(&group->b);
158 : 0 : group->poly[0] = 0;
159 : 0 : group->poly[1] = 0;
160 : 0 : group->poly[2] = 0;
161 : 0 : group->poly[3] = 0;
162 : 0 : group->poly[4] = 0;
163 : 0 : group->poly[5] = -1;
164 : 0 : }
165 : :
166 : :
167 : : /* Copy a GF(2^m)-based EC_GROUP structure.
168 : : * Note that all other members are handled by EC_GROUP_copy.
169 : : */
170 : 3419 : int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
171 : : {
172 : : int i;
173 [ + - ]: 3419 : if (!BN_copy(&dest->field, &src->field)) return 0;
174 [ + - ]: 3419 : if (!BN_copy(&dest->a, &src->a)) return 0;
175 [ + - ]: 3419 : if (!BN_copy(&dest->b, &src->b)) return 0;
176 : 3419 : dest->poly[0] = src->poly[0];
177 : 3419 : dest->poly[1] = src->poly[1];
178 : 3419 : dest->poly[2] = src->poly[2];
179 : 3419 : dest->poly[3] = src->poly[3];
180 : 3419 : dest->poly[4] = src->poly[4];
181 : 3419 : dest->poly[5] = src->poly[5];
182 [ + + ][ + - ]: 3419 : if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0;
183 [ + + ][ + - ]: 3419 : if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0;
184 [ + + ]: 10296 : for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0;
185 [ + + ]: 3539 : for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0;
186 : : return 1;
187 : : }
188 : :
189 : :
190 : : /* Set the curve parameters of an EC_GROUP structure. */
191 : 1485 : int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
192 : : const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
193 : : {
194 : 1485 : int ret = 0, i;
195 : :
196 : : /* group->field */
197 [ + - ]: 1485 : if (!BN_copy(&group->field, p)) goto err;
198 : 1485 : i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1;
199 [ - + ]: 1485 : if ((i != 5) && (i != 3))
200 : : {
201 : 0 : ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
202 : 0 : goto err;
203 : : }
204 : :
205 : : /* group->a */
206 [ + - ]: 1485 : if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err;
207 [ + + ][ + - ]: 1485 : if(bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err;
208 [ + + ]: 4526 : for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0;
209 : :
210 : : /* group->b */
211 [ + - ]: 1485 : if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) goto err;
212 [ + + ][ + - ]: 1485 : if(bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err;
213 [ + + ]: 1669 : for (i = group->b.top; i < group->b.dmax; i++) group->b.d[i] = 0;
214 : :
215 : : ret = 1;
216 : : err:
217 : 1485 : return ret;
218 : : }
219 : :
220 : :
221 : : /* Get the curve parameters of an EC_GROUP structure.
222 : : * If p, a, or b are NULL then there values will not be set but the method will return with success.
223 : : */
224 : 5 : int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
225 : : {
226 : 5 : int ret = 0;
227 : :
228 [ + - ]: 5 : if (p != NULL)
229 : : {
230 [ + - ]: 5 : if (!BN_copy(p, &group->field)) return 0;
231 : : }
232 : :
233 [ + - ]: 5 : if (a != NULL)
234 : : {
235 [ + - ]: 5 : if (!BN_copy(a, &group->a)) goto err;
236 : : }
237 : :
238 [ + - ]: 5 : if (b != NULL)
239 : : {
240 [ + - ]: 5 : if (!BN_copy(b, &group->b)) goto err;
241 : : }
242 : :
243 : : ret = 1;
244 : :
245 : : err:
246 : 5 : return ret;
247 : : }
248 : :
249 : :
250 : : /* Gets the degree of the field. For a curve over GF(2^m) this is the value m. */
251 : 4703 : int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
252 : : {
253 : 4703 : return BN_num_bits(&group->field)-1;
254 : : }
255 : :
256 : :
257 : : /* Checks the discriminant of the curve.
258 : : * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
259 : : */
260 : 42 : int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
261 : : {
262 : 42 : int ret = 0;
263 : : BIGNUM *b;
264 : 42 : BN_CTX *new_ctx = NULL;
265 : :
266 [ - + ]: 42 : if (ctx == NULL)
267 : : {
268 : 0 : ctx = new_ctx = BN_CTX_new();
269 [ # # ]: 0 : if (ctx == NULL)
270 : : {
271 : 0 : ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
272 : 0 : goto err;
273 : : }
274 : : }
275 : 42 : BN_CTX_start(ctx);
276 : 42 : b = BN_CTX_get(ctx);
277 [ + - ]: 42 : if (b == NULL) goto err;
278 : :
279 [ + - ]: 42 : if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) goto err;
280 : :
281 : : /* check the discriminant:
282 : : * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
283 : : */
284 [ + - ]: 42 : if (BN_is_zero(b)) goto err;
285 : :
286 : 42 : ret = 1;
287 : :
288 : : err:
289 [ + - ]: 42 : if (ctx != NULL)
290 : 42 : BN_CTX_end(ctx);
291 [ - + ]: 42 : if (new_ctx != NULL)
292 : 0 : BN_CTX_free(new_ctx);
293 : 42 : return ret;
294 : : }
295 : :
296 : :
297 : : /* Initializes an EC_POINT. */
298 : 21093 : int ec_GF2m_simple_point_init(EC_POINT *point)
299 : : {
300 : 21093 : BN_init(&point->X);
301 : 21093 : BN_init(&point->Y);
302 : 21093 : BN_init(&point->Z);
303 : 21093 : return 1;
304 : : }
305 : :
306 : :
307 : : /* Frees an EC_POINT. */
308 : 21001 : void ec_GF2m_simple_point_finish(EC_POINT *point)
309 : : {
310 : 21001 : BN_free(&point->X);
311 : 21001 : BN_free(&point->Y);
312 : 21001 : BN_free(&point->Z);
313 : 21001 : }
314 : :
315 : :
316 : : /* Clears and frees an EC_POINT. */
317 : 92 : void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
318 : : {
319 : 92 : BN_clear_free(&point->X);
320 : 92 : BN_clear_free(&point->Y);
321 : 92 : BN_clear_free(&point->Z);
322 : 92 : point->Z_is_one = 0;
323 : 92 : }
324 : :
325 : :
326 : : /* Copy the contents of one EC_POINT into another. Assumes dest is initialized. */
327 : 13177 : int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
328 : : {
329 [ + - ]: 13177 : if (!BN_copy(&dest->X, &src->X)) return 0;
330 [ + - ]: 13177 : if (!BN_copy(&dest->Y, &src->Y)) return 0;
331 [ + - ]: 13177 : if (!BN_copy(&dest->Z, &src->Z)) return 0;
332 : 13177 : dest->Z_is_one = src->Z_is_one;
333 : :
334 : 13177 : return 1;
335 : : }
336 : :
337 : :
338 : : /* Set an EC_POINT to the point at infinity.
339 : : * A point at infinity is represented by having Z=0.
340 : : */
341 : 3218 : int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
342 : : {
343 : 3218 : point->Z_is_one = 0;
344 : 3218 : BN_zero(&point->Z);
345 : 3218 : return 1;
346 : : }
347 : :
348 : :
349 : : /* Set the coordinates of an EC_POINT using affine coordinates.
350 : : * Note that the simple implementation only uses affine coordinates.
351 : : */
352 : 14025 : int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
353 : : const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
354 : : {
355 : 14025 : int ret = 0;
356 [ - + ]: 14025 : if (x == NULL || y == NULL)
357 : : {
358 : 0 : ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
359 : 0 : return 0;
360 : : }
361 : :
362 [ + - ]: 14025 : if (!BN_copy(&point->X, x)) goto err;
363 : 14025 : BN_set_negative(&point->X, 0);
364 [ + - ]: 14025 : if (!BN_copy(&point->Y, y)) goto err;
365 : 14025 : BN_set_negative(&point->Y, 0);
366 [ + - ]: 14025 : if (!BN_copy(&point->Z, BN_value_one())) goto err;
367 : 14025 : BN_set_negative(&point->Z, 0);
368 : 14025 : point->Z_is_one = 1;
369 : 14025 : ret = 1;
370 : :
371 : : err:
372 : 14025 : return ret;
373 : : }
374 : :
375 : :
376 : : /* Gets the affine coordinates of an EC_POINT.
377 : : * Note that the simple implementation only uses affine coordinates.
378 : : */
379 : 2105 : int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
380 : : BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
381 : : {
382 : 2105 : int ret = 0;
383 : :
384 [ - + ]: 2105 : if (EC_POINT_is_at_infinity(group, point))
385 : : {
386 : 0 : ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
387 : 0 : return 0;
388 : : }
389 : :
390 [ - + ]: 2105 : if (BN_cmp(&point->Z, BN_value_one()))
391 : : {
392 : 0 : ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
393 : 0 : return 0;
394 : : }
395 [ + - ]: 2105 : if (x != NULL)
396 : : {
397 [ + - ]: 2105 : if (!BN_copy(x, &point->X)) goto err;
398 : 2105 : BN_set_negative(x, 0);
399 : : }
400 [ + + ]: 2105 : if (y != NULL)
401 : : {
402 [ + - ]: 1899 : if (!BN_copy(y, &point->Y)) goto err;
403 : 1899 : BN_set_negative(y, 0);
404 : : }
405 : : ret = 1;
406 : :
407 : : err:
408 : 2105 : return ret;
409 : : }
410 : :
411 : : /* Computes a + b and stores the result in r. r could be a or b, a could be b.
412 : : * Uses algorithm A.10.2 of IEEE P1363.
413 : : */
414 : 14914 : int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
415 : : {
416 : 14914 : BN_CTX *new_ctx = NULL;
417 : : BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
418 : 14914 : int ret = 0;
419 : :
420 [ + + ]: 14914 : if (EC_POINT_is_at_infinity(group, a))
421 : : {
422 [ + - ]: 3242 : if (!EC_POINT_copy(r, b)) return 0;
423 : 3242 : return 1;
424 : : }
425 : :
426 [ - + ]: 11672 : if (EC_POINT_is_at_infinity(group, b))
427 : : {
428 [ # # ]: 0 : if (!EC_POINT_copy(r, a)) return 0;
429 : 0 : return 1;
430 : : }
431 : :
432 [ - + ]: 11672 : if (ctx == NULL)
433 : : {
434 : 0 : ctx = new_ctx = BN_CTX_new();
435 [ # # ]: 0 : if (ctx == NULL)
436 : : return 0;
437 : : }
438 : :
439 : 11672 : BN_CTX_start(ctx);
440 : 11672 : x0 = BN_CTX_get(ctx);
441 : 11672 : y0 = BN_CTX_get(ctx);
442 : 11672 : x1 = BN_CTX_get(ctx);
443 : 11672 : y1 = BN_CTX_get(ctx);
444 : 11672 : x2 = BN_CTX_get(ctx);
445 : 11672 : y2 = BN_CTX_get(ctx);
446 : 11672 : s = BN_CTX_get(ctx);
447 : 11672 : t = BN_CTX_get(ctx);
448 [ + - ]: 11672 : if (t == NULL) goto err;
449 : :
450 [ + - ]: 11672 : if (a->Z_is_one)
451 : : {
452 [ + - ]: 11672 : if (!BN_copy(x0, &a->X)) goto err;
453 [ + - ]: 11672 : if (!BN_copy(y0, &a->Y)) goto err;
454 : : }
455 : : else
456 : : {
457 [ # # ]: 0 : if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) goto err;
458 : : }
459 [ + - ]: 11672 : if (b->Z_is_one)
460 : : {
461 [ + - ]: 11672 : if (!BN_copy(x1, &b->X)) goto err;
462 [ + - ]: 11672 : if (!BN_copy(y1, &b->Y)) goto err;
463 : : }
464 : : else
465 : : {
466 [ # # ]: 0 : if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) goto err;
467 : : }
468 : :
469 : :
470 [ + + ]: 11672 : if (BN_GF2m_cmp(x0, x1))
471 : : {
472 [ + - ]: 4109 : if (!BN_GF2m_add(t, x0, x1)) goto err;
473 [ + - ]: 4109 : if (!BN_GF2m_add(s, y0, y1)) goto err;
474 [ + - ]: 4109 : if (!group->meth->field_div(group, s, s, t, ctx)) goto err;
475 [ + - ]: 4109 : if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
476 [ + - ]: 4109 : if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
477 [ + - ]: 4109 : if (!BN_GF2m_add(x2, x2, s)) goto err;
478 [ + - ]: 4109 : if (!BN_GF2m_add(x2, x2, t)) goto err;
479 : : }
480 : : else
481 : : {
482 [ + + ][ - + ]: 7563 : if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1))
483 : : {
484 [ + - ]: 60 : if (!EC_POINT_set_to_infinity(group, r)) goto err;
485 : 60 : ret = 1;
486 : 60 : goto err;
487 : : }
488 [ + - ]: 7503 : if (!group->meth->field_div(group, s, y1, x1, ctx)) goto err;
489 [ + - ]: 7503 : if (!BN_GF2m_add(s, s, x1)) goto err;
490 : :
491 [ + - ]: 7503 : if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
492 [ + - ]: 7503 : if (!BN_GF2m_add(x2, x2, s)) goto err;
493 [ + - ]: 7503 : if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
494 : : }
495 : :
496 [ + - ]: 11612 : if (!BN_GF2m_add(y2, x1, x2)) goto err;
497 [ + - ]: 11612 : if (!group->meth->field_mul(group, y2, y2, s, ctx)) goto err;
498 [ + - ]: 11612 : if (!BN_GF2m_add(y2, y2, x2)) goto err;
499 [ + - ]: 11612 : if (!BN_GF2m_add(y2, y2, y1)) goto err;
500 : :
501 [ + - ]: 11612 : if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) goto err;
502 : :
503 : 11612 : ret = 1;
504 : :
505 : : err:
506 : 11672 : BN_CTX_end(ctx);
507 [ - + ]: 11672 : if (new_ctx != NULL)
508 : 0 : BN_CTX_free(new_ctx);
509 : 11672 : return ret;
510 : : }
511 : :
512 : :
513 : : /* Computes 2 * a and stores the result in r. r could be a.
514 : : * Uses algorithm A.10.2 of IEEE P1363.
515 : : */
516 : 7655 : int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
517 : : {
518 : 7655 : return ec_GF2m_simple_add(group, r, a, a, ctx);
519 : : }
520 : :
521 : :
522 : 512 : int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
523 : : {
524 [ + + ][ + - ]: 512 : if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
525 : : /* point is its own inverse */
526 : : return 1;
527 : :
528 [ + - ]: 468 : if (!EC_POINT_make_affine(group, point, ctx)) return 0;
529 : 468 : return BN_GF2m_add(&point->Y, &point->X, &point->Y);
530 : : }
531 : :
532 : :
533 : : /* Indicates whether the given point is the point at infinity. */
534 : 35626 : int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
535 : : {
536 : 35626 : return BN_is_zero(&point->Z);
537 : : }
538 : :
539 : :
540 : : /* Determines whether the given EC_POINT is an actual point on the curve defined
541 : : * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
542 : : * y^2 + x*y = x^3 + a*x^2 + b.
543 : : */
544 : 1016 : int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
545 : : {
546 : 1016 : int ret = -1;
547 : 1016 : BN_CTX *new_ctx = NULL;
548 : : BIGNUM *lh, *y2;
549 : : int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
550 : : int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
551 : :
552 [ + - ]: 1016 : if (EC_POINT_is_at_infinity(group, point))
553 : : return 1;
554 : :
555 : 1016 : field_mul = group->meth->field_mul;
556 : 1016 : field_sqr = group->meth->field_sqr;
557 : :
558 : : /* only support affine coordinates */
559 [ + - ]: 1016 : if (!point->Z_is_one) return -1;
560 : :
561 [ - + ]: 1016 : if (ctx == NULL)
562 : : {
563 : 0 : ctx = new_ctx = BN_CTX_new();
564 [ # # ]: 0 : if (ctx == NULL)
565 : : return -1;
566 : : }
567 : :
568 : 1016 : BN_CTX_start(ctx);
569 : 1016 : y2 = BN_CTX_get(ctx);
570 : 1016 : lh = BN_CTX_get(ctx);
571 [ + - ]: 1016 : if (lh == NULL) goto err;
572 : :
573 : : /* We have a curve defined by a Weierstrass equation
574 : : * y^2 + x*y = x^3 + a*x^2 + b.
575 : : * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
576 : : * <=> ((x + a) * x + y ) * x + b + y^2 = 0
577 : : */
578 [ + - ]: 1016 : if (!BN_GF2m_add(lh, &point->X, &group->a)) goto err;
579 [ + - ]: 1016 : if (!field_mul(group, lh, lh, &point->X, ctx)) goto err;
580 [ + - ]: 1016 : if (!BN_GF2m_add(lh, lh, &point->Y)) goto err;
581 [ + - ]: 1016 : if (!field_mul(group, lh, lh, &point->X, ctx)) goto err;
582 [ + - ]: 1016 : if (!BN_GF2m_add(lh, lh, &group->b)) goto err;
583 [ + - ]: 1016 : if (!field_sqr(group, y2, &point->Y, ctx)) goto err;
584 [ + - ]: 1016 : if (!BN_GF2m_add(lh, lh, y2)) goto err;
585 : 1016 : ret = BN_is_zero(lh);
586 : : err:
587 [ + - ]: 1016 : if (ctx) BN_CTX_end(ctx);
588 [ - + ]: 1016 : if (new_ctx) BN_CTX_free(new_ctx);
589 : 1016 : return ret;
590 : : }
591 : :
592 : :
593 : : /* Indicates whether two points are equal.
594 : : * Return values:
595 : : * -1 error
596 : : * 0 equal (in affine coordinates)
597 : : * 1 not equal
598 : : */
599 : 90 : int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
600 : : {
601 : : BIGNUM *aX, *aY, *bX, *bY;
602 : 90 : BN_CTX *new_ctx = NULL;
603 : 90 : int ret = -1;
604 : :
605 [ + + ]: 90 : if (EC_POINT_is_at_infinity(group, a))
606 : : {
607 : 30 : return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
608 : : }
609 : :
610 [ + - ]: 60 : if (EC_POINT_is_at_infinity(group, b))
611 : : return 1;
612 : :
613 [ + - ][ + - ]: 60 : if (a->Z_is_one && b->Z_is_one)
614 : : {
615 [ + + ][ - + ]: 60 : return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
616 : : }
617 : :
618 [ # # ]: 0 : if (ctx == NULL)
619 : : {
620 : 0 : ctx = new_ctx = BN_CTX_new();
621 [ # # ]: 0 : if (ctx == NULL)
622 : : return -1;
623 : : }
624 : :
625 : 0 : BN_CTX_start(ctx);
626 : 0 : aX = BN_CTX_get(ctx);
627 : 0 : aY = BN_CTX_get(ctx);
628 : 0 : bX = BN_CTX_get(ctx);
629 : 0 : bY = BN_CTX_get(ctx);
630 [ # # ]: 0 : if (bY == NULL) goto err;
631 : :
632 [ # # ]: 0 : if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) goto err;
633 [ # # ]: 0 : if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) goto err;
634 [ # # ][ # # ]: 0 : ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
635 : :
636 : : err:
637 [ # # ]: 0 : if (ctx) BN_CTX_end(ctx);
638 [ # # ]: 0 : if (new_ctx) BN_CTX_free(new_ctx);
639 : 0 : return ret;
640 : : }
641 : :
642 : :
643 : : /* Forces the given EC_POINT to internally use affine coordinates. */
644 : 3920 : int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
645 : : {
646 : 3920 : BN_CTX *new_ctx = NULL;
647 : : BIGNUM *x, *y;
648 : 3920 : int ret = 0;
649 : :
650 [ - + ][ # # ]: 3920 : if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
651 : : return 1;
652 : :
653 [ # # ]: 0 : if (ctx == NULL)
654 : : {
655 : 0 : ctx = new_ctx = BN_CTX_new();
656 [ # # ]: 0 : if (ctx == NULL)
657 : : return 0;
658 : : }
659 : :
660 : 0 : BN_CTX_start(ctx);
661 : 0 : x = BN_CTX_get(ctx);
662 : 0 : y = BN_CTX_get(ctx);
663 [ # # ]: 0 : if (y == NULL) goto err;
664 : :
665 [ # # ]: 0 : if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
666 [ # # ]: 0 : if (!BN_copy(&point->X, x)) goto err;
667 [ # # ]: 0 : if (!BN_copy(&point->Y, y)) goto err;
668 [ # # ]: 0 : if (!BN_one(&point->Z)) goto err;
669 : :
670 : 0 : ret = 1;
671 : :
672 : : err:
673 [ # # ]: 0 : if (ctx) BN_CTX_end(ctx);
674 [ # # ]: 0 : if (new_ctx) BN_CTX_free(new_ctx);
675 : 0 : return ret;
676 : : }
677 : :
678 : :
679 : : /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
680 : 31 : int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
681 : : {
682 : : size_t i;
683 : :
684 [ + + ]: 3483 : for (i = 0; i < num; i++)
685 : : {
686 [ + - ]: 3452 : if (!group->meth->make_affine(group, points[i], ctx)) return 0;
687 : : }
688 : :
689 : : return 1;
690 : : }
691 : :
692 : :
693 : : /* Wrapper to simple binary polynomial field multiplication implementation. */
694 : 3463650 : int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
695 : : {
696 : 3463650 : return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
697 : : }
698 : :
699 : :
700 : : /* Wrapper to simple binary polynomial field squaring implementation. */
701 : 2871179 : int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
702 : : {
703 : 2871179 : return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
704 : : }
705 : :
706 : :
707 : : /* Wrapper to simple binary polynomial field division implementation. */
708 : 14726 : int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
709 : : {
710 : 14726 : return BN_GF2m_mod_div(r, a, b, &group->field, ctx);
711 : : }
712 : :
713 : : #endif
|
