]> git.ipfire.org Git - thirdparty/openssl.git/blame - crypto/ec/ec2_smpl.c
projects / thirdparty / openssl.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Fix external symbols related to ec & sm2 keys
[thirdparty/openssl.git] / crypto / ec / ec2_smpl.c
CommitLineData
4f22f405 1/*
33388b44 2 * Copyright 2002-2020 The OpenSSL Project Authors. All Rights Reserved.
aa8f3d76 3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4f22f405 4 *
a7f182b7 5 * Licensed under the Apache License 2.0 (the "License"). You may not use
4f22f405
RS		 6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 */
10
579422c8
P		 11/*
12 * ECDSA low level APIs are deprecated for public use, but still ok for
13 * internal use.
14 */
15#include "internal/deprecated.h"
16
7793f30e
BM		 17#include <openssl/err.h>
18
25f2138b 19#include "crypto/bn.h"
706457b7 20#include "ec_local.h"
7793f30e 21
b3310161
DSH		 22#ifndef OPENSSL_NO_EC2M
23
0f113f3e
MC		 24/*
25 * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
26 * are handled by EC_GROUP_new.
7793f30e 27 */
32ab57cb 28int ossl_ec_GF2m_simple_group_init(EC_GROUP *group)
0f113f3e
MC		 29{
30 group->field = BN_new();
31 group->a = BN_new();
32 group->b = BN_new();
33
90945fa3 34 if (group->field == NULL || group->a == NULL || group->b == NULL) {
23a1d5e9
RS		 35 BN_free(group->field);
36 BN_free(group->a);
37 BN_free(group->b);
0f113f3e
MC		 38 return 0;
39 }
40 return 1;
41}
42
43/*
44 * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
45 * handled by EC_GROUP_free.
7793f30e 46 */
32ab57cb 47void ossl_ec_GF2m_simple_group_finish(EC_GROUP *group)
0f113f3e
MC		 48{
49 BN_free(group->field);
50 BN_free(group->a);
51 BN_free(group->b);
52}
53
54/*
55 * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
56 * members are handled by EC_GROUP_clear_free.
7793f30e 57 */
32ab57cb 58void ossl_ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
0f113f3e
MC		 59{
60 BN_clear_free(group->field);
61 BN_clear_free(group->a);
62 BN_clear_free(group->b);
63 group->poly[0] = 0;
64 group->poly[1] = 0;
65 group->poly[2] = 0;
66 group->poly[3] = 0;
67 group->poly[4] = 0;
68 group->poly[5] = -1;
69}
70
71/*
72 * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
73 * handled by EC_GROUP_copy.
7793f30e 74 */
32ab57cb 75int ossl_ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
0f113f3e
MC		 76{
77 if (!BN_copy(dest->field, src->field))
78 return 0;
79 if (!BN_copy(dest->a, src->a))
80 return 0;
81 if (!BN_copy(dest->b, src->b))
82 return 0;
83 dest->poly[0] = src->poly[0];
84 dest->poly[1] = src->poly[1];
85 dest->poly[2] = src->poly[2];
86 dest->poly[3] = src->poly[3];
87 dest->poly[4] = src->poly[4];
88 dest->poly[5] = src->poly[5];
89 if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
90 NULL)
91 return 0;
92 if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
93 NULL)
94 return 0;
95 bn_set_all_zero(dest->a);
96 bn_set_all_zero(dest->b);
97 return 1;
98}
7793f30e
BM		 99
100/* Set the curve parameters of an EC_GROUP structure. */
32ab57cb
SL		 101int ossl_ec_GF2m_simple_group_set_curve(EC_GROUP *group,
102 const BIGNUM *p, const BIGNUM *a,
103 const BIGNUM *b, BN_CTX *ctx)
0f113f3e
MC		 104{
105 int ret = 0, i;
106
107 /* group->field */
108 if (!BN_copy(group->field, p))
109 goto err;
110 i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
111 if ((i != 5) && (i != 3)) {
9311d0c4 112 ERR_raise(ERR_LIB_EC, EC_R_UNSUPPORTED_FIELD);
0f113f3e
MC		 113 goto err;
114 }
115
116 /* group->a */
117 if (!BN_GF2m_mod_arr(group->a, a, group->poly))
118 goto err;
119 if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
120 == NULL)
121 goto err;
122 bn_set_all_zero(group->a);
123
124 /* group->b */
125 if (!BN_GF2m_mod_arr(group->b, b, group->poly))
126 goto err;
127 if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
128 == NULL)
129 goto err;
130 bn_set_all_zero(group->b);
131
132 ret = 1;
133 err:
134 return ret;
135}
136
137/*
138 * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
139 * then there values will not be set but the method will return with success.
7793f30e 140 */
32ab57cb
SL		 141int ossl_ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
142 BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
0f113f3e
MC		 143{
144 int ret = 0;
145
146 if (p != NULL) {
147 if (!BN_copy(p, group->field))
148 return 0;
149 }
150
151 if (a != NULL) {
152 if (!BN_copy(a, group->a))
153 goto err;
154 }
7793f30e 155
0f113f3e
MC		 156 if (b != NULL) {
157 if (!BN_copy(b, group->b))
158 goto err;
159 }
7793f30e 160
0f113f3e
MC		 161 ret = 1;
162
163 err:
164 return ret;
165}
166
167/*
168 * Gets the degree of the field. For a curve over GF(2^m) this is the value
169 * m.
170 */
32ab57cb 171int ossl_ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
0f113f3e
MC		 172{
173 return BN_num_bits(group->field) - 1;
174}
175
176/*
177 * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
178 * elliptic curve <=> b != 0 (mod p)
7793f30e 179 */
32ab57cb
SL		 180int ossl_ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
181 BN_CTX *ctx)
0f113f3e
MC		 182{
183 int ret = 0;
184 BIGNUM *b;
f844f9eb 185#ifndef FIPS_MODULE
0f113f3e
MC		 186 BN_CTX *new_ctx = NULL;
187
188 if (ctx == NULL) {
189 ctx = new_ctx = BN_CTX_new();
190 if (ctx == NULL) {
9311d0c4 191 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
0f113f3e
MC		 192 goto err;
193 }
194 }
a9612d6c 195#endif
0f113f3e
MC		 196 BN_CTX_start(ctx);
197 b = BN_CTX_get(ctx);
198 if (b == NULL)
199 goto err;
200
201 if (!BN_GF2m_mod_arr(b, group->b, group->poly))
202 goto err;
203
204 /*
205 * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
206 * curve <=> b != 0 (mod p)
207 */
208 if (BN_is_zero(b))
209 goto err;
210
211 ret = 1;
7793f30e 212
0f113f3e 213 err:
ce1415ed 214 BN_CTX_end(ctx);
f844f9eb 215#ifndef FIPS_MODULE
23a1d5e9 216 BN_CTX_free(new_ctx);
a9612d6c 217#endif
0f113f3e
MC		 218 return ret;
219}
7793f30e
BM		 220
221/* Initializes an EC_POINT. */
32ab57cb 222int ossl_ec_GF2m_simple_point_init(EC_POINT *point)
0f113f3e
MC		 223{
224 point->X = BN_new();
225 point->Y = BN_new();
226 point->Z = BN_new();
227
90945fa3 228 if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
23a1d5e9
RS		 229 BN_free(point->X);
230 BN_free(point->Y);
231 BN_free(point->Z);
0f113f3e
MC		 232 return 0;
233 }
234 return 1;
235}
7793f30e
BM		 236
237/* Frees an EC_POINT. */
32ab57cb 238void ossl_ec_GF2m_simple_point_finish(EC_POINT *point)
0f113f3e
MC		 239{
240 BN_free(point->X);
241 BN_free(point->Y);
242 BN_free(point->Z);
243}
7793f30e
BM		 244
245/* Clears and frees an EC_POINT. */
32ab57cb 246void ossl_ec_GF2m_simple_point_clear_finish(EC_POINT *point)
0f113f3e
MC		 247{
248 BN_clear_free(point->X);
249 BN_clear_free(point->Y);
250 BN_clear_free(point->Z);
251 point->Z_is_one = 0;
252}
253
254/*
255 * Copy the contents of one EC_POINT into another. Assumes dest is
256 * initialized.
7793f30e 257 */
32ab57cb 258int ossl_ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
0f113f3e
MC		 259{
260 if (!BN_copy(dest->X, src->X))
261 return 0;
262 if (!BN_copy(dest->Y, src->Y))
263 return 0;
264 if (!BN_copy(dest->Z, src->Z))
265 return 0;
266 dest->Z_is_one = src->Z_is_one;
b14e6015 267 dest->curve_name = src->curve_name;
0f113f3e
MC		 268
269 return 1;
270}
271
272/*
273 * Set an EC_POINT to the point at infinity. A point at infinity is
274 * represented by having Z=0.
7793f30e 275 */
32ab57cb
SL		 276int ossl_ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
277 EC_POINT *point)
0f113f3e
MC		 278{
279 point->Z_is_one = 0;
280 BN_zero(point->Z);
281 return 1;
282}
283
284/*
285 * Set the coordinates of an EC_POINT using affine coordinates. Note that
286 * the simple implementation only uses affine coordinates.
7793f30e 287 */
32ab57cb
SL		 288int ossl_ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
289 EC_POINT *point,
290 const BIGNUM *x,
291 const BIGNUM *y,
292 BN_CTX *ctx)
0f113f3e
MC		 293{
294 int ret = 0;
295 if (x == NULL || y == NULL) {
9311d0c4 296 ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER);
0f113f3e
MC		 297 return 0;
298 }
299
300 if (!BN_copy(point->X, x))
301 goto err;
302 BN_set_negative(point->X, 0);
303 if (!BN_copy(point->Y, y))
304 goto err;
305 BN_set_negative(point->Y, 0);
306 if (!BN_copy(point->Z, BN_value_one()))
307 goto err;
308 BN_set_negative(point->Z, 0);
309 point->Z_is_one = 1;
310 ret = 1;
311
7793f30e 312 err:
0f113f3e
MC		 313 return ret;
314}
7793f30e 315
0f113f3e
MC		 316/*
317 * Gets the affine coordinates of an EC_POINT. Note that the simple
318 * implementation only uses affine coordinates.
7793f30e 319 */
32ab57cb
SL		 320int ossl_ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
321 const EC_POINT *point,
322 BIGNUM *x, BIGNUM *y,
323 BN_CTX *ctx)
0f113f3e
MC		 324{
325 int ret = 0;
326
327 if (EC_POINT_is_at_infinity(group, point)) {
9311d0c4 328 ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
0f113f3e
MC		 329 return 0;
330 }
331
332 if (BN_cmp(point->Z, BN_value_one())) {
9311d0c4 333 ERR_raise(ERR_LIB_EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
0f113f3e
MC		 334 return 0;
335 }
336 if (x != NULL) {
337 if (!BN_copy(x, point->X))
338 goto err;
339 BN_set_negative(x, 0);
340 }
341 if (y != NULL) {
342 if (!BN_copy(y, point->Y))
343 goto err;
344 BN_set_negative(y, 0);
345 }
346 ret = 1;
7793f30e
BM		 347
348 err:
0f113f3e
MC		 349 return ret;
350}
7793f30e 351
0f113f3e
MC		 352/*
353 * Computes a + b and stores the result in r. r could be a or b, a could be
354 * b. Uses algorithm A.10.2 of IEEE P1363.
7793f30e 355 */
32ab57cb
SL		 356int ossl_ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r,
357 const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
0f113f3e 358{
0f113f3e
MC		 359 BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
360 int ret = 0;
f844f9eb 361#ifndef FIPS_MODULE
a9612d6c
MC		 362 BN_CTX *new_ctx = NULL;
363#endif
0f113f3e
MC		 364
365 if (EC_POINT_is_at_infinity(group, a)) {
366 if (!EC_POINT_copy(r, b))
367 return 0;
368 return 1;
369 }
370
371 if (EC_POINT_is_at_infinity(group, b)) {
372 if (!EC_POINT_copy(r, a))
373 return 0;
374 return 1;
375 }
376
f844f9eb 377#ifndef FIPS_MODULE
0f113f3e
MC		 378 if (ctx == NULL) {
379 ctx = new_ctx = BN_CTX_new();
380 if (ctx == NULL)
381 return 0;
382 }
a9612d6c 383#endif
0f113f3e
MC		 384
385 BN_CTX_start(ctx);
386 x0 = BN_CTX_get(ctx);
387 y0 = BN_CTX_get(ctx);
388 x1 = BN_CTX_get(ctx);
389 y1 = BN_CTX_get(ctx);
390 x2 = BN_CTX_get(ctx);
391 y2 = BN_CTX_get(ctx);
392 s = BN_CTX_get(ctx);
393 t = BN_CTX_get(ctx);
394 if (t == NULL)
395 goto err;
396
397 if (a->Z_is_one) {
398 if (!BN_copy(x0, a->X))
399 goto err;
400 if (!BN_copy(y0, a->Y))
401 goto err;
402 } else {
9cc570d4 403 if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
0f113f3e
MC		 404 goto err;
405 }
406 if (b->Z_is_one) {
407 if (!BN_copy(x1, b->X))
408 goto err;
409 if (!BN_copy(y1, b->Y))
410 goto err;
411 } else {
9cc570d4 412 if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
0f113f3e
MC		 413 goto err;
414 }
415
416 if (BN_GF2m_cmp(x0, x1)) {
417 if (!BN_GF2m_add(t, x0, x1))
418 goto err;
419 if (!BN_GF2m_add(s, y0, y1))
420 goto err;
421 if (!group->meth->field_div(group, s, s, t, ctx))
422 goto err;
423 if (!group->meth->field_sqr(group, x2, s, ctx))
424 goto err;
425 if (!BN_GF2m_add(x2, x2, group->a))
426 goto err;
427 if (!BN_GF2m_add(x2, x2, s))
428 goto err;
429 if (!BN_GF2m_add(x2, x2, t))
430 goto err;
431 } else {
432 if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
433 if (!EC_POINT_set_to_infinity(group, r))
434 goto err;
435 ret = 1;
436 goto err;
437 }
438 if (!group->meth->field_div(group, s, y1, x1, ctx))
439 goto err;
440 if (!BN_GF2m_add(s, s, x1))
441 goto err;
442
443 if (!group->meth->field_sqr(group, x2, s, ctx))
444 goto err;
445 if (!BN_GF2m_add(x2, x2, s))
446 goto err;
447 if (!BN_GF2m_add(x2, x2, group->a))
448 goto err;
449 }
450
451 if (!BN_GF2m_add(y2, x1, x2))
452 goto err;
453 if (!group->meth->field_mul(group, y2, y2, s, ctx))
454 goto err;
455 if (!BN_GF2m_add(y2, y2, x2))
456 goto err;
457 if (!BN_GF2m_add(y2, y2, y1))
458 goto err;
459
9cc570d4 460 if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
0f113f3e
MC		 461 goto err;
462
463 ret = 1;
7793f30e 464
0f113f3e
MC		 465 err:
466 BN_CTX_end(ctx);
f844f9eb 467#ifndef FIPS_MODULE
23a1d5e9 468 BN_CTX_free(new_ctx);
a9612d6c 469#endif
0f113f3e
MC		 470 return ret;
471}
472
473/*
474 * Computes 2 * a and stores the result in r. r could be a. Uses algorithm
475 * A.10.2 of IEEE P1363.
476 */
32ab57cb
SL		 477int ossl_ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r,
478 const EC_POINT *a, BN_CTX *ctx)
0f113f3e 479{
32ab57cb 480 return ossl_ec_GF2m_simple_add(group, r, a, a, ctx);
0f113f3e 481}
7793f30e 482
32ab57cb
SL		 483int ossl_ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point,
484 BN_CTX *ctx)
0f113f3e
MC		 485{
486 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
487 /* point is its own inverse */
488 return 1;
7793f30e 489
c2f2db9b
BB		 490 if (group->meth->make_affine == NULL
491 || !group->meth->make_affine(group, point, ctx))
0f113f3e
MC		 492 return 0;
493 return BN_GF2m_add(point->Y, point->X, point->Y);
494}
7793f30e
BM		 495
496/* Indicates whether the given point is the point at infinity. */
32ab57cb
SL		 497int ossl_ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
498 const EC_POINT *point)
0f113f3e
MC		 499{
500 return BN_is_zero(point->Z);
501}
7793f30e 502
23a22b4c
MC		 503/*-
504 * Determines whether the given EC_POINT is an actual point on the curve defined
7793f30e
BM		 505 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
506 * y^2 + x*y = x^3 + a*x^2 + b.
507 */
32ab57cb
SL		 508int ossl_ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
509 BN_CTX *ctx)
0f113f3e
MC		 510{
511 int ret = -1;
0f113f3e
MC		 512 BIGNUM *lh, *y2;
513 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
514 const BIGNUM *, BN_CTX *);
515 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
f844f9eb 516#ifndef FIPS_MODULE
a9612d6c
MC		 517 BN_CTX *new_ctx = NULL;
518#endif
0f113f3e
MC		 519
520 if (EC_POINT_is_at_infinity(group, point))
521 return 1;
522
523 field_mul = group->meth->field_mul;
524 field_sqr = group->meth->field_sqr;
525
526 /* only support affine coordinates */
527 if (!point->Z_is_one)
528 return -1;
529
f844f9eb 530#ifndef FIPS_MODULE
0f113f3e
MC		 531 if (ctx == NULL) {
532 ctx = new_ctx = BN_CTX_new();
533 if (ctx == NULL)
534 return -1;
535 }
a9612d6c 536#endif
0f113f3e
MC		 537
538 BN_CTX_start(ctx);
539 y2 = BN_CTX_get(ctx);
540 lh = BN_CTX_get(ctx);
541 if (lh == NULL)
542 goto err;
543
50e735f9
MC		 544 /*-
545 * We have a curve defined by a Weierstrass equation
546 * y^2 + x*y = x^3 + a*x^2 + b.
547 * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
548 * <=> ((x + a) * x + y ) * x + b + y^2 = 0
549 */
0f113f3e
MC		 550 if (!BN_GF2m_add(lh, point->X, group->a))
551 goto err;
552 if (!field_mul(group, lh, lh, point->X, ctx))
553 goto err;
554 if (!BN_GF2m_add(lh, lh, point->Y))
555 goto err;
556 if (!field_mul(group, lh, lh, point->X, ctx))
557 goto err;
558 if (!BN_GF2m_add(lh, lh, group->b))
559 goto err;
560 if (!field_sqr(group, y2, point->Y, ctx))
561 goto err;
562 if (!BN_GF2m_add(lh, lh, y2))
563 goto err;
564 ret = BN_is_zero(lh);
a0fda2cf 565
7793f30e 566 err:
a0fda2cf 567 BN_CTX_end(ctx);
f844f9eb 568#ifndef FIPS_MODULE
23a1d5e9 569 BN_CTX_free(new_ctx);
a9612d6c 570#endif
0f113f3e
MC		 571 return ret;
572}
7793f30e 573
1d97c843
TH		 574/*-
575 * Indicates whether two points are equal.
7793f30e
BM		 576 * Return values:
577 * -1 error
578 * 0 equal (in affine coordinates)
579 * 1 not equal
580 */
32ab57cb
SL		 581int ossl_ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
582 const EC_POINT *b, BN_CTX *ctx)
0f113f3e
MC		 583{
584 BIGNUM *aX, *aY, *bX, *bY;
0f113f3e 585 int ret = -1;
f844f9eb 586#ifndef FIPS_MODULE
a9612d6c
MC		 587 BN_CTX *new_ctx = NULL;
588#endif
0f113f3e
MC		 589
590 if (EC_POINT_is_at_infinity(group, a)) {
591 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
592 }
593
594 if (EC_POINT_is_at_infinity(group, b))
595 return 1;
596
597 if (a->Z_is_one && b->Z_is_one) {
598 return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
599 }
600
f844f9eb 601#ifndef FIPS_MODULE
0f113f3e
MC		 602 if (ctx == NULL) {
603 ctx = new_ctx = BN_CTX_new();
604 if (ctx == NULL)
605 return -1;
606 }
a9612d6c 607#endif
0f113f3e
MC		 608
609 BN_CTX_start(ctx);
610 aX = BN_CTX_get(ctx);
611 aY = BN_CTX_get(ctx);
612 bX = BN_CTX_get(ctx);
613 bY = BN_CTX_get(ctx);
614 if (bY == NULL)
615 goto err;
616
9cc570d4 617 if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
0f113f3e 618 goto err;
9cc570d4 619 if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
0f113f3e
MC		 620 goto err;
621 ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
7793f30e 622
0f113f3e 623 err:
a0fda2cf 624 BN_CTX_end(ctx);
f844f9eb 625#ifndef FIPS_MODULE
23a1d5e9 626 BN_CTX_free(new_ctx);
a9612d6c 627#endif
0f113f3e
MC		 628 return ret;
629}
7793f30e
BM		 630
631/* Forces the given EC_POINT to internally use affine coordinates. */
32ab57cb
SL		 632int ossl_ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
633 BN_CTX *ctx)
0f113f3e 634{
0f113f3e
MC		 635 BIGNUM *x, *y;
636 int ret = 0;
f844f9eb 637#ifndef FIPS_MODULE
a9612d6c
MC		 638 BN_CTX *new_ctx = NULL;
639#endif
0f113f3e
MC		 640
641 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
642 return 1;
643
f844f9eb 644#ifndef FIPS_MODULE
0f113f3e
MC		 645 if (ctx == NULL) {
646 ctx = new_ctx = BN_CTX_new();
647 if (ctx == NULL)
648 return 0;
649 }
a9612d6c 650#endif
0f113f3e
MC		 651
652 BN_CTX_start(ctx);
653 x = BN_CTX_get(ctx);
654 y = BN_CTX_get(ctx);
655 if (y == NULL)
656 goto err;
657
9cc570d4 658 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
0f113f3e
MC		 659 goto err;
660 if (!BN_copy(point->X, x))
661 goto err;
662 if (!BN_copy(point->Y, y))
663 goto err;
664 if (!BN_one(point->Z))
665 goto err;
dd67493c 666 point->Z_is_one = 1;
0f113f3e
MC		 667
668 ret = 1;
669
670 err:
a0fda2cf 671 BN_CTX_end(ctx);
f844f9eb 672#ifndef FIPS_MODULE
23a1d5e9 673 BN_CTX_free(new_ctx);
a9612d6c 674#endif
0f113f3e
MC		 675 return ret;
676}
677
678/*
679 * Forces each of the EC_POINTs in the given array to use affine coordinates.
680 */
32ab57cb
SL		 681int ossl_ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
682 EC_POINT *points[], BN_CTX *ctx)
0f113f3e
MC		 683{
684 size_t i;
7793f30e 685
0f113f3e
MC		 686 for (i = 0; i < num; i++) {
687 if (!group->meth->make_affine(group, points[i], ctx))
688 return 0;
689 }
7793f30e 690
0f113f3e
MC		 691 return 1;
692}
7793f30e 693
0f113f3e 694/* Wrapper to simple binary polynomial field multiplication implementation. */
32ab57cb
SL		 695int ossl_ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
696 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
0f113f3e
MC		 697{
698 return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
699}
7793f30e
BM		 700
701/* Wrapper to simple binary polynomial field squaring implementation. */
32ab57cb
SL		 702int ossl_ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
703 const BIGNUM *a, BN_CTX *ctx)
0f113f3e
MC		 704{
705 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
706}
7793f30e
BM		 707
708/* Wrapper to simple binary polynomial field division implementation. */
32ab57cb
SL		 709int ossl_ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
710 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
0f113f3e
MC		 711{
712 return BN_GF2m_mod_div(r, a, b, group->field, ctx);
713}
b3310161 714
f45846f5
NT		 715/*-
716 * Lopez-Dahab ladder, pre step.
717 * See e.g. "Guide to ECC" Alg 3.40.
718 * Modified to blind s and r independently.
719 * s:= p, r := 2p
720 */
721static
722int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
723 EC_POINT *r, EC_POINT *s,
724 EC_POINT *p, BN_CTX *ctx)
725{
726 /* if p is not affine, something is wrong */
727 if (p->Z_is_one == 0)
728 return 0;
729
730 /* s blinding: make sure lambda (s->Z here) is not zero */
731 do {
a9612d6c
MC		 732 if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
733 BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
9311d0c4 734 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
f45846f5
NT		 735 return 0;
736 }
737 } while (BN_is_zero(s->Z));
738
739 /* if field_encode defined convert between representations */
740 if ((group->meth->field_encode != NULL
741 && !group->meth->field_encode(group, s->Z, s->Z, ctx))
742 || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
743 return 0;
744
745 /* r blinding: make sure lambda (r->Y here for storage) is not zero */
746 do {
a9612d6c
MC		 747 if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
748 BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
9311d0c4 749 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
f45846f5
NT		 750 return 0;
751 }
752 } while (BN_is_zero(r->Y));
753
754 if ((group->meth->field_encode != NULL
755 && !group->meth->field_encode(group, r->Y, r->Y, ctx))
756 || !group->meth->field_sqr(group, r->Z, p->X, ctx)
757 || !group->meth->field_sqr(group, r->X, r->Z, ctx)
758 || !BN_GF2m_add(r->X, r->X, group->b)
759 || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
760 || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
761 return 0;
762
763 s->Z_is_one = 0;
764 r->Z_is_one = 0;
765
766 return 1;
767}
768
769/*-
770 * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
771 * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
772 * s := r + s, r := 2r
773 */
774static
775int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
776 EC_POINT *r, EC_POINT *s,
777 EC_POINT *p, BN_CTX *ctx)
778{
779 if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
780 || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
781 || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
782 || !group->meth->field_sqr(group, r->Z, r->X, ctx)
783 || !BN_GF2m_add(s->Z, r->Y, s->X)
784 || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
785 || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
786 || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
787 || !BN_GF2m_add(s->X, s->X, r->Y)
788 || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
789 || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
790 || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
791 || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
792 || !BN_GF2m_add(r->X, r->Y, s->Y))
793 return 0;
794
795 return 1;
796}
797
798/*-
799 * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
800 * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
801 * without Precomputation" (Lopez and Dahab, CHES 1999),
802 * Appendix Alg Mxy.
803 */
804static
805int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
806 EC_POINT *r, EC_POINT *s,
807 EC_POINT *p, BN_CTX *ctx)
808{
809 int ret = 0;
810 BIGNUM *t0, *t1, *t2 = NULL;
811
812 if (BN_is_zero(r->Z))
813 return EC_POINT_set_to_infinity(group, r);
814
815 if (BN_is_zero(s->Z)) {
816 if (!EC_POINT_copy(r, p)
817 || !EC_POINT_invert(group, r, ctx)) {
9311d0c4 818 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
f45846f5
NT		 819 return 0;
820 }
821 return 1;
822 }
823
824 BN_CTX_start(ctx);
825 t0 = BN_CTX_get(ctx);
826 t1 = BN_CTX_get(ctx);
827 t2 = BN_CTX_get(ctx);
828 if (t2 == NULL) {
9311d0c4 829 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
f45846f5
NT		 830 goto err;
831 }
832
833 if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
834 || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
835 || !BN_GF2m_add(t1, r->X, t1)
836 || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
837 || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
838 || !BN_GF2m_add(t2, t2, s->X)
839 || !group->meth->field_mul(group, t1, t1, t2, ctx)
840 || !group->meth->field_sqr(group, t2, p->X, ctx)
841 || !BN_GF2m_add(t2, p->Y, t2)
842 || !group->meth->field_mul(group, t2, t2, t0, ctx)
843 || !BN_GF2m_add(t1, t2, t1)
844 || !group->meth->field_mul(group, t2, p->X, t0, ctx)
e0033efc 845 || !group->meth->field_inv(group, t2, t2, ctx)
f45846f5
NT		 846 || !group->meth->field_mul(group, t1, t1, t2, ctx)
847 || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
848 || !BN_GF2m_add(t2, p->X, r->X)
849 || !group->meth->field_mul(group, t2, t2, t1, ctx)
850 || !BN_GF2m_add(r->Y, p->Y, t2)
851 || !BN_one(r->Z))
852 goto err;
853
854 r->Z_is_one = 1;
855
856 /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
857 BN_set_negative(r->X, 0);
858 BN_set_negative(r->Y, 0);
859
860 ret = 1;
861
862 err:
863 BN_CTX_end(ctx);
864 return ret;
865}
866
01ad66f8
NT		 867static
868int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
869 const BIGNUM *scalar, size_t num,
870 const EC_POINT *points[],
871 const BIGNUM *scalars[],
872 BN_CTX *ctx)
873{
874 int ret = 0;
875 EC_POINT *t = NULL;
876
877 /*-
878 * We limit use of the ladder only to the following cases:
879 * - r := scalar * G
880 * Fixed point mul: scalar != NULL && num == 0;
881 * - r := scalars[0] * points[0]
882 * Variable point mul: scalar == NULL && num == 1;
883 * - r := scalar * G + scalars[0] * points[0]
884 * used, e.g., in ECDSA verification: scalar != NULL && num == 1
885 *
886 * In any other case (num > 1) we use the default wNAF implementation.
887 *
888 * We also let the default implementation handle degenerate cases like group
889 * order or cofactor set to 0.
890 */
891 if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
32ab57cb 892 return ossl_ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
01ad66f8
NT		 893
894 if (scalar != NULL && num == 0)
895 /* Fixed point multiplication */
32ab57cb 896 return ossl_ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
01ad66f8
NT		 897
898 if (scalar == NULL && num == 1)
899 /* Variable point multiplication */
32ab57cb 900 return ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
01ad66f8
NT		 901
902 /*-
903 * Double point multiplication:
904 * r := scalar * G + scalars[0] * points[0]
905 */
906
907 if ((t = EC_POINT_new(group)) == NULL) {
9311d0c4 908 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
01ad66f8
NT		 909 return 0;
910 }
911
32ab57cb
SL		 912 if (!ossl_ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
913 || !ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
01ad66f8
NT		 914 || !EC_POINT_add(group, r, t, r, ctx))
915 goto err;
916
917 ret = 1;
918
919 err:
920 EC_POINT_free(t);
921 return ret;
922}
923
e0033efc
BB		 924/*-
925 * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
926 * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
927 * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
928 */
929static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
930 const BIGNUM *a, BN_CTX *ctx)
931{
932 int ret;
933
934 if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
9311d0c4 935 ERR_raise(ERR_LIB_EC, EC_R_CANNOT_INVERT);
e0033efc
BB		 936 return ret;
937}
938
f45846f5
NT		 939const EC_METHOD *EC_GF2m_simple_method(void)
940{
941 static const EC_METHOD ret = {
942 EC_FLAGS_DEFAULT_OCT,
943 NID_X9_62_characteristic_two_field,
32ab57cb
SL		 944 ossl_ec_GF2m_simple_group_init,
945 ossl_ec_GF2m_simple_group_finish,
946 ossl_ec_GF2m_simple_group_clear_finish,
947 ossl_ec_GF2m_simple_group_copy,
948 ossl_ec_GF2m_simple_group_set_curve,
949 ossl_ec_GF2m_simple_group_get_curve,
950 ossl_ec_GF2m_simple_group_get_degree,
951 ossl_ec_group_simple_order_bits,
952 ossl_ec_GF2m_simple_group_check_discriminant,
953 ossl_ec_GF2m_simple_point_init,
954 ossl_ec_GF2m_simple_point_finish,
955 ossl_ec_GF2m_simple_point_clear_finish,
956 ossl_ec_GF2m_simple_point_copy,
957 ossl_ec_GF2m_simple_point_set_to_infinity,
958 ossl_ec_GF2m_simple_point_set_affine_coordinates,
959 ossl_ec_GF2m_simple_point_get_affine_coordinates,
f45846f5
NT		 960 0, /* point_set_compressed_coordinates */
961 0, /* point2oct */
962 0, /* oct2point */
32ab57cb
SL		 963 ossl_ec_GF2m_simple_add,
964 ossl_ec_GF2m_simple_dbl,
965 ossl_ec_GF2m_simple_invert,
966 ossl_ec_GF2m_simple_is_at_infinity,
967 ossl_ec_GF2m_simple_is_on_curve,
968 ossl_ec_GF2m_simple_cmp,
969 ossl_ec_GF2m_simple_make_affine,
970 ossl_ec_GF2m_simple_points_make_affine,
01ad66f8 971 ec_GF2m_simple_points_mul,
f45846f5
NT		 972 0, /* precompute_mult */
973 0, /* have_precompute_mult */
32ab57cb
SL		 974 ossl_ec_GF2m_simple_field_mul,
975 ossl_ec_GF2m_simple_field_sqr,
976 ossl_ec_GF2m_simple_field_div,
e0033efc 977 ec_GF2m_simple_field_inv,
f45846f5
NT		 978 0, /* field_encode */
979 0, /* field_decode */
980 0, /* field_set_to_one */
32ab57cb
SL		 981 ossl_ec_key_simple_priv2oct,
982 ossl_ec_key_simple_oct2priv,
f45846f5 983 0, /* set private */
32ab57cb
SL		 984 ossl_ec_key_simple_generate_key,
985 ossl_ec_key_simple_check_key,
986 ossl_ec_key_simple_generate_public_key,
f45846f5
NT		 987 0, /* keycopy */
988 0, /* keyfinish */
32ab57cb
SL		 989 ossl_ecdh_simple_compute_key,
990 ossl_ecdsa_simple_sign_setup,
991 ossl_ecdsa_simple_sign_sig,
992 ossl_ecdsa_simple_verify_sig,
f45846f5
NT		 993 0, /* field_inverse_mod_ord */
994 0, /* blind_coordinates */
995 ec_GF2m_simple_ladder_pre,
996 ec_GF2m_simple_ladder_step,
997 ec_GF2m_simple_ladder_post
998 };
999
1000 return &ret;
1001}
1002
b3310161 1003#endif
A mirror of the official openssl repository