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