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