Embed the generator into EC_GROUP
Another point indirection removed. As part of this, remove the extra
copy of one and just use generator.raw.Z.
Bug: 20
Change-Id: I066f624fe02e17082383afc15871ab2431e97b61
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60930
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/ec_extra/hash_to_curve.c b/crypto/ec_extra/hash_to_curve.c
index d9d9d5b..2d11ef5 100644
--- a/crypto/ec_extra/hash_to_curve.c
+++ b/crypto/ec_extra/hash_to_curve.c
@@ -286,12 +286,12 @@
group->meth->felem_sqr;
EC_FELEM tv1, tv2, tv3, tv4, tv5, tv6, x, y, y1;
- felem_sqr(group, &tv1, u); // 1. tv1 = u^2
- felem_mul(group, &tv1, Z, &tv1); // 2. tv1 = Z * tv1
- felem_sqr(group, &tv2, &tv1); // 3. tv2 = tv1^2
- ec_felem_add(group, &tv2, &tv2, &tv1); // 4. tv2 = tv2 + tv1
- ec_felem_add(group, &tv3, &tv2, &group->one); // 5. tv3 = tv2 + 1
- felem_mul(group, &tv3, &group->b, &tv3); // 6. tv3 = B * tv3
+ felem_sqr(group, &tv1, u); // 1. tv1 = u^2
+ felem_mul(group, &tv1, Z, &tv1); // 2. tv1 = Z * tv1
+ felem_sqr(group, &tv2, &tv1); // 3. tv2 = tv1^2
+ ec_felem_add(group, &tv2, &tv2, &tv1); // 4. tv2 = tv2 + tv1
+ ec_felem_add(group, &tv3, &tv2, ec_felem_one(group)); // 5. tv3 = tv2 + 1
+ felem_mul(group, &tv3, &group->b, &tv3); // 6. tv3 = B * tv3
// 7. tv4 = CMOV(Z, -tv2, tv2 != 0)
const BN_ULONG tv2_non_zero = ec_felem_non_zero_mask(group, &tv2);
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index a1d6e24..fe77396 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -283,6 +283,8 @@
bn_mont_ctx_init(&ret->field);
bn_mont_ctx_init(&ret->order);
+ ret->generator.group = ret;
+
if (!ec_GFp_simple_group_set_curve(ret, p, a, b, ctx)) {
EC_GROUP_free(ret);
return NULL;
@@ -300,19 +302,9 @@
}
group->field_greater_than_order = BN_cmp(&group->field.N, order) > 0;
- group->generator = EC_POINT_new(group);
- if (group->generator == NULL) {
- return 0;
- }
- ec_affine_to_jacobian(group, &group->generator->raw, generator);
- assert(ec_felem_equal(group, &group->one, &group->generator->raw.Z));
-
- // Avoid a reference cycle. |group->generator| does not maintain an owning
- // pointer to |group|.
- int is_zero = CRYPTO_refcount_dec_and_test_zero(&group->references);
-
- assert(!is_zero);
- (void)is_zero;
+ group->generator.raw.X = generator->X;
+ group->generator.raw.Y = generator->Y;
+ // |raw.Z| was set to 1 by |ec_GFp_simple_group_set_curve|.
group->has_order = 1;
return 1;
}
@@ -357,7 +349,7 @@
int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
const BIGNUM *order, const BIGNUM *cofactor) {
- if (group->curve_name != NID_undef || group->generator != NULL ||
+ if (group->curve_name != NID_undef || group->has_order ||
generator->group != group) {
// |EC_GROUP_set_generator| may only be used with |EC_GROUP|s returned by
// |EC_GROUP_new_curve_GFp| and may only used once on each group.
@@ -521,7 +513,6 @@
return;
}
- ec_point_free(group->generator, /*free_group=*/0);
bn_mont_ctx_cleanup(&group->order);
bn_mont_ctx_cleanup(&group->field);
OPENSSL_free(group);
@@ -558,18 +549,17 @@
// structure. If |a| or |b| is incomplete (due to legacy OpenSSL mistakes,
// custom curve construction is sadly done in two parts) but otherwise not the
// same object, we consider them always unequal.
- return a->meth != b->meth ||
- a->generator == NULL ||
- b->generator == NULL ||
+ return a->meth != b->meth || //
+ !a->has_order || !b->has_order ||
BN_cmp(&a->order.N, &b->order.N) != 0 ||
BN_cmp(&a->field.N, &b->field.N) != 0 ||
- !ec_felem_equal(a, &a->a, &b->a) ||
+ !ec_felem_equal(a, &a->a, &b->a) || //
!ec_felem_equal(a, &a->b, &b->b) ||
- !ec_GFp_simple_points_equal(a, &a->generator->raw, &b->generator->raw);
+ !ec_GFp_simple_points_equal(a, &a->generator.raw, &b->generator.raw);
}
const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) {
- return group->generator;
+ return group->has_order ? &group->generator : NULL;
}
const BIGNUM *EC_GROUP_get0_order(const EC_GROUP *group) {
@@ -764,7 +754,7 @@
const EC_AFFINE *p) {
out->X = p->X;
out->Y = p->Y;
- out->Z = group->one;
+ out->Z = *ec_felem_one(group);
}
int ec_jacobian_to_affine(const EC_GROUP *group, EC_AFFINE *out,
@@ -801,10 +791,9 @@
// return value by setting a known safe value. Note this may not be possible
// if the caller is in the process of constructing an arbitrary group and
// the generator is missing.
- if (group->generator != NULL) {
- assert(ec_felem_equal(group, &group->one, &group->generator->raw.Z));
- out->X = group->generator->raw.X;
- out->Y = group->generator->raw.Y;
+ if (group->has_order) {
+ out->X = group->generator.raw.X;
+ out->Y = group->generator.raw.Y;
}
return 0;
}
@@ -1180,8 +1169,8 @@
}
void ec_set_to_safe_point(const EC_GROUP *group, EC_JACOBIAN *out) {
- if (group->generator != NULL) {
- ec_GFp_simple_point_copy(out, &group->generator->raw);
+ if (group->has_order) {
+ ec_GFp_simple_point_copy(out, &group->generator.raw);
} else {
// The generator can be missing if the caller is in the process of
// constructing an arbitrary group. In this case, we give up and use the
diff --git a/crypto/fipsmodule/ec/felem.c b/crypto/fipsmodule/ec/felem.c
index bc7bbb7..6064819 100644
--- a/crypto/fipsmodule/ec/felem.c
+++ b/crypto/fipsmodule/ec/felem.c
@@ -23,6 +23,11 @@
#include "../../internal.h"
+const EC_FELEM *ec_felem_one(const EC_GROUP *group) {
+ // We reuse generator.Z as a cache for 1 in the field.
+ return &group->generator.raw.Z;
+}
+
int ec_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out, const BIGNUM *in) {
uint8_t bytes[EC_MAX_BYTES];
size_t len = BN_num_bytes(&group->field.N);
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 64f41bb..77c3dd6 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -197,6 +197,9 @@
BN_ULONG words[EC_MAX_WORDS];
} EC_FELEM;
+// ec_felem_one returns one in |group|'s field.
+const EC_FELEM *ec_felem_one(const EC_GROUP *group);
+
// ec_bignum_to_felem converts |in| to an |EC_FELEM|. It returns one on success
// and zero if |in| is out of range.
int ec_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out, const BIGNUM *in);
@@ -583,19 +586,30 @@
const EC_METHOD *EC_GFp_mont_method(void);
+struct ec_point_st {
+ // group is an owning reference to |group|, unless this is
+ // |group->generator|.
+ EC_GROUP *group;
+ // raw is the group-specific point data. Functions that take |EC_POINT|
+ // typically check consistency with |EC_GROUP| while functions that take
+ // |EC_JACOBIAN| do not. Thus accesses to this field should be externally
+ // checked for consistency.
+ EC_JACOBIAN raw;
+} /* EC_POINT */;
+
struct ec_group_st {
const EC_METHOD *meth;
// Unlike all other |EC_POINT|s, |generator| does not own |generator->group|
// to avoid a reference cycle. Additionally, Z is guaranteed to be one, so X
- // and Y are suitable for use as an |EC_AFFINE|.
- EC_POINT *generator;
+ // and Y are suitable for use as an |EC_AFFINE|. Before |has_order| is set, Z
+ // is one, but X and Y are uninitialized.
+ EC_POINT generator;
BN_MONT_CTX order;
BN_MONT_CTX field;
EC_FELEM a, b; // Curve coefficients.
- EC_FELEM one; // The value one.
int curve_name; // optional NID for named curve
@@ -613,17 +627,6 @@
CRYPTO_refcount_t references;
} /* EC_GROUP */;
-struct ec_point_st {
- // group is an owning reference to |group|, unless this is
- // |group->generator|.
- EC_GROUP *group;
- // raw is the group-specific point data. Functions that take |EC_POINT|
- // typically check consistency with |EC_GROUP| while functions that take
- // |EC_JACOBIAN| do not. Thus accesses to this field should be externally
- // checked for consistency.
- EC_JACOBIAN raw;
-} /* EC_POINT */;
-
EC_GROUP *ec_group_new(const EC_METHOD *meth, const BIGNUM *p, const BIGNUM *a,
const BIGNUM *b, BN_CTX *ctx);
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c
index 624d3ce..406e108 100644
--- a/crypto/fipsmodule/ec/simple.c
+++ b/crypto/fipsmodule/ec/simple.c
@@ -107,7 +107,8 @@
if (!BN_MONT_CTX_set(&group->field, p, ctx) ||
!ec_bignum_to_felem(group, &group->a, a) ||
!ec_bignum_to_felem(group, &group->b, b) ||
- !ec_bignum_to_felem(group, &group->one, BN_value_one())) {
+ // Reuse Z from the generator to cache the value one.
+ !ec_bignum_to_felem(group, &group->generator.raw.Z, BN_value_one())) {
goto err;
}
diff --git a/crypto/fipsmodule/ec/simple_mul.c b/crypto/fipsmodule/ec/simple_mul.c
index 796c408..3ec0b12 100644
--- a/crypto/fipsmodule/ec/simple_mul.c
+++ b/crypto/fipsmodule/ec/simple_mul.c
@@ -78,7 +78,7 @@
void ec_GFp_mont_mul_base(const EC_GROUP *group, EC_JACOBIAN *r,
const EC_SCALAR *scalar) {
- ec_GFp_mont_mul(group, r, &group->generator->raw, scalar);
+ ec_GFp_mont_mul(group, r, &group->generator.raw, scalar);
}
static void ec_GFp_mont_batch_precomp(const EC_GROUP *group, EC_JACOBIAN *out,
@@ -230,7 +230,7 @@
ec_felem_select(group, &out->Y, match, &precomp->comb[j].Y, &out->Y);
}
BN_ULONG is_infinity = constant_time_is_zero_w(window);
- ec_felem_select(group, &out->Z, is_infinity, &out->Z, &group->one);
+ ec_felem_select(group, &out->Z, is_infinity, &out->Z, ec_felem_one(group));
}
void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_JACOBIAN *r,
diff --git a/crypto/fipsmodule/ec/wnaf.c b/crypto/fipsmodule/ec/wnaf.c
index 2cc0fbc..f5214b2 100644
--- a/crypto/fipsmodule/ec/wnaf.c
+++ b/crypto/fipsmodule/ec/wnaf.c
@@ -214,7 +214,7 @@
int8_t g_wNAF[EC_MAX_BYTES * 8 + 1];
EC_JACOBIAN g_precomp[EC_WNAF_TABLE_SIZE];
assert(wNAF_len <= OPENSSL_ARRAY_SIZE(g_wNAF));
- const EC_JACOBIAN *g = &group->generator->raw;
+ const EC_JACOBIAN *g = &group->generator.raw;
if (g_scalar != NULL) {
ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS);
compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE);
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c
index be093fc..49eda91 100644
--- a/crypto/trust_token/pmbtoken.c
+++ b/crypto/trust_token/pmbtoken.c
@@ -86,7 +86,7 @@
ec_affine_to_jacobian(method->group, &method->h, &h);
if (!ec_init_precomp(method->group, &method->g_precomp,
- &method->group->generator->raw) ||
+ &method->group->generator.raw) ||
!ec_init_precomp(method->group, &method->h_precomp, &method->h)) {
return 0;
}
@@ -679,7 +679,7 @@
const EC_JACOBIAN *S, const EC_JACOBIAN *W,
const EC_JACOBIAN *Ws) {
const EC_GROUP *group = method->group;
- const EC_JACOBIAN *g = &group->generator->raw;
+ const EC_JACOBIAN *g = &group->generator.raw;
// We verify a DLEQ proof for the validity token and a DLEQOR2 proof for the
// private metadata token. To allow amortizing Jacobian-to-affine conversions,
