1*1dcdf01fSchristos /*
2*1dcdf01fSchristos * Copyright 2002-2019 The OpenSSL Project Authors. All Rights Reserved.
3*1dcdf01fSchristos * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
460662d10Schristos *
5*1dcdf01fSchristos * Licensed under the OpenSSL license (the "License"). You may not use
6*1dcdf01fSchristos * this file except in compliance with the License. You can obtain a copy
7*1dcdf01fSchristos * in the file LICENSE in the source distribution or at
8*1dcdf01fSchristos * https://www.openssl.org/source/license.html
960662d10Schristos */
1060662d10Schristos
1160662d10Schristos #include <openssl/err.h>
1260662d10Schristos
13*1dcdf01fSchristos #include "crypto/bn.h"
14*1dcdf01fSchristos #include "ec_local.h"
1560662d10Schristos
1660662d10Schristos #ifndef OPENSSL_NO_EC2M
1760662d10Schristos
1860662d10Schristos /*
1960662d10Schristos * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
2060662d10Schristos * are handled by EC_GROUP_new.
2160662d10Schristos */
ec_GF2m_simple_group_init(EC_GROUP * group)2260662d10Schristos int ec_GF2m_simple_group_init(EC_GROUP *group)
2360662d10Schristos {
24*1dcdf01fSchristos group->field = BN_new();
25*1dcdf01fSchristos group->a = BN_new();
26*1dcdf01fSchristos group->b = BN_new();
27*1dcdf01fSchristos
28*1dcdf01fSchristos if (group->field == NULL || group->a == NULL || group->b == NULL) {
29*1dcdf01fSchristos BN_free(group->field);
30*1dcdf01fSchristos BN_free(group->a);
31*1dcdf01fSchristos BN_free(group->b);
32*1dcdf01fSchristos return 0;
33*1dcdf01fSchristos }
3460662d10Schristos return 1;
3560662d10Schristos }
3660662d10Schristos
3760662d10Schristos /*
3860662d10Schristos * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
3960662d10Schristos * handled by EC_GROUP_free.
4060662d10Schristos */
ec_GF2m_simple_group_finish(EC_GROUP * group)4160662d10Schristos void ec_GF2m_simple_group_finish(EC_GROUP *group)
4260662d10Schristos {
43*1dcdf01fSchristos BN_free(group->field);
44*1dcdf01fSchristos BN_free(group->a);
45*1dcdf01fSchristos BN_free(group->b);
4660662d10Schristos }
4760662d10Schristos
4860662d10Schristos /*
4960662d10Schristos * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
5060662d10Schristos * members are handled by EC_GROUP_clear_free.
5160662d10Schristos */
ec_GF2m_simple_group_clear_finish(EC_GROUP * group)5260662d10Schristos void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
5360662d10Schristos {
54*1dcdf01fSchristos BN_clear_free(group->field);
55*1dcdf01fSchristos BN_clear_free(group->a);
56*1dcdf01fSchristos BN_clear_free(group->b);
5760662d10Schristos group->poly[0] = 0;
5860662d10Schristos group->poly[1] = 0;
5960662d10Schristos group->poly[2] = 0;
6060662d10Schristos group->poly[3] = 0;
6160662d10Schristos group->poly[4] = 0;
6260662d10Schristos group->poly[5] = -1;
6360662d10Schristos }
6460662d10Schristos
6560662d10Schristos /*
6660662d10Schristos * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
6760662d10Schristos * handled by EC_GROUP_copy.
6860662d10Schristos */
ec_GF2m_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)6960662d10Schristos int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
7060662d10Schristos {
71*1dcdf01fSchristos if (!BN_copy(dest->field, src->field))
7260662d10Schristos return 0;
73*1dcdf01fSchristos if (!BN_copy(dest->a, src->a))
7460662d10Schristos return 0;
75*1dcdf01fSchristos if (!BN_copy(dest->b, src->b))
7660662d10Schristos return 0;
7760662d10Schristos dest->poly[0] = src->poly[0];
7860662d10Schristos dest->poly[1] = src->poly[1];
7960662d10Schristos dest->poly[2] = src->poly[2];
8060662d10Schristos dest->poly[3] = src->poly[3];
8160662d10Schristos dest->poly[4] = src->poly[4];
8260662d10Schristos dest->poly[5] = src->poly[5];
83*1dcdf01fSchristos if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
84*1dcdf01fSchristos NULL)
8560662d10Schristos return 0;
86*1dcdf01fSchristos if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
87*1dcdf01fSchristos NULL)
8860662d10Schristos return 0;
89*1dcdf01fSchristos bn_set_all_zero(dest->a);
90*1dcdf01fSchristos bn_set_all_zero(dest->b);
9160662d10Schristos return 1;
9260662d10Schristos }
9360662d10Schristos
9460662d10Schristos /* Set the curve parameters of an EC_GROUP structure. */
ec_GF2m_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)9560662d10Schristos int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
9660662d10Schristos const BIGNUM *p, const BIGNUM *a,
9760662d10Schristos const BIGNUM *b, BN_CTX *ctx)
9860662d10Schristos {
9960662d10Schristos int ret = 0, i;
10060662d10Schristos
10160662d10Schristos /* group->field */
102*1dcdf01fSchristos if (!BN_copy(group->field, p))
10360662d10Schristos goto err;
104*1dcdf01fSchristos i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
10560662d10Schristos if ((i != 5) && (i != 3)) {
10660662d10Schristos ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
10760662d10Schristos goto err;
10860662d10Schristos }
10960662d10Schristos
11060662d10Schristos /* group->a */
111*1dcdf01fSchristos if (!BN_GF2m_mod_arr(group->a, a, group->poly))
11260662d10Schristos goto err;
113*1dcdf01fSchristos if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
11460662d10Schristos == NULL)
11560662d10Schristos goto err;
116*1dcdf01fSchristos bn_set_all_zero(group->a);
11760662d10Schristos
11860662d10Schristos /* group->b */
119*1dcdf01fSchristos if (!BN_GF2m_mod_arr(group->b, b, group->poly))
12060662d10Schristos goto err;
121*1dcdf01fSchristos if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
12260662d10Schristos == NULL)
12360662d10Schristos goto err;
124*1dcdf01fSchristos bn_set_all_zero(group->b);
12560662d10Schristos
12660662d10Schristos ret = 1;
12760662d10Schristos err:
12860662d10Schristos return ret;
12960662d10Schristos }
13060662d10Schristos
13160662d10Schristos /*
13260662d10Schristos * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
13360662d10Schristos * then there values will not be set but the method will return with success.
13460662d10Schristos */
ec_GF2m_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)13560662d10Schristos int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
13660662d10Schristos BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
13760662d10Schristos {
13860662d10Schristos int ret = 0;
13960662d10Schristos
14060662d10Schristos if (p != NULL) {
141*1dcdf01fSchristos if (!BN_copy(p, group->field))
14260662d10Schristos return 0;
14360662d10Schristos }
14460662d10Schristos
14560662d10Schristos if (a != NULL) {
146*1dcdf01fSchristos if (!BN_copy(a, group->a))
14760662d10Schristos goto err;
14860662d10Schristos }
14960662d10Schristos
15060662d10Schristos if (b != NULL) {
151*1dcdf01fSchristos if (!BN_copy(b, group->b))
15260662d10Schristos goto err;
15360662d10Schristos }
15460662d10Schristos
15560662d10Schristos ret = 1;
15660662d10Schristos
15760662d10Schristos err:
15860662d10Schristos return ret;
15960662d10Schristos }
16060662d10Schristos
16160662d10Schristos /*
16260662d10Schristos * Gets the degree of the field. For a curve over GF(2^m) this is the value
16360662d10Schristos * m.
16460662d10Schristos */
ec_GF2m_simple_group_get_degree(const EC_GROUP * group)16560662d10Schristos int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
16660662d10Schristos {
167*1dcdf01fSchristos return BN_num_bits(group->field) - 1;
16860662d10Schristos }
16960662d10Schristos
17060662d10Schristos /*
17160662d10Schristos * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
17260662d10Schristos * elliptic curve <=> b != 0 (mod p)
17360662d10Schristos */
ec_GF2m_simple_group_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)17460662d10Schristos int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
17560662d10Schristos BN_CTX *ctx)
17660662d10Schristos {
17760662d10Schristos int ret = 0;
17860662d10Schristos BIGNUM *b;
17960662d10Schristos BN_CTX *new_ctx = NULL;
18060662d10Schristos
18160662d10Schristos if (ctx == NULL) {
18260662d10Schristos ctx = new_ctx = BN_CTX_new();
18360662d10Schristos if (ctx == NULL) {
18460662d10Schristos ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT,
18560662d10Schristos ERR_R_MALLOC_FAILURE);
18660662d10Schristos goto err;
18760662d10Schristos }
18860662d10Schristos }
18960662d10Schristos BN_CTX_start(ctx);
19060662d10Schristos b = BN_CTX_get(ctx);
19160662d10Schristos if (b == NULL)
19260662d10Schristos goto err;
19360662d10Schristos
194*1dcdf01fSchristos if (!BN_GF2m_mod_arr(b, group->b, group->poly))
19560662d10Schristos goto err;
19660662d10Schristos
19760662d10Schristos /*
19860662d10Schristos * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
19960662d10Schristos * curve <=> b != 0 (mod p)
20060662d10Schristos */
20160662d10Schristos if (BN_is_zero(b))
20260662d10Schristos goto err;
20360662d10Schristos
20460662d10Schristos ret = 1;
20560662d10Schristos
20660662d10Schristos err:
20760662d10Schristos BN_CTX_end(ctx);
20860662d10Schristos BN_CTX_free(new_ctx);
20960662d10Schristos return ret;
21060662d10Schristos }
21160662d10Schristos
21260662d10Schristos /* Initializes an EC_POINT. */
ec_GF2m_simple_point_init(EC_POINT * point)21360662d10Schristos int ec_GF2m_simple_point_init(EC_POINT *point)
21460662d10Schristos {
215*1dcdf01fSchristos point->X = BN_new();
216*1dcdf01fSchristos point->Y = BN_new();
217*1dcdf01fSchristos point->Z = BN_new();
218*1dcdf01fSchristos
219*1dcdf01fSchristos if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
220*1dcdf01fSchristos BN_free(point->X);
221*1dcdf01fSchristos BN_free(point->Y);
222*1dcdf01fSchristos BN_free(point->Z);
223*1dcdf01fSchristos return 0;
224*1dcdf01fSchristos }
22560662d10Schristos return 1;
22660662d10Schristos }
22760662d10Schristos
22860662d10Schristos /* Frees an EC_POINT. */
ec_GF2m_simple_point_finish(EC_POINT * point)22960662d10Schristos void ec_GF2m_simple_point_finish(EC_POINT *point)
23060662d10Schristos {
231*1dcdf01fSchristos BN_free(point->X);
232*1dcdf01fSchristos BN_free(point->Y);
233*1dcdf01fSchristos BN_free(point->Z);
23460662d10Schristos }
23560662d10Schristos
23660662d10Schristos /* Clears and frees an EC_POINT. */
ec_GF2m_simple_point_clear_finish(EC_POINT * point)23760662d10Schristos void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
23860662d10Schristos {
239*1dcdf01fSchristos BN_clear_free(point->X);
240*1dcdf01fSchristos BN_clear_free(point->Y);
241*1dcdf01fSchristos BN_clear_free(point->Z);
24260662d10Schristos point->Z_is_one = 0;
24360662d10Schristos }
24460662d10Schristos
24560662d10Schristos /*
24660662d10Schristos * Copy the contents of one EC_POINT into another. Assumes dest is
24760662d10Schristos * initialized.
24860662d10Schristos */
ec_GF2m_simple_point_copy(EC_POINT * dest,const EC_POINT * src)24960662d10Schristos int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
25060662d10Schristos {
251*1dcdf01fSchristos if (!BN_copy(dest->X, src->X))
25260662d10Schristos return 0;
253*1dcdf01fSchristos if (!BN_copy(dest->Y, src->Y))
25460662d10Schristos return 0;
255*1dcdf01fSchristos if (!BN_copy(dest->Z, src->Z))
25660662d10Schristos return 0;
25760662d10Schristos dest->Z_is_one = src->Z_is_one;
258*1dcdf01fSchristos dest->curve_name = src->curve_name;
25960662d10Schristos
26060662d10Schristos return 1;
26160662d10Schristos }
26260662d10Schristos
26360662d10Schristos /*
26460662d10Schristos * Set an EC_POINT to the point at infinity. A point at infinity is
26560662d10Schristos * represented by having Z=0.
26660662d10Schristos */
ec_GF2m_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)26760662d10Schristos int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
26860662d10Schristos EC_POINT *point)
26960662d10Schristos {
27060662d10Schristos point->Z_is_one = 0;
271*1dcdf01fSchristos BN_zero(point->Z);
27260662d10Schristos return 1;
27360662d10Schristos }
27460662d10Schristos
27560662d10Schristos /*
27660662d10Schristos * Set the coordinates of an EC_POINT using affine coordinates. Note that
27760662d10Schristos * the simple implementation only uses affine coordinates.
27860662d10Schristos */
ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)27960662d10Schristos int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
28060662d10Schristos EC_POINT *point,
28160662d10Schristos const BIGNUM *x,
28260662d10Schristos const BIGNUM *y, BN_CTX *ctx)
28360662d10Schristos {
28460662d10Schristos int ret = 0;
28560662d10Schristos if (x == NULL || y == NULL) {
28660662d10Schristos ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
28760662d10Schristos ERR_R_PASSED_NULL_PARAMETER);
28860662d10Schristos return 0;
28960662d10Schristos }
29060662d10Schristos
291*1dcdf01fSchristos if (!BN_copy(point->X, x))
29260662d10Schristos goto err;
293*1dcdf01fSchristos BN_set_negative(point->X, 0);
294*1dcdf01fSchristos if (!BN_copy(point->Y, y))
29560662d10Schristos goto err;
296*1dcdf01fSchristos BN_set_negative(point->Y, 0);
297*1dcdf01fSchristos if (!BN_copy(point->Z, BN_value_one()))
29860662d10Schristos goto err;
299*1dcdf01fSchristos BN_set_negative(point->Z, 0);
30060662d10Schristos point->Z_is_one = 1;
30160662d10Schristos ret = 1;
30260662d10Schristos
30360662d10Schristos err:
30460662d10Schristos return ret;
30560662d10Schristos }
30660662d10Schristos
30760662d10Schristos /*
30860662d10Schristos * Gets the affine coordinates of an EC_POINT. Note that the simple
30960662d10Schristos * implementation only uses affine coordinates.
31060662d10Schristos */
ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)31160662d10Schristos int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
31260662d10Schristos const EC_POINT *point,
31360662d10Schristos BIGNUM *x, BIGNUM *y,
31460662d10Schristos BN_CTX *ctx)
31560662d10Schristos {
31660662d10Schristos int ret = 0;
31760662d10Schristos
31860662d10Schristos if (EC_POINT_is_at_infinity(group, point)) {
31960662d10Schristos ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
32060662d10Schristos EC_R_POINT_AT_INFINITY);
32160662d10Schristos return 0;
32260662d10Schristos }
32360662d10Schristos
324*1dcdf01fSchristos if (BN_cmp(point->Z, BN_value_one())) {
32560662d10Schristos ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
32660662d10Schristos ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
32760662d10Schristos return 0;
32860662d10Schristos }
32960662d10Schristos if (x != NULL) {
330*1dcdf01fSchristos if (!BN_copy(x, point->X))
33160662d10Schristos goto err;
33260662d10Schristos BN_set_negative(x, 0);
33360662d10Schristos }
33460662d10Schristos if (y != NULL) {
335*1dcdf01fSchristos if (!BN_copy(y, point->Y))
33660662d10Schristos goto err;
33760662d10Schristos BN_set_negative(y, 0);
33860662d10Schristos }
33960662d10Schristos ret = 1;
34060662d10Schristos
34160662d10Schristos err:
34260662d10Schristos return ret;
34360662d10Schristos }
34460662d10Schristos
34560662d10Schristos /*
34660662d10Schristos * Computes a + b and stores the result in r. r could be a or b, a could be
34760662d10Schristos * b. Uses algorithm A.10.2 of IEEE P1363.
34860662d10Schristos */
ec_GF2m_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)34960662d10Schristos int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
35060662d10Schristos const EC_POINT *b, BN_CTX *ctx)
35160662d10Schristos {
35260662d10Schristos BN_CTX *new_ctx = NULL;
35360662d10Schristos BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
35460662d10Schristos int ret = 0;
35560662d10Schristos
35660662d10Schristos if (EC_POINT_is_at_infinity(group, a)) {
35760662d10Schristos if (!EC_POINT_copy(r, b))
35860662d10Schristos return 0;
35960662d10Schristos return 1;
36060662d10Schristos }
36160662d10Schristos
36260662d10Schristos if (EC_POINT_is_at_infinity(group, b)) {
36360662d10Schristos if (!EC_POINT_copy(r, a))
36460662d10Schristos return 0;
36560662d10Schristos return 1;
36660662d10Schristos }
36760662d10Schristos
36860662d10Schristos if (ctx == NULL) {
36960662d10Schristos ctx = new_ctx = BN_CTX_new();
37060662d10Schristos if (ctx == NULL)
37160662d10Schristos return 0;
37260662d10Schristos }
37360662d10Schristos
37460662d10Schristos BN_CTX_start(ctx);
37560662d10Schristos x0 = BN_CTX_get(ctx);
37660662d10Schristos y0 = BN_CTX_get(ctx);
37760662d10Schristos x1 = BN_CTX_get(ctx);
37860662d10Schristos y1 = BN_CTX_get(ctx);
37960662d10Schristos x2 = BN_CTX_get(ctx);
38060662d10Schristos y2 = BN_CTX_get(ctx);
38160662d10Schristos s = BN_CTX_get(ctx);
38260662d10Schristos t = BN_CTX_get(ctx);
38360662d10Schristos if (t == NULL)
38460662d10Schristos goto err;
38560662d10Schristos
38660662d10Schristos if (a->Z_is_one) {
387*1dcdf01fSchristos if (!BN_copy(x0, a->X))
38860662d10Schristos goto err;
389*1dcdf01fSchristos if (!BN_copy(y0, a->Y))
39060662d10Schristos goto err;
39160662d10Schristos } else {
392*1dcdf01fSchristos if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
39360662d10Schristos goto err;
39460662d10Schristos }
39560662d10Schristos if (b->Z_is_one) {
396*1dcdf01fSchristos if (!BN_copy(x1, b->X))
39760662d10Schristos goto err;
398*1dcdf01fSchristos if (!BN_copy(y1, b->Y))
39960662d10Schristos goto err;
40060662d10Schristos } else {
401*1dcdf01fSchristos if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
40260662d10Schristos goto err;
40360662d10Schristos }
40460662d10Schristos
40560662d10Schristos if (BN_GF2m_cmp(x0, x1)) {
40660662d10Schristos if (!BN_GF2m_add(t, x0, x1))
40760662d10Schristos goto err;
40860662d10Schristos if (!BN_GF2m_add(s, y0, y1))
40960662d10Schristos goto err;
41060662d10Schristos if (!group->meth->field_div(group, s, s, t, ctx))
41160662d10Schristos goto err;
41260662d10Schristos if (!group->meth->field_sqr(group, x2, s, ctx))
41360662d10Schristos goto err;
414*1dcdf01fSchristos if (!BN_GF2m_add(x2, x2, group->a))
41560662d10Schristos goto err;
41660662d10Schristos if (!BN_GF2m_add(x2, x2, s))
41760662d10Schristos goto err;
41860662d10Schristos if (!BN_GF2m_add(x2, x2, t))
41960662d10Schristos goto err;
42060662d10Schristos } else {
42160662d10Schristos if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
42260662d10Schristos if (!EC_POINT_set_to_infinity(group, r))
42360662d10Schristos goto err;
42460662d10Schristos ret = 1;
42560662d10Schristos goto err;
42660662d10Schristos }
42760662d10Schristos if (!group->meth->field_div(group, s, y1, x1, ctx))
42860662d10Schristos goto err;
42960662d10Schristos if (!BN_GF2m_add(s, s, x1))
43060662d10Schristos goto err;
43160662d10Schristos
43260662d10Schristos if (!group->meth->field_sqr(group, x2, s, ctx))
43360662d10Schristos goto err;
43460662d10Schristos if (!BN_GF2m_add(x2, x2, s))
43560662d10Schristos goto err;
436*1dcdf01fSchristos if (!BN_GF2m_add(x2, x2, group->a))
43760662d10Schristos goto err;
43860662d10Schristos }
43960662d10Schristos
44060662d10Schristos if (!BN_GF2m_add(y2, x1, x2))
44160662d10Schristos goto err;
44260662d10Schristos if (!group->meth->field_mul(group, y2, y2, s, ctx))
44360662d10Schristos goto err;
44460662d10Schristos if (!BN_GF2m_add(y2, y2, x2))
44560662d10Schristos goto err;
44660662d10Schristos if (!BN_GF2m_add(y2, y2, y1))
44760662d10Schristos goto err;
44860662d10Schristos
449*1dcdf01fSchristos if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
45060662d10Schristos goto err;
45160662d10Schristos
45260662d10Schristos ret = 1;
45360662d10Schristos
45460662d10Schristos err:
45560662d10Schristos BN_CTX_end(ctx);
45660662d10Schristos BN_CTX_free(new_ctx);
45760662d10Schristos return ret;
45860662d10Schristos }
45960662d10Schristos
46060662d10Schristos /*
46160662d10Schristos * Computes 2 * a and stores the result in r. r could be a. Uses algorithm
46260662d10Schristos * A.10.2 of IEEE P1363.
46360662d10Schristos */
ec_GF2m_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)46460662d10Schristos int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
46560662d10Schristos BN_CTX *ctx)
46660662d10Schristos {
46760662d10Schristos return ec_GF2m_simple_add(group, r, a, a, ctx);
46860662d10Schristos }
46960662d10Schristos
ec_GF2m_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)47060662d10Schristos int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
47160662d10Schristos {
472*1dcdf01fSchristos if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
47360662d10Schristos /* point is its own inverse */
47460662d10Schristos return 1;
47560662d10Schristos
47660662d10Schristos if (!EC_POINT_make_affine(group, point, ctx))
47760662d10Schristos return 0;
478*1dcdf01fSchristos return BN_GF2m_add(point->Y, point->X, point->Y);
47960662d10Schristos }
48060662d10Schristos
48160662d10Schristos /* Indicates whether the given point is the point at infinity. */
ec_GF2m_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)48260662d10Schristos int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
48360662d10Schristos const EC_POINT *point)
48460662d10Schristos {
485*1dcdf01fSchristos return BN_is_zero(point->Z);
48660662d10Schristos }
48760662d10Schristos
48860662d10Schristos /*-
48960662d10Schristos * Determines whether the given EC_POINT is an actual point on the curve defined
49060662d10Schristos * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
49160662d10Schristos * y^2 + x*y = x^3 + a*x^2 + b.
49260662d10Schristos */
ec_GF2m_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)49360662d10Schristos int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
49460662d10Schristos BN_CTX *ctx)
49560662d10Schristos {
49660662d10Schristos int ret = -1;
49760662d10Schristos BN_CTX *new_ctx = NULL;
49860662d10Schristos BIGNUM *lh, *y2;
49960662d10Schristos int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
50060662d10Schristos const BIGNUM *, BN_CTX *);
50160662d10Schristos int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
50260662d10Schristos
50360662d10Schristos if (EC_POINT_is_at_infinity(group, point))
50460662d10Schristos return 1;
50560662d10Schristos
50660662d10Schristos field_mul = group->meth->field_mul;
50760662d10Schristos field_sqr = group->meth->field_sqr;
50860662d10Schristos
50960662d10Schristos /* only support affine coordinates */
51060662d10Schristos if (!point->Z_is_one)
51160662d10Schristos return -1;
51260662d10Schristos
51360662d10Schristos if (ctx == NULL) {
51460662d10Schristos ctx = new_ctx = BN_CTX_new();
51560662d10Schristos if (ctx == NULL)
51660662d10Schristos return -1;
51760662d10Schristos }
51860662d10Schristos
51960662d10Schristos BN_CTX_start(ctx);
52060662d10Schristos y2 = BN_CTX_get(ctx);
52160662d10Schristos lh = BN_CTX_get(ctx);
52260662d10Schristos if (lh == NULL)
52360662d10Schristos goto err;
52460662d10Schristos
52560662d10Schristos /*-
52660662d10Schristos * We have a curve defined by a Weierstrass equation
52760662d10Schristos * y^2 + x*y = x^3 + a*x^2 + b.
52860662d10Schristos * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
52960662d10Schristos * <=> ((x + a) * x + y ) * x + b + y^2 = 0
53060662d10Schristos */
531*1dcdf01fSchristos if (!BN_GF2m_add(lh, point->X, group->a))
53260662d10Schristos goto err;
533*1dcdf01fSchristos if (!field_mul(group, lh, lh, point->X, ctx))
53460662d10Schristos goto err;
535*1dcdf01fSchristos if (!BN_GF2m_add(lh, lh, point->Y))
53660662d10Schristos goto err;
537*1dcdf01fSchristos if (!field_mul(group, lh, lh, point->X, ctx))
53860662d10Schristos goto err;
539*1dcdf01fSchristos if (!BN_GF2m_add(lh, lh, group->b))
54060662d10Schristos goto err;
541*1dcdf01fSchristos if (!field_sqr(group, y2, point->Y, ctx))
54260662d10Schristos goto err;
54360662d10Schristos if (!BN_GF2m_add(lh, lh, y2))
54460662d10Schristos goto err;
54560662d10Schristos ret = BN_is_zero(lh);
546*1dcdf01fSchristos
54760662d10Schristos err:
54860662d10Schristos BN_CTX_end(ctx);
54960662d10Schristos BN_CTX_free(new_ctx);
55060662d10Schristos return ret;
55160662d10Schristos }
55260662d10Schristos
55360662d10Schristos /*-
55460662d10Schristos * Indicates whether two points are equal.
55560662d10Schristos * Return values:
55660662d10Schristos * -1 error
55760662d10Schristos * 0 equal (in affine coordinates)
55860662d10Schristos * 1 not equal
55960662d10Schristos */
ec_GF2m_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)56060662d10Schristos int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
56160662d10Schristos const EC_POINT *b, BN_CTX *ctx)
56260662d10Schristos {
56360662d10Schristos BIGNUM *aX, *aY, *bX, *bY;
56460662d10Schristos BN_CTX *new_ctx = NULL;
56560662d10Schristos int ret = -1;
56660662d10Schristos
56760662d10Schristos if (EC_POINT_is_at_infinity(group, a)) {
56860662d10Schristos return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
56960662d10Schristos }
57060662d10Schristos
57160662d10Schristos if (EC_POINT_is_at_infinity(group, b))
57260662d10Schristos return 1;
57360662d10Schristos
57460662d10Schristos if (a->Z_is_one && b->Z_is_one) {
575*1dcdf01fSchristos return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
57660662d10Schristos }
57760662d10Schristos
57860662d10Schristos if (ctx == NULL) {
57960662d10Schristos ctx = new_ctx = BN_CTX_new();
58060662d10Schristos if (ctx == NULL)
58160662d10Schristos return -1;
58260662d10Schristos }
58360662d10Schristos
58460662d10Schristos BN_CTX_start(ctx);
58560662d10Schristos aX = BN_CTX_get(ctx);
58660662d10Schristos aY = BN_CTX_get(ctx);
58760662d10Schristos bX = BN_CTX_get(ctx);
58860662d10Schristos bY = BN_CTX_get(ctx);
58960662d10Schristos if (bY == NULL)
59060662d10Schristos goto err;
59160662d10Schristos
592*1dcdf01fSchristos if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
59360662d10Schristos goto err;
594*1dcdf01fSchristos if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
59560662d10Schristos goto err;
59660662d10Schristos ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
59760662d10Schristos
59860662d10Schristos err:
59960662d10Schristos BN_CTX_end(ctx);
60060662d10Schristos BN_CTX_free(new_ctx);
60160662d10Schristos return ret;
60260662d10Schristos }
60360662d10Schristos
60460662d10Schristos /* Forces the given EC_POINT to internally use affine coordinates. */
ec_GF2m_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)60560662d10Schristos int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
60660662d10Schristos BN_CTX *ctx)
60760662d10Schristos {
60860662d10Schristos BN_CTX *new_ctx = NULL;
60960662d10Schristos BIGNUM *x, *y;
61060662d10Schristos int ret = 0;
61160662d10Schristos
61260662d10Schristos if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
61360662d10Schristos return 1;
61460662d10Schristos
61560662d10Schristos if (ctx == NULL) {
61660662d10Schristos ctx = new_ctx = BN_CTX_new();
61760662d10Schristos if (ctx == NULL)
61860662d10Schristos return 0;
61960662d10Schristos }
62060662d10Schristos
62160662d10Schristos BN_CTX_start(ctx);
62260662d10Schristos x = BN_CTX_get(ctx);
62360662d10Schristos y = BN_CTX_get(ctx);
62460662d10Schristos if (y == NULL)
62560662d10Schristos goto err;
62660662d10Schristos
627*1dcdf01fSchristos if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
62860662d10Schristos goto err;
629*1dcdf01fSchristos if (!BN_copy(point->X, x))
63060662d10Schristos goto err;
631*1dcdf01fSchristos if (!BN_copy(point->Y, y))
63260662d10Schristos goto err;
633*1dcdf01fSchristos if (!BN_one(point->Z))
63460662d10Schristos goto err;
63560662d10Schristos point->Z_is_one = 1;
63660662d10Schristos
63760662d10Schristos ret = 1;
63860662d10Schristos
63960662d10Schristos err:
64060662d10Schristos BN_CTX_end(ctx);
64160662d10Schristos BN_CTX_free(new_ctx);
64260662d10Schristos return ret;
64360662d10Schristos }
64460662d10Schristos
64560662d10Schristos /*
64660662d10Schristos * Forces each of the EC_POINTs in the given array to use affine coordinates.
64760662d10Schristos */
ec_GF2m_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)64860662d10Schristos int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
64960662d10Schristos EC_POINT *points[], BN_CTX *ctx)
65060662d10Schristos {
65160662d10Schristos size_t i;
65260662d10Schristos
65360662d10Schristos for (i = 0; i < num; i++) {
65460662d10Schristos if (!group->meth->make_affine(group, points[i], ctx))
65560662d10Schristos return 0;
65660662d10Schristos }
65760662d10Schristos
65860662d10Schristos return 1;
65960662d10Schristos }
66060662d10Schristos
66160662d10Schristos /* Wrapper to simple binary polynomial field multiplication implementation. */
ec_GF2m_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)66260662d10Schristos int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
66360662d10Schristos const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
66460662d10Schristos {
66560662d10Schristos return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
66660662d10Schristos }
66760662d10Schristos
66860662d10Schristos /* Wrapper to simple binary polynomial field squaring implementation. */
ec_GF2m_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)66960662d10Schristos int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
67060662d10Schristos const BIGNUM *a, BN_CTX *ctx)
67160662d10Schristos {
67260662d10Schristos return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
67360662d10Schristos }
67460662d10Schristos
67560662d10Schristos /* Wrapper to simple binary polynomial field division implementation. */
ec_GF2m_simple_field_div(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)67660662d10Schristos int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
67760662d10Schristos const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
67860662d10Schristos {
679*1dcdf01fSchristos return BN_GF2m_mod_div(r, a, b, group->field, ctx);
680*1dcdf01fSchristos }
681*1dcdf01fSchristos
682*1dcdf01fSchristos /*-
683*1dcdf01fSchristos * Lopez-Dahab ladder, pre step.
684*1dcdf01fSchristos * See e.g. "Guide to ECC" Alg 3.40.
685*1dcdf01fSchristos * Modified to blind s and r independently.
686*1dcdf01fSchristos * s:= p, r := 2p
687*1dcdf01fSchristos */
688*1dcdf01fSchristos static
ec_GF2m_simple_ladder_pre(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)689*1dcdf01fSchristos int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
690*1dcdf01fSchristos EC_POINT *r, EC_POINT *s,
691*1dcdf01fSchristos EC_POINT *p, BN_CTX *ctx)
692*1dcdf01fSchristos {
693*1dcdf01fSchristos /* if p is not affine, something is wrong */
694*1dcdf01fSchristos if (p->Z_is_one == 0)
695*1dcdf01fSchristos return 0;
696*1dcdf01fSchristos
697*1dcdf01fSchristos /* s blinding: make sure lambda (s->Z here) is not zero */
698*1dcdf01fSchristos do {
699*1dcdf01fSchristos if (!BN_priv_rand(s->Z, BN_num_bits(group->field) - 1,
700*1dcdf01fSchristos BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
701*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
702*1dcdf01fSchristos return 0;
703*1dcdf01fSchristos }
704*1dcdf01fSchristos } while (BN_is_zero(s->Z));
705*1dcdf01fSchristos
706*1dcdf01fSchristos /* if field_encode defined convert between representations */
707*1dcdf01fSchristos if ((group->meth->field_encode != NULL
708*1dcdf01fSchristos && !group->meth->field_encode(group, s->Z, s->Z, ctx))
709*1dcdf01fSchristos || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
710*1dcdf01fSchristos return 0;
711*1dcdf01fSchristos
712*1dcdf01fSchristos /* r blinding: make sure lambda (r->Y here for storage) is not zero */
713*1dcdf01fSchristos do {
714*1dcdf01fSchristos if (!BN_priv_rand(r->Y, BN_num_bits(group->field) - 1,
715*1dcdf01fSchristos BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
716*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
717*1dcdf01fSchristos return 0;
718*1dcdf01fSchristos }
719*1dcdf01fSchristos } while (BN_is_zero(r->Y));
720*1dcdf01fSchristos
721*1dcdf01fSchristos if ((group->meth->field_encode != NULL
722*1dcdf01fSchristos && !group->meth->field_encode(group, r->Y, r->Y, ctx))
723*1dcdf01fSchristos || !group->meth->field_sqr(group, r->Z, p->X, ctx)
724*1dcdf01fSchristos || !group->meth->field_sqr(group, r->X, r->Z, ctx)
725*1dcdf01fSchristos || !BN_GF2m_add(r->X, r->X, group->b)
726*1dcdf01fSchristos || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
727*1dcdf01fSchristos || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
728*1dcdf01fSchristos return 0;
729*1dcdf01fSchristos
730*1dcdf01fSchristos s->Z_is_one = 0;
731*1dcdf01fSchristos r->Z_is_one = 0;
732*1dcdf01fSchristos
733*1dcdf01fSchristos return 1;
734*1dcdf01fSchristos }
735*1dcdf01fSchristos
736*1dcdf01fSchristos /*-
737*1dcdf01fSchristos * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
738*1dcdf01fSchristos * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
739*1dcdf01fSchristos * s := r + s, r := 2r
740*1dcdf01fSchristos */
741*1dcdf01fSchristos static
ec_GF2m_simple_ladder_step(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)742*1dcdf01fSchristos int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
743*1dcdf01fSchristos EC_POINT *r, EC_POINT *s,
744*1dcdf01fSchristos EC_POINT *p, BN_CTX *ctx)
745*1dcdf01fSchristos {
746*1dcdf01fSchristos if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
747*1dcdf01fSchristos || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
748*1dcdf01fSchristos || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
749*1dcdf01fSchristos || !group->meth->field_sqr(group, r->Z, r->X, ctx)
750*1dcdf01fSchristos || !BN_GF2m_add(s->Z, r->Y, s->X)
751*1dcdf01fSchristos || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
752*1dcdf01fSchristos || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
753*1dcdf01fSchristos || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
754*1dcdf01fSchristos || !BN_GF2m_add(s->X, s->X, r->Y)
755*1dcdf01fSchristos || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
756*1dcdf01fSchristos || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
757*1dcdf01fSchristos || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
758*1dcdf01fSchristos || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
759*1dcdf01fSchristos || !BN_GF2m_add(r->X, r->Y, s->Y))
760*1dcdf01fSchristos return 0;
761*1dcdf01fSchristos
762*1dcdf01fSchristos return 1;
763*1dcdf01fSchristos }
764*1dcdf01fSchristos
765*1dcdf01fSchristos /*-
766*1dcdf01fSchristos * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
767*1dcdf01fSchristos * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
768*1dcdf01fSchristos * without Precomputation" (Lopez and Dahab, CHES 1999),
769*1dcdf01fSchristos * Appendix Alg Mxy.
770*1dcdf01fSchristos */
771*1dcdf01fSchristos static
ec_GF2m_simple_ladder_post(const EC_GROUP * group,EC_POINT * r,EC_POINT * s,EC_POINT * p,BN_CTX * ctx)772*1dcdf01fSchristos int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
773*1dcdf01fSchristos EC_POINT *r, EC_POINT *s,
774*1dcdf01fSchristos EC_POINT *p, BN_CTX *ctx)
775*1dcdf01fSchristos {
776*1dcdf01fSchristos int ret = 0;
777*1dcdf01fSchristos BIGNUM *t0, *t1, *t2 = NULL;
778*1dcdf01fSchristos
779*1dcdf01fSchristos if (BN_is_zero(r->Z))
780*1dcdf01fSchristos return EC_POINT_set_to_infinity(group, r);
781*1dcdf01fSchristos
782*1dcdf01fSchristos if (BN_is_zero(s->Z)) {
783*1dcdf01fSchristos if (!EC_POINT_copy(r, p)
784*1dcdf01fSchristos || !EC_POINT_invert(group, r, ctx)) {
785*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
786*1dcdf01fSchristos return 0;
787*1dcdf01fSchristos }
788*1dcdf01fSchristos return 1;
789*1dcdf01fSchristos }
790*1dcdf01fSchristos
791*1dcdf01fSchristos BN_CTX_start(ctx);
792*1dcdf01fSchristos t0 = BN_CTX_get(ctx);
793*1dcdf01fSchristos t1 = BN_CTX_get(ctx);
794*1dcdf01fSchristos t2 = BN_CTX_get(ctx);
795*1dcdf01fSchristos if (t2 == NULL) {
796*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
797*1dcdf01fSchristos goto err;
798*1dcdf01fSchristos }
799*1dcdf01fSchristos
800*1dcdf01fSchristos if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
801*1dcdf01fSchristos || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
802*1dcdf01fSchristos || !BN_GF2m_add(t1, r->X, t1)
803*1dcdf01fSchristos || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
804*1dcdf01fSchristos || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
805*1dcdf01fSchristos || !BN_GF2m_add(t2, t2, s->X)
806*1dcdf01fSchristos || !group->meth->field_mul(group, t1, t1, t2, ctx)
807*1dcdf01fSchristos || !group->meth->field_sqr(group, t2, p->X, ctx)
808*1dcdf01fSchristos || !BN_GF2m_add(t2, p->Y, t2)
809*1dcdf01fSchristos || !group->meth->field_mul(group, t2, t2, t0, ctx)
810*1dcdf01fSchristos || !BN_GF2m_add(t1, t2, t1)
811*1dcdf01fSchristos || !group->meth->field_mul(group, t2, p->X, t0, ctx)
812*1dcdf01fSchristos || !group->meth->field_inv(group, t2, t2, ctx)
813*1dcdf01fSchristos || !group->meth->field_mul(group, t1, t1, t2, ctx)
814*1dcdf01fSchristos || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
815*1dcdf01fSchristos || !BN_GF2m_add(t2, p->X, r->X)
816*1dcdf01fSchristos || !group->meth->field_mul(group, t2, t2, t1, ctx)
817*1dcdf01fSchristos || !BN_GF2m_add(r->Y, p->Y, t2)
818*1dcdf01fSchristos || !BN_one(r->Z))
819*1dcdf01fSchristos goto err;
820*1dcdf01fSchristos
821*1dcdf01fSchristos r->Z_is_one = 1;
822*1dcdf01fSchristos
823*1dcdf01fSchristos /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
824*1dcdf01fSchristos BN_set_negative(r->X, 0);
825*1dcdf01fSchristos BN_set_negative(r->Y, 0);
826*1dcdf01fSchristos
827*1dcdf01fSchristos ret = 1;
828*1dcdf01fSchristos
829*1dcdf01fSchristos err:
830*1dcdf01fSchristos BN_CTX_end(ctx);
831*1dcdf01fSchristos return ret;
832*1dcdf01fSchristos }
833*1dcdf01fSchristos
834*1dcdf01fSchristos static
ec_GF2m_simple_points_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,size_t num,const EC_POINT * points[],const BIGNUM * scalars[],BN_CTX * ctx)835*1dcdf01fSchristos int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
836*1dcdf01fSchristos const BIGNUM *scalar, size_t num,
837*1dcdf01fSchristos const EC_POINT *points[],
838*1dcdf01fSchristos const BIGNUM *scalars[],
839*1dcdf01fSchristos BN_CTX *ctx)
840*1dcdf01fSchristos {
841*1dcdf01fSchristos int ret = 0;
842*1dcdf01fSchristos EC_POINT *t = NULL;
843*1dcdf01fSchristos
844*1dcdf01fSchristos /*-
845*1dcdf01fSchristos * We limit use of the ladder only to the following cases:
846*1dcdf01fSchristos * - r := scalar * G
847*1dcdf01fSchristos * Fixed point mul: scalar != NULL && num == 0;
848*1dcdf01fSchristos * - r := scalars[0] * points[0]
849*1dcdf01fSchristos * Variable point mul: scalar == NULL && num == 1;
850*1dcdf01fSchristos * - r := scalar * G + scalars[0] * points[0]
851*1dcdf01fSchristos * used, e.g., in ECDSA verification: scalar != NULL && num == 1
852*1dcdf01fSchristos *
853*1dcdf01fSchristos * In any other case (num > 1) we use the default wNAF implementation.
854*1dcdf01fSchristos *
855*1dcdf01fSchristos * We also let the default implementation handle degenerate cases like group
856*1dcdf01fSchristos * order or cofactor set to 0.
857*1dcdf01fSchristos */
858*1dcdf01fSchristos if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
859*1dcdf01fSchristos return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
860*1dcdf01fSchristos
861*1dcdf01fSchristos if (scalar != NULL && num == 0)
862*1dcdf01fSchristos /* Fixed point multiplication */
863*1dcdf01fSchristos return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
864*1dcdf01fSchristos
865*1dcdf01fSchristos if (scalar == NULL && num == 1)
866*1dcdf01fSchristos /* Variable point multiplication */
867*1dcdf01fSchristos return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
868*1dcdf01fSchristos
869*1dcdf01fSchristos /*-
870*1dcdf01fSchristos * Double point multiplication:
871*1dcdf01fSchristos * r := scalar * G + scalars[0] * points[0]
872*1dcdf01fSchristos */
873*1dcdf01fSchristos
874*1dcdf01fSchristos if ((t = EC_POINT_new(group)) == NULL) {
875*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
876*1dcdf01fSchristos return 0;
877*1dcdf01fSchristos }
878*1dcdf01fSchristos
879*1dcdf01fSchristos if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
880*1dcdf01fSchristos || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
881*1dcdf01fSchristos || !EC_POINT_add(group, r, t, r, ctx))
882*1dcdf01fSchristos goto err;
883*1dcdf01fSchristos
884*1dcdf01fSchristos ret = 1;
885*1dcdf01fSchristos
886*1dcdf01fSchristos err:
887*1dcdf01fSchristos EC_POINT_free(t);
888*1dcdf01fSchristos return ret;
889*1dcdf01fSchristos }
890*1dcdf01fSchristos
891*1dcdf01fSchristos /*-
892*1dcdf01fSchristos * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
893*1dcdf01fSchristos * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
894*1dcdf01fSchristos * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
895*1dcdf01fSchristos */
ec_GF2m_simple_field_inv(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)896*1dcdf01fSchristos static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
897*1dcdf01fSchristos const BIGNUM *a, BN_CTX *ctx)
898*1dcdf01fSchristos {
899*1dcdf01fSchristos int ret;
900*1dcdf01fSchristos
901*1dcdf01fSchristos if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
902*1dcdf01fSchristos ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
903*1dcdf01fSchristos return ret;
904*1dcdf01fSchristos }
905*1dcdf01fSchristos
EC_GF2m_simple_method(void)906*1dcdf01fSchristos const EC_METHOD *EC_GF2m_simple_method(void)
907*1dcdf01fSchristos {
908*1dcdf01fSchristos static const EC_METHOD ret = {
909*1dcdf01fSchristos EC_FLAGS_DEFAULT_OCT,
910*1dcdf01fSchristos NID_X9_62_characteristic_two_field,
911*1dcdf01fSchristos ec_GF2m_simple_group_init,
912*1dcdf01fSchristos ec_GF2m_simple_group_finish,
913*1dcdf01fSchristos ec_GF2m_simple_group_clear_finish,
914*1dcdf01fSchristos ec_GF2m_simple_group_copy,
915*1dcdf01fSchristos ec_GF2m_simple_group_set_curve,
916*1dcdf01fSchristos ec_GF2m_simple_group_get_curve,
917*1dcdf01fSchristos ec_GF2m_simple_group_get_degree,
918*1dcdf01fSchristos ec_group_simple_order_bits,
919*1dcdf01fSchristos ec_GF2m_simple_group_check_discriminant,
920*1dcdf01fSchristos ec_GF2m_simple_point_init,
921*1dcdf01fSchristos ec_GF2m_simple_point_finish,
922*1dcdf01fSchristos ec_GF2m_simple_point_clear_finish,
923*1dcdf01fSchristos ec_GF2m_simple_point_copy,
924*1dcdf01fSchristos ec_GF2m_simple_point_set_to_infinity,
925*1dcdf01fSchristos 0, /* set_Jprojective_coordinates_GFp */
926*1dcdf01fSchristos 0, /* get_Jprojective_coordinates_GFp */
927*1dcdf01fSchristos ec_GF2m_simple_point_set_affine_coordinates,
928*1dcdf01fSchristos ec_GF2m_simple_point_get_affine_coordinates,
929*1dcdf01fSchristos 0, /* point_set_compressed_coordinates */
930*1dcdf01fSchristos 0, /* point2oct */
931*1dcdf01fSchristos 0, /* oct2point */
932*1dcdf01fSchristos ec_GF2m_simple_add,
933*1dcdf01fSchristos ec_GF2m_simple_dbl,
934*1dcdf01fSchristos ec_GF2m_simple_invert,
935*1dcdf01fSchristos ec_GF2m_simple_is_at_infinity,
936*1dcdf01fSchristos ec_GF2m_simple_is_on_curve,
937*1dcdf01fSchristos ec_GF2m_simple_cmp,
938*1dcdf01fSchristos ec_GF2m_simple_make_affine,
939*1dcdf01fSchristos ec_GF2m_simple_points_make_affine,
940*1dcdf01fSchristos ec_GF2m_simple_points_mul,
941*1dcdf01fSchristos 0, /* precompute_mult */
942*1dcdf01fSchristos 0, /* have_precompute_mult */
943*1dcdf01fSchristos ec_GF2m_simple_field_mul,
944*1dcdf01fSchristos ec_GF2m_simple_field_sqr,
945*1dcdf01fSchristos ec_GF2m_simple_field_div,
946*1dcdf01fSchristos ec_GF2m_simple_field_inv,
947*1dcdf01fSchristos 0, /* field_encode */
948*1dcdf01fSchristos 0, /* field_decode */
949*1dcdf01fSchristos 0, /* field_set_to_one */
950*1dcdf01fSchristos ec_key_simple_priv2oct,
951*1dcdf01fSchristos ec_key_simple_oct2priv,
952*1dcdf01fSchristos 0, /* set private */
953*1dcdf01fSchristos ec_key_simple_generate_key,
954*1dcdf01fSchristos ec_key_simple_check_key,
955*1dcdf01fSchristos ec_key_simple_generate_public_key,
956*1dcdf01fSchristos 0, /* keycopy */
957*1dcdf01fSchristos 0, /* keyfinish */
958*1dcdf01fSchristos ecdh_simple_compute_key,
959*1dcdf01fSchristos 0, /* field_inverse_mod_ord */
960*1dcdf01fSchristos 0, /* blind_coordinates */
961*1dcdf01fSchristos ec_GF2m_simple_ladder_pre,
962*1dcdf01fSchristos ec_GF2m_simple_ladder_step,
963*1dcdf01fSchristos ec_GF2m_simple_ladder_post
964*1dcdf01fSchristos };
965*1dcdf01fSchristos
966*1dcdf01fSchristos return &ret;
96760662d10Schristos }
96860662d10Schristos
96960662d10Schristos #endif
970