ec_GFp_simple_is_on_curve,
ec_GFp_simple_cmp,
ec_GFp_simple_make_affine,
+ ec_GFp_simple_points_make_affine,
ec_GFp_simple_field_mul,
ec_GFp_simple_field_sqr,
0 /* field_encode */,
- 0 /* field_decode */ };
+ 0 /* field_decode */,
+ 0 /* field_set_to_one */ };
return &ret;
}
}
-int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
+int ec_GFp_simple_group_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
{
int ret = 0;
BN_CTX *new_ctx = NULL;
int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator,
const BIGNUM *order, const BIGNUM *cofactor)
{
- if (generator)
+ if (generator == NULL)
{
ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR, ERR_R_PASSED_NULL_PARAMETER);
return 0 ;
}
-EC_POINT *ec_GFp_simple_group_get0_generator(EC_GROUP *group)
+EC_POINT *ec_GFp_simple_group_get0_generator(const EC_GROUP *group)
{
return group->generator;
}
-int ec_GFp_simple_group_get_order(EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
+int ec_GFp_simple_group_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
{
if (!BN_copy(order, &group->order))
return 0;
}
-int ec_GFp_simple_group_get_cofactor(EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
+int ec_GFp_simple_group_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
{
if (!BN_copy(cofactor, &group->cofactor))
return 0;
Z_is_one = BN_is_one(&point->Z);
if (group->meth->field_encode)
{
- if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
+ if (Z_is_one && (group->meth->field_set_to_one != 0))
+ {
+ if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
+ }
+ else
+ {
+ if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
+ }
}
point->Z_is_one = Z_is_one;
}
ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, ERR_R_BN_LIB);
goto err;
}
- if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
+
+ if (group->meth->field_encode == 0)
+ {
+ /* field_sqr works on standard representation */
+ if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
+ }
if (x != NULL)
{
- if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
+ if (group->meth->field_encode == 0)
+ {
+ /* field_mul works on standard representation */
+ if (!group->meth->field_mul(group, x, X_, Z_2, ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
+ }
}
if (y != NULL)
{
- if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
- if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
+ if (group->meth->field_encode == 0)
+ {
+ /* field_mul works on standard representation */
+ if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
+ if (!group->meth->field_mul(group, y, Y_, Z_3, ctx)) goto err;
+
+ }
+ else
+ {
+ if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
+ if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
+ }
}
}
int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
- const BIGNUM *x, int y_bit, BN_CTX *ctx)
+ const BIGNUM *x_, int y_bit, BN_CTX *ctx)
{
BN_CTX *new_ctx = NULL;
- BIGNUM *tmp1, *tmp2, *y;
+ BIGNUM *tmp1, *tmp2, *x, *y;
int ret = 0;
if (ctx == NULL)
BN_CTX_start(ctx);
tmp1 = BN_CTX_get(ctx);
tmp2 = BN_CTX_get(ctx);
+ x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
if (y == NULL) goto err;
*/
/* tmp1 := x^3 */
- if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err;
- if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err;
+ if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
+ if (group->meth->field_decode == 0)
+ {
+ /* field_{sqr,mul} work on standard representation */
+ if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
+ if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
+ if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
+ }
/* tmp1 := tmp1 + a*x */
if (group->a_is_minus3)
}
else
{
- if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err;
+ /* field_mul works on standard representation */
+ if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
}
if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
{
- ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_BN_LIB);
+ unsigned long err = ERR_peek_error();
+
+ if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
+ {
+ (void)ERR_get_error();
+ ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, EC_R_INVALID_COMPRESSED_POINT);
+ }
+ else
+ ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_BN_LIB);
goto err;
}
/* If tmp1 is not a square (i.e. there is no point on the curve with
size_t field_len, enc_len;
int ret = 0;
- if (len <= 0)
+ if (len == 0)
{
ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
return 0;
}
+int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
+ {
+ BN_CTX *new_ctx = NULL;
+ BIGNUM *tmp0, *tmp1;
+ size_t pow2 = 0;
+ BIGNUM **heap = NULL;
+ size_t i;
+ int ret = 0;
+
+ if (num == 0)
+ return 1;
+
+ if (ctx == NULL)
+ {
+ ctx = new_ctx = BN_CTX_new();
+ if (ctx == NULL)
+ return 0;
+ }
+
+ BN_CTX_start(ctx);
+ tmp0 = BN_CTX_get(ctx);
+ tmp1 = BN_CTX_get(ctx);
+ if (tmp0 == NULL || tmp1 == NULL) goto err;
+
+ /* Before converting the individual points, compute inverses of all Z values.
+ * Modular inversion is rather slow, but luckily we can do with a single
+ * explicit inversion, plus about 3 multiplications per input value.
+ */
+
+ pow2 = 1;
+ while (num > pow2)
+ pow2 <<= 1;
+ /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
+ * We need twice that. */
+ pow2 <<= 1;
+
+ heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
+ if (heap == NULL) goto err;
+
+ /* The array is used as a binary tree, exactly as in heapsort:
+ *
+ * heap[1]
+ * heap[2] heap[3]
+ * heap[4] heap[5] heap[6] heap[7]
+ * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
+ *
+ * We put the Z's in the last line;
+ * then we set each other node to the product of its two child-nodes (where
+ * empty or 0 entries are treated as ones);
+ * then we invert heap[1];
+ * then we invert each other node by replacing it by the product of its
+ * parent (after inversion) and its sibling (before inversion).
+ */
+ heap[0] = NULL;
+ for (i = pow2/2 - 1; i > 0; i--)
+ heap[i] = NULL;
+ for (i = 0; i < num; i++)
+ heap[pow2/2 + i] = &points[i]->Z;
+ for (i = pow2/2 + num; i < pow2; i++)
+ heap[i] = NULL;
+
+ /* set each node to the product of its children */
+ for (i = pow2/2 - 1; i > 0; i--)
+ {
+ heap[i] = BN_new();
+ if (heap[i] == NULL) goto err;
+
+ if (heap[2*i] != NULL)
+ {
+ if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
+ {
+ if (!BN_copy(heap[i], heap[2*i])) goto err;
+ }
+ else
+ {
+ if (BN_is_zero(heap[2*i]))
+ {
+ if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
+ }
+ else
+ {
+ if (!group->meth->field_mul(group, heap[i],
+ heap[2*i], heap[2*i + 1], ctx)) goto err;
+ }
+ }
+ }
+ }
+
+ /* invert heap[1] */
+ if (!BN_is_zero(heap[1]))
+ {
+ if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
+ {
+ ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
+ goto err;
+ }
+ }
+ if (group->meth->field_encode != 0)
+ {
+ /* in the Montgomery case, we just turned R*H (representing H)
+ * into 1/(R*H), but we need R*(1/H) (representing 1/H);
+ * i.e. we have need to multiply by the Montgomery factor twice */
+ if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+ if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+ }
+
+ /* set other heap[i]'s to their inverses */
+ for (i = 2; i < pow2/2 + num; i += 2)
+ {
+ /* i is even */
+ if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
+ {
+ if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
+ if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
+ if (!BN_copy(heap[i], tmp0)) goto err;
+ if (!BN_copy(heap[i + 1], tmp1)) goto err;
+ }
+ else
+ {
+ if (!BN_copy(heap[i], heap[i/2])) goto err;
+ }
+ }
+
+ /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
+ for (i = 0; i < num; i++)
+ {
+ EC_POINT *p = points[i];
+
+ if (!BN_is_zero(&p->Z))
+ {
+ /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
+
+ if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
+ if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
+
+ if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
+ if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
+
+ if (group->meth->field_set_to_one != 0)
+ {
+ if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_one(&p->Z)) goto err;
+ }
+ p->Z_is_one = 1;
+ }
+ }
+
+ ret = 1;
+
+ err:
+ BN_CTX_end(ctx);
+ if (new_ctx != NULL)
+ BN_CTX_free(new_ctx);
+ if (heap != NULL)
+ {
+ /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
+ for (i = pow2/2 - 1; i > 0; i--)
+ {
+ if (heap[i] != NULL)
+ BN_clear_free(heap[i]);
+ }
+ OPENSSL_free(heap);
+ }
+ return ret;
+ }
+
+
int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
{
return BN_mod_mul(r, a, b, &group->field, ctx);
projects / openssl.git / blobdiff