自学教程：C++ BN_GF2m_add函数代码示例

/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery  * projective coordinates. * Uses algorithm Madd in appendix of  *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over  *     GF(2^m) without precomputation" (CHES '99, LNCS 1717). */static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 	const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx)	{	BIGNUM *t1, *t2;	int ret = 0;		/* Since Madd is static we can guarantee that ctx != NULL. */	BN_CTX_start(ctx);	t1 = BN_CTX_get(ctx);	t2 = BN_CTX_get(ctx);	if (t2 == NULL) goto err;	if (!BN_copy(t1, x)) goto err;	if (!group->meth->field_mul(group, x1, x1, z2, ctx)) goto err;	if (!group->meth->field_mul(group, z1, z1, x2, ctx)) goto err;	if (!group->meth->field_mul(group, t2, x1, z1, ctx)) goto err;	if (!BN_GF2m_add(z1, z1, x1)) goto err;	if (!group->meth->field_sqr(group, z1, z1, ctx)) goto err;	if (!group->meth->field_mul(group, x1, z1, t1, ctx)) goto err;	if (!BN_GF2m_add(x1, x1, t2)) goto err;	ret = 1; err:	BN_CTX_end(ctx);	return ret;	}

/*- * Determines whether the given EC_POINT is an actual point on the curve defined * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation: *      y^2 + x*y = x^3 + a*x^2 + b. */int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,                               BN_CTX *ctx){    int ret = -1;    BN_CTX *new_ctx = NULL;    BIGNUM *lh, *y2;    int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,                      const BIGNUM *, BN_CTX *);    int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);    if (EC_POINT_is_at_infinity(group, point))        return 1;    field_mul = group->meth->field_mul;    field_sqr = group->meth->field_sqr;    /* only support affine coordinates */    if (!point->Z_is_one)        return -1;    if (ctx == NULL) {        ctx = new_ctx = BN_CTX_new();        if (ctx == NULL)            return -1;    }    BN_CTX_start(ctx);    y2 = BN_CTX_get(ctx);    lh = BN_CTX_get(ctx);    if (lh == NULL)        goto err;    /*-     * We have a curve defined by a Weierstrass equation     *      y^2 + x*y = x^3 + a*x^2 + b.     *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0     *  <=> ((x + a) * x + y ) * x + b + y^2 = 0     */    if (!BN_GF2m_add(lh, &point->X, &group->a))        goto err;    if (!field_mul(group, lh, lh, &point->X, ctx))        goto err;    if (!BN_GF2m_add(lh, lh, &point->Y))        goto err;    if (!field_mul(group, lh, lh, &point->X, ctx))        goto err;    if (!BN_GF2m_add(lh, lh, &group->b))        goto err;    if (!field_sqr(group, y2, &point->Y, ctx))        goto err;    if (!BN_GF2m_add(lh, lh, y2))        goto err;    ret = BN_is_zero(lh); err:    if (ctx)        BN_CTX_end(ctx);    if (new_ctx)        BN_CTX_free(new_ctx);    return ret;}

/*- * Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective * coordinates. * Uses algorithm Mdouble in appendix of *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over *     GF(2^m) without precomputation" (CHES '99, LNCS 1717). * modified to not require precomputation of c=b^{2^{m-1}}. */static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z,                        BN_CTX *ctx){    BIGNUM *t1;    int ret = 0;    /* Since Mdouble is static we can guarantee that ctx != NULL. */    BN_CTX_start(ctx);    t1 = BN_CTX_get(ctx);    if (t1 == NULL)        goto err;    if (!group->meth->field_sqr(group, x, x, ctx))        goto err;    if (!group->meth->field_sqr(group, t1, z, ctx))        goto err;    if (!group->meth->field_mul(group, z, x, t1, ctx))        goto err;    if (!group->meth->field_sqr(group, x, x, ctx))        goto err;    if (!group->meth->field_sqr(group, t1, t1, ctx))        goto err;    if (!group->meth->field_mul(group, t1, &group->b, t1, ctx))        goto err;    if (!BN_GF2m_add(x, x, t1))        goto err;    ret = 1; err:    BN_CTX_end(ctx);    return ret;}

int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)	{	if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))		/* point is its own inverse */		return 1;		if (!EC_POINT_make_affine(group, point, ctx)) return 0;	return BN_GF2m_add(&point->Y, &point->X, &point->Y);	}

/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)  * using Montgomery point multiplication algorithm Mxy() in appendix of  *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over  *     GF(2^m) without precomputation" (CHES '99, LNCS 1717). * Returns: *     0 on error *     1 if return value should be the point at infinity *     2 otherwise */static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1, 	BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx)	{	BIGNUM *t3, *t4, *t5;	int ret = 0;		if (BN_is_zero(z1))		{		BN_zero(x2);		BN_zero(z2);		return 1;		}		if (BN_is_zero(z2))		{		if (!BN_copy(x2, x)) return 0;		if (!BN_GF2m_add(z2, x, y)) return 0;		return 2;		}			/* Since Mxy is static we can guarantee that ctx != NULL. */	BN_CTX_start(ctx);	t3 = BN_CTX_get(ctx);	t4 = BN_CTX_get(ctx);	t5 = BN_CTX_get(ctx);	if (t5 == NULL) goto err;	if (!BN_one(t5)) goto err;	if (!group->meth->field_mul(group, t3, z1, z2, ctx)) goto err;	if (!group->meth->field_mul(group, z1, z1, x, ctx)) goto err;	if (!BN_GF2m_add(z1, z1, x1)) goto err;	if (!group->meth->field_mul(group, z2, z2, x, ctx)) goto err;	if (!group->meth->field_mul(group, x1, z2, x1, ctx)) goto err;	if (!BN_GF2m_add(z2, z2, x2)) goto err;	if (!group->meth->field_mul(group, z2, z2, z1, ctx)) goto err;	if (!group->meth->field_sqr(group, t4, x, ctx)) goto err;	if (!BN_GF2m_add(t4, t4, y)) goto err;	if (!group->meth->field_mul(group, t4, t4, t3, ctx)) goto err;	if (!BN_GF2m_add(t4, t4, z2)) goto err;	if (!group->meth->field_mul(group, t3, t3, x, ctx)) goto err;	if (!group->meth->field_div(group, t3, t5, t3, ctx)) goto err;	if (!group->meth->field_mul(group, t4, t3, t4, ctx)) goto err;	if (!group->meth->field_mul(group, x2, x1, t3, ctx)) goto err;	if (!BN_GF2m_add(z2, x2, x)) goto err;	if (!group->meth->field_mul(group, z2, z2, t4, ctx)) goto err;	if (!BN_GF2m_add(z2, z2, y)) goto err;	ret = 2; err:	BN_CTX_end(ctx);	return ret;	}

/* Computes scalar*point and stores the result in r. * point can not equal r. * Uses a modified algorithm 2P of *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over  *     GF(2^m) without precomputation" (CHES '99, LNCS 1717). * * To protect against side-channel attack the function uses constant time swap, * avoiding conditional branches. */static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,	const EC_POINT *point, BN_CTX *ctx)	{	BIGNUM *x1, *x2, *z1, *z2;	int ret = 0, i;	BN_ULONG mask,word;	if (r == point)		{		ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT);		return 0;		}		/* if result should be point at infinity */	if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 		EC_POINT_is_at_infinity(group, point))		{		return EC_POINT_set_to_infinity(group, r);		}	/* only support affine coordinates */	if (!point->Z_is_one) return 0;	/* Since point_multiply is static we can guarantee that ctx != NULL. */	BN_CTX_start(ctx);	x1 = BN_CTX_get(ctx);	z1 = BN_CTX_get(ctx);	if (z1 == NULL) goto err;	x2 = &r->X;	z2 = &r->Y;	bn_wexpand(x1, group->field.top);	bn_wexpand(z1, group->field.top);	bn_wexpand(x2, group->field.top);	bn_wexpand(z2, group->field.top);	if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */	if (!BN_one(z1)) goto err; /* z1 = 1 */	if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */	if (!group->meth->field_sqr(group, x2, z2, ctx)) goto err;	if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */	/* find top most bit and go one past it */	i = scalar->top - 1;	mask = BN_TBIT;	word = scalar->d[i];	while (!(word & mask)) mask >>= 1;	mask >>= 1;	/* if top most bit was at word break, go to next word */	if (!mask) 		{		i--;		mask = BN_TBIT;		}	for (; i >= 0; i--)		{		word = scalar->d[i];		while (mask)			{			BN_consttime_swap(word & mask, x1, x2, group->field.top);			BN_consttime_swap(word & mask, z1, z2, group->field.top);			if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err;			if (!gf2m_Mdouble(group, x1, z1, ctx)) goto err;			BN_consttime_swap(word & mask, x1, x2, group->field.top);			BN_consttime_swap(word & mask, z1, z2, group->field.top);			mask >>= 1;			}		mask = BN_TBIT;		}	/* convert out of "projective" coordinates */	i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx);	if (i == 0) goto err;	else if (i == 1) 		{		if (!EC_POINT_set_to_infinity(group, r)) goto err;		}	else		{		if (!BN_one(&r->Z)) goto err;		r->Z_is_one = 1;		}	/* GF(2^m) field elements should always have BIGNUM::neg = 0 */	BN_set_negative(&r->X, 0);	BN_set_negative(&r->Y, 0);	ret = 1;//.........这里部分代码省略.........

/* * Computes a + b and stores the result in r.  r could be a or b, a could be * b. Uses algorithm A.10.2 of IEEE P1363. */int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,                       const EC_POINT *b, BN_CTX *ctx){    BN_CTX *new_ctx = NULL;    BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;    int ret = 0;    if (EC_POINT_is_at_infinity(group, a)) {        if (!EC_POINT_copy(r, b))            return 0;        return 1;    }    if (EC_POINT_is_at_infinity(group, b)) {        if (!EC_POINT_copy(r, a))            return 0;        return 1;    }    if (ctx == NULL) {        ctx = new_ctx = BN_CTX_new();        if (ctx == NULL)            return 0;    }    BN_CTX_start(ctx);    x0 = BN_CTX_get(ctx);    y0 = BN_CTX_get(ctx);    x1 = BN_CTX_get(ctx);    y1 = BN_CTX_get(ctx);    x2 = BN_CTX_get(ctx);    y2 = BN_CTX_get(ctx);    s = BN_CTX_get(ctx);    t = BN_CTX_get(ctx);    if (t == NULL)        goto err;    if (a->Z_is_one) {        if (!BN_copy(x0, &a->X))            goto err;        if (!BN_copy(y0, &a->Y))            goto err;    } else {        if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx))            goto err;    }    if (b->Z_is_one) {        if (!BN_copy(x1, &b->X))            goto err;        if (!BN_copy(y1, &b->Y))            goto err;    } else {        if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx))            goto err;    }    if (BN_GF2m_cmp(x0, x1)) {        if (!BN_GF2m_add(t, x0, x1))            goto err;        if (!BN_GF2m_add(s, y0, y1))            goto err;        if (!group->meth->field_div(group, s, s, t, ctx))            goto err;        if (!group->meth->field_sqr(group, x2, s, ctx))            goto err;        if (!BN_GF2m_add(x2, x2, &group->a))            goto err;        if (!BN_GF2m_add(x2, x2, s))            goto err;        if (!BN_GF2m_add(x2, x2, t))            goto err;    } else {        if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {            if (!EC_POINT_set_to_infinity(group, r))                goto err;            ret = 1;            goto err;        }        if (!group->meth->field_div(group, s, y1, x1, ctx))            goto err;        if (!BN_GF2m_add(s, s, x1))            goto err;        if (!group->meth->field_sqr(group, x2, s, ctx))            goto err;        if (!BN_GF2m_add(x2, x2, s))            goto err;        if (!BN_GF2m_add(x2, x2, &group->a))            goto err;    }    if (!BN_GF2m_add(y2, x1, x2))        goto err;    if (!group->meth->field_mul(group, y2, y2, s, ctx))        goto err;    if (!BN_GF2m_add(y2, y2, x2))//.........这里部分代码省略.........

/*- * Calculates and sets the affine coordinates of an EC_POINT from the given * compressed coordinates.  Uses algorithm 2.3.4 of SEC 1. * Note that the simple implementation only uses affine coordinates. * * The method is from the following publication: * *     Harper, Menezes, Vanstone: *     "Public-Key Cryptosystems with Very Small Key Lengths", *     EUROCRYPT '92, Springer-Verlag LNCS 658, *     published February 1993 * * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe * the same method, but claim no priority date earlier than July 29, 1994 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). */int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group,                                              EC_POINT *point,                                              const BIGNUM *x_, int y_bit,                                              BN_CTX *ctx){    BN_CTX *new_ctx = NULL;    BIGNUM *tmp, *x, *y, *z;    int ret = 0, z0;    /* clear error queue */    ERR_clear_error();    if (ctx == NULL) {        ctx = new_ctx = BN_CTX_new();        if (ctx == NULL)            return 0;    }    y_bit = (y_bit != 0) ? 1 : 0;    BN_CTX_start(ctx);    tmp = BN_CTX_get(ctx);    x = BN_CTX_get(ctx);    y = BN_CTX_get(ctx);    z = BN_CTX_get(ctx);    if (z == NULL)        goto err;    if (!BN_GF2m_mod_arr(x, x_, group->poly))        goto err;    if (BN_is_zero(x)) {        if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx))            goto err;    } else {        if (!group->meth->field_sqr(group, tmp, x, ctx))            goto err;        if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx))            goto err;        if (!BN_GF2m_add(tmp, &group->a, tmp))            goto err;        if (!BN_GF2m_add(tmp, x, tmp))            goto err;        if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {            unsigned long err = ERR_peek_last_error();            if (ERR_GET_LIB(err) == ERR_LIB_BN                && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {                ERR_clear_error();                ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,                      EC_R_INVALID_COMPRESSED_POINT);            } else                ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,                      ERR_R_BN_LIB);            goto err;        }        z0 = (BN_is_odd(z)) ? 1 : 0;        if (!group->meth->field_mul(group, y, x, z, ctx))            goto err;        if (z0 != y_bit) {            if (!BN_GF2m_add(y, y, x))                goto err;        }    }    if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))        goto err;    ret = 1; err:    BN_CTX_end(ctx);    if (new_ctx != NULL)        BN_CTX_free(new_ctx);    return ret;}