Introduce an EC_AFFINE abstraction.
PMBTokens ends up converting the same point to affine coordinates
repeatedly. Additionally, it converts many affine coordinates at once,
which we can batch. Introduce an EC_AFFINE type to store affine points
and move the inversion to the Jacobian -> affine conversion.
This does mean we lose the (negligible) Montgomery reduction
optimization in EC_GFp_mont. point_get_affine_coordinates no longer
breaks the EC_FELEM abstraction around Montgomery form.
Unfortunately, this complicates hardening of the callers not checking
return values because EC_AFFINE cannot represent the point at infinity
and, due to OpenSSL's API limitations, groups may not have generators
available and the generator is not affine at the type level. (EC_AFFINE
cannot represent the point at infinity.) Thus this CL:
- Tidies up some duplicate code in setting up the generator and ensures
it always has Z = 1.
- ec_point_set_affine_coordinates hardens against unused results if the
generator is configured. But this is ultimately an internal function.
- Retains the hardening on the public APIs by adding calls to
ec_set_to_safe_point in two places.
This CL does not apply the optimization to Trust Tokens, only introduces
the EC_AFFINE abstraction. It additionally continues to store EC_POINTs
(used in ECDH and ECDSA) in Jacobian form. See
https://crbug.com/boringssl/326#c4 for a discussion on why this is
tricky. Those protocols are hopefully simple enough that they don't need
complexity around inversions.
Having an EC_AFFINE type will also be useful for computing custom tables
for Trust Token public keys, which gives a nice speedup.
Bug: 326
Change-Id: I11b010a33f36a15bac9939351df5205bd35cc665
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/41084
Commit-Queue: Steven Valdez <svaldez@google.com>
Reviewed-by: Steven Valdez <svaldez@google.com>
diff --git a/crypto/ecdh_extra/ecdh_extra.c b/crypto/ecdh_extra/ecdh_extra.c
index b8a099a..237d973 100644
--- a/crypto/ecdh_extra/ecdh_extra.c
+++ b/crypto/ecdh_extra/ecdh_extra.c
@@ -96,8 +96,8 @@
uint8_t buf[EC_MAX_BYTES];
size_t buf_len;
if (!ec_point_mul_scalar(group, &shared_point, &pub_key->raw, priv) ||
- !ec_point_get_affine_coordinate_bytes(group, buf, NULL, &buf_len,
- sizeof(buf), &shared_point)) {
+ !ec_get_x_coordinate_as_bytes(group, buf, &buf_len, sizeof(buf),
+ &shared_point)) {
OPENSSL_PUT_ERROR(ECDH, ECDH_R_POINT_ARITHMETIC_FAILURE);
return -1;
}
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 186a2fe..56a9e1d 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -301,17 +301,49 @@
return ret;
}
-static void ec_group_set0_generator(EC_GROUP *group, EC_POINT *generator) {
+static int ec_group_set_generator(EC_GROUP *group, const EC_AFFINE *generator,
+ const BIGNUM *order) {
assert(group->generator == NULL);
- assert(group == generator->group);
+
+ if (!BN_copy(&group->order, order)) {
+ return 0;
+ }
+ // Store the order in minimal form, so it can be used with |BN_ULONG| arrays.
+ bn_set_minimal_width(&group->order);
+
+ BN_MONT_CTX_free(group->order_mont);
+ group->order_mont = BN_MONT_CTX_new_for_modulus(&group->order, NULL);
+ if (group->order_mont == NULL) {
+ return 0;
+ }
+
+ group->field_greater_than_order = BN_cmp(&group->field, order) > 0;
+ if (group->field_greater_than_order) {
+ BIGNUM tmp;
+ BN_init(&tmp);
+ int ok =
+ BN_sub(&tmp, &group->field, order) &&
+ bn_copy_words(group->field_minus_order.words, group->field.width, &tmp);
+ BN_free(&tmp);
+ if (!ok) {
+ return 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|.
- group->generator = generator;
int is_zero = CRYPTO_refcount_dec_and_test_zero(&group->references);
assert(!is_zero);
(void)is_zero;
+ return 1;
}
EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a,
@@ -384,7 +416,6 @@
// tiny prime (less than 17). See the proof in |field_element_to_scalar| in
// the ECDSA implementation.
int ret = 0;
- EC_POINT *copy = NULL;
BIGNUM *tmp = BN_new();
if (tmp == NULL ||
!BN_lshift1(tmp, order)) {
@@ -395,44 +426,22 @@
goto err;
}
- copy = EC_POINT_new(group);
- if (copy == NULL ||
- !EC_POINT_copy(copy, generator) ||
- !BN_copy(&group->order, order)) {
- goto err;
- }
- // Store the order in minimal form, so it can be used with |BN_ULONG| arrays.
- bn_set_minimal_width(&group->order);
-
- BN_MONT_CTX_free(group->order_mont);
- group->order_mont = BN_MONT_CTX_new_for_modulus(&group->order, NULL);
- if (group->order_mont == NULL) {
+ EC_AFFINE affine;
+ if (!ec_jacobian_to_affine(group, &affine, &generator->raw) ||
+ !ec_group_set_generator(group, &affine, order)) {
goto err;
}
- group->field_greater_than_order = BN_cmp(&group->field, &group->order) > 0;
- if (group->field_greater_than_order) {
- if (!BN_sub(tmp, &group->field, &group->order) ||
- !bn_copy_words(group->field_minus_order.words, group->field.width,
- tmp)) {
- goto err;
- }
- }
-
- ec_group_set0_generator(group, copy);
- copy = NULL;
ret = 1;
err:
- EC_POINT_free(copy);
BN_free(tmp);
return ret;
}
static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) {
EC_GROUP *group = NULL;
- EC_POINT *P = NULL;
- BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL;
+ BIGNUM *p = NULL, *a = NULL, *b = NULL, *order = NULL;
int ok = 0;
BN_CTX *ctx = BN_CTX_new();
@@ -446,7 +455,8 @@
if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) ||
!(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) ||
- !(b = BN_bin2bn(params + 2 * param_len, param_len, NULL))) {
+ !(b = BN_bin2bn(params + 2 * param_len, param_len, NULL)) ||
+ !(order = BN_bin2bn(params + 5 * param_len, param_len, NULL))) {
OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
goto err;
}
@@ -458,42 +468,18 @@
goto err;
}
- if ((P = EC_POINT_new(group)) == NULL) {
- OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
+ EC_AFFINE G;
+ EC_FELEM x, y;
+ if (!ec_felem_from_bytes(group, &x, params + 3 * param_len, param_len) ||
+ !ec_felem_from_bytes(group, &y, params + 4 * param_len, param_len) ||
+ !ec_point_set_affine_coordinates(group, &G, &x, &y)) {
goto err;
}
- if (!(x = BN_bin2bn(params + 3 * param_len, param_len, NULL)) ||
- !(y = BN_bin2bn(params + 4 * param_len, param_len, NULL))) {
- OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
+ if (!ec_group_set_generator(group, &G, order)) {
goto err;
}
- if (!EC_POINT_set_affine_coordinates_GFp(group, P, x, y, ctx)) {
- OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
- goto err;
- }
- if (!BN_bin2bn(params + 5 * param_len, param_len, &group->order)) {
- OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
- goto err;
- }
-
- group->field_greater_than_order = BN_cmp(&group->field, &group->order) > 0;
- if (group->field_greater_than_order) {
- if (!BN_sub(p, &group->field, &group->order) ||
- !bn_copy_words(group->field_minus_order.words, group->field.width, p)) {
- goto err;
- }
- }
-
- group->order_mont = BN_MONT_CTX_new_for_modulus(&group->order, ctx);
- if (group->order_mont == NULL) {
- OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
- goto err;
- }
-
- ec_group_set0_generator(group, P);
- P = NULL;
ok = 1;
err:
@@ -501,13 +487,11 @@
EC_GROUP_free(group);
group = NULL;
}
- EC_POINT_free(P);
BN_CTX_free(ctx);
BN_free(p);
BN_free(a);
BN_free(b);
- BN_free(x);
- BN_free(y);
+ BN_free(order);
return group;
}
@@ -806,14 +790,26 @@
if (!group->meth->point_get_affine_coordinates(group, &point->raw,
x == NULL ? NULL : &x_felem,
y == NULL ? NULL : &y_felem) ||
- (x != NULL && !bn_set_words(x, x_felem.words, group->field.width)) ||
- (y != NULL && !bn_set_words(y, y_felem.words, group->field.width))) {
+ (x != NULL && !ec_felem_to_bignum(group, x, &x_felem)) ||
+ (y != NULL && !ec_felem_to_bignum(group, y, &y_felem))) {
return 0;
}
return 1;
}
-int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_RAW_POINT *out,
+void ec_affine_to_jacobian(const EC_GROUP *group, EC_RAW_POINT *out,
+ const EC_AFFINE *p) {
+ out->X = p->X;
+ out->Y = p->Y;
+ out->Z = group->one;
+}
+
+int ec_jacobian_to_affine(const EC_GROUP *group, EC_AFFINE *out,
+ const EC_RAW_POINT *p) {
+ return group->meth->point_get_affine_coordinates(group, p, &out->X, &out->Y);
+}
+
+int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_AFFINE *out,
const EC_FELEM *x, const EC_FELEM *y) {
void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
const EC_FELEM *b) = group->meth->felem_mul;
@@ -828,24 +824,21 @@
felem_mul(group, &rhs, &rhs, x); // rhs = x^3 + ax
ec_felem_add(group, &rhs, &rhs, &group->b); // rhs = x^3 + ax + b
if (!ec_felem_equal(group, &lhs, &rhs)) {
- // In the event of an error, defend against the caller not checking the
- // return value by setting a known safe value: the base point.
- const EC_POINT *generator = EC_GROUP_get0_generator(group);
- if (generator) {
- ec_GFp_simple_point_copy(out, &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
- // point at infinity.
- ec_GFp_simple_point_set_to_infinity(group, out);
- }
OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
+ // In the event of an error, defend against the caller not checking the
+ // 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;
+ }
return 0;
}
out->X = *x;
out->Y = *y;
- out->Z = group->one;
return 1;
}
@@ -863,13 +856,17 @@
}
EC_FELEM x_felem, y_felem;
+ EC_AFFINE affine;
if (!ec_bignum_to_felem(group, &x_felem, x) ||
!ec_bignum_to_felem(group, &y_felem, y) ||
- !ec_point_set_affine_coordinates(group, &point->raw, &x_felem,
- &y_felem)) {
+ !ec_point_set_affine_coordinates(group, &affine, &x_felem, &y_felem)) {
+ // In the event of an error, defend against the caller not checking the
+ // return value by setting a known safe value.
+ ec_set_to_safe_point(group, &point->raw);
return 0;
}
+ ec_affine_to_jacobian(group, &point->raw, &affine);
return 1;
}
@@ -1056,14 +1053,19 @@
int ec_get_x_coordinate_as_scalar(const EC_GROUP *group, EC_SCALAR *out,
const EC_RAW_POINT *p) {
- EC_FELEM x;
- // For simplicity, in case of width mismatches between |group->field| and
- // |group->order|, zero any untouched words in |x|.
- OPENSSL_memset(&x, 0, sizeof(x));
- if (!group->meth->point_get_affine_coordinates(group, p, &x, NULL)) {
+ uint8_t bytes[EC_MAX_BYTES];
+ size_t len;
+ if (!ec_get_x_coordinate_as_bytes(group, bytes, &len, sizeof(bytes), p)) {
return 0;
}
+ // For simplicity, in case of width mismatches between |group->field| and
+ // |group->order|, zero any untouched words in |out|.
+ OPENSSL_memset(out, 0, sizeof(EC_SCALAR));
+ for (size_t i = 0; i < len; i++) {
+ out->bytes[len - i - 1] = bytes[i];
+ }
+
// We must have p < 2×order, assuming p is not tiny (p >= 17). Thus rather we
// can reduce by performing at most one subtraction.
//
@@ -1082,17 +1084,17 @@
// The above does not guarantee |group->field| is not one word larger than
// |group->order|, so read one extra carry word.
+ BN_ULONG tmp[EC_MAX_WORDS];
BN_ULONG carry =
- group->order.width < EC_MAX_WORDS ? x.words[group->order.width] : 0;
- bn_reduce_once(out->words, x.words, carry, group->order.d,
- group->order.width);
+ group->order.width < EC_MAX_WORDS ? out->words[group->order.width] : 0;
+ bn_reduce_once_in_place(out->words, carry, group->order.d, tmp,
+ group->order.width);
return 1;
}
-int ec_point_get_affine_coordinate_bytes(const EC_GROUP *group, uint8_t *out_x,
- uint8_t *out_y, size_t *out_len,
- size_t max_out,
- const EC_RAW_POINT *p) {
+int ec_get_x_coordinate_as_bytes(const EC_GROUP *group, uint8_t *out,
+ size_t *out_len, size_t max_out,
+ const EC_RAW_POINT *p) {
size_t len = BN_num_bytes(&group->field);
assert(len <= EC_MAX_BYTES);
if (max_out < len) {
@@ -1100,26 +1102,27 @@
return 0;
}
- EC_FELEM x, y;
- if (!group->meth->point_get_affine_coordinates(
- group, p, out_x == NULL ? NULL : &x, out_y == NULL ? NULL : &y)) {
+ EC_FELEM x;
+ if (!group->meth->point_get_affine_coordinates(group, p, &x, NULL)) {
return 0;
}
- if (out_x != NULL) {
- for (size_t i = 0; i < len; i++) {
- out_x[i] = x.bytes[len - i - 1];
- }
- }
- if (out_y != NULL) {
- for (size_t i = 0; i < len; i++) {
- out_y[i] = y.bytes[len - i - 1];
- }
- }
+ ec_felem_to_bytes(group, out, out_len, &x);
*out_len = len;
return 1;
}
+void ec_set_to_safe_point(const EC_GROUP *group, EC_RAW_POINT *out) {
+ if (group->generator != NULL) {
+ 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
+ // point at infinity.
+ ec_GFp_simple_point_set_to_infinity(group, out);
+ }
+}
+
void EC_GROUP_set_asn1_flag(EC_GROUP *group, int flag) {}
const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group) {
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index 233de7f..02bd66c 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -188,12 +188,6 @@
ec_GFp_mont_felem_inv0(group, &z2, &point->Z);
ec_GFp_mont_felem_sqr(group, &z1, &z2);
- // Instead of using |ec_GFp_mont_felem_from_montgomery| to convert the |x|
- // coordinate and then calling |ec_GFp_mont_felem_from_montgomery| again to
- // convert the |y| coordinate below, convert the common factor |z1| once now,
- // saving one reduction.
- ec_GFp_mont_felem_from_montgomery(group, &z1, &z1);
-
if (x != NULL) {
ec_GFp_mont_felem_mul(group, x, &point->X, &z1);
}
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 6333d43..ef6014c 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -239,21 +239,54 @@
// Points.
+//
+// Points may represented in affine coordinates as |EC_AFFINE| or Jacobian
+// coordinates as |EC_RAW_POINT|. Affine coordinates directly represent a
+// point on the curve, but point addition over affine coordinates requires
+// costly field inversions, so arithmetic is done in Jacobian coordinates.
+// Converting from affine to Jacobian is cheap, while converting from Jacobian
+// to affine costs a field inversion. (Jacobian coordinates amortize the field
+// inversions needed in a sequence of point operations.)
+//
+// TODO(davidben): Rename |EC_RAW_POINT| to |EC_JACOBIAN|.
-// An EC_RAW_POINT represents an elliptic curve point. Unlike |EC_POINT|, it is
-// a plain struct which can be stack-allocated and needs no cleanup. It is
-// specific to an |EC_GROUP| and must not be mixed between groups.
+// An EC_RAW_POINT represents an elliptic curve point in Jacobian coordinates.
+// Unlike |EC_POINT|, it is a plain struct which can be stack-allocated and
+// needs no cleanup. It is specific to an |EC_GROUP| and must not be mixed
+// between groups.
typedef struct {
- EC_FELEM X, Y, Z;
// X, Y, and Z are Jacobian projective coordinates. They represent
// (X/Z^2, Y/Z^3) if Z != 0 and the point at infinity otherwise.
+ EC_FELEM X, Y, Z;
} EC_RAW_POINT;
+// An EC_AFFINE represents an elliptic curve point in affine coordinates.
+// coordinates. Note the point at infinity cannot be represented in affine
+// coordinates.
+typedef struct {
+ EC_FELEM X, Y;
+} EC_AFFINE;
+
+// ec_affine_to_jacobian converts |p| to Jacobian form and writes the result to
+// |*out|. This operation is very cheap and only costs a few copies.
+void ec_affine_to_jacobian(const EC_GROUP *group, EC_RAW_POINT *out,
+ const EC_AFFINE *p);
+
+// ec_jacobian_to_affine converts |p| to affine form and writes the result to
+// |*out|. It returns one on success and zero if |p| was the point at infinity.
+// This operation performs a field inversion and should only be done once per
+// point.
+//
+// If only extracting the x-coordinate, use |ec_get_x_coordinate_*| which is
+// slightly faster.
+int ec_jacobian_to_affine(const EC_GROUP *group, EC_AFFINE *out,
+ const EC_RAW_POINT *p);
+
// ec_point_set_affine_coordinates sets |out|'s to a point with affine
// coordinates |x| and |y|. It returns one if the point is on the curve and
// zero otherwise. If the point is not on the curve, the value of |out| is
// undefined.
-int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_RAW_POINT *out,
+int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_AFFINE *out,
const EC_FELEM *x, const EC_FELEM *y);
// ec_point_mul_scalar sets |r| to |p| * |scalar|. Both inputs are considered
@@ -292,30 +325,31 @@
int ec_get_x_coordinate_as_scalar(const EC_GROUP *group, EC_SCALAR *out,
const EC_RAW_POINT *p);
-// ec_point_get_affine_coordinate_bytes writes |p|'s affine coordinates to
-// |out_x| and |out_y|, each of which must have at must |max_out| bytes. It sets
-// |*out_len| to the number of bytes written in each buffer. Coordinates are
-// written big-endian and zero-padded to the size of the field.
-//
-// Either of |out_x| or |out_y| may be NULL to omit that coordinate. This
-// function returns one on success and zero on failure.
-int ec_point_get_affine_coordinate_bytes(const EC_GROUP *group, uint8_t *out_x,
- uint8_t *out_y, size_t *out_len,
- size_t max_out, const EC_RAW_POINT *p);
+// ec_get_x_coordinate_as_bytes writes |p|'s affine x-coordinate to |out|, which
+// must have at must |max_out| bytes. It sets |*out_len| to the number of bytes
+// written. The value is written big-endian and zero-padded to the size of the
+// field. This function returns one on success and zero on failure.
+int ec_get_x_coordinate_as_bytes(const EC_GROUP *group, uint8_t *out,
+ size_t *out_len, size_t max_out,
+ const EC_RAW_POINT *p);
// ec_point_to_bytes behaves like |EC_POINT_point2oct| but takes an
-// |EC_RAW_POINT|.
-OPENSSL_EXPORT size_t ec_point_to_bytes(const EC_GROUP *group,
- const EC_RAW_POINT *point,
- point_conversion_form_t form,
- uint8_t *buf, size_t len);
+// |EC_AFFINE|.
+size_t ec_point_to_bytes(const EC_GROUP *group, const EC_AFFINE *point,
+ point_conversion_form_t form, uint8_t *buf,
+ size_t len);
// ec_point_from_uncompressed parses |in| as a point in uncompressed form and
// sets the result to |out|. It returns one on success and zero if the input was
// invalid.
-int ec_point_from_uncompressed(const EC_GROUP *group, EC_RAW_POINT *out,
+int ec_point_from_uncompressed(const EC_GROUP *group, EC_AFFINE *out,
const uint8_t *in, size_t len);
+// ec_set_to_safe_point sets |out| to an arbitrary point on |group|, either the
+// generator or the point at infinity. This is used to guard against callers of
+// external APIs not checking the return value.
+void ec_set_to_safe_point(const EC_GROUP *group, EC_RAW_POINT *out);
+
// Implementation details.
@@ -328,9 +362,6 @@
// point_get_affine_coordinates sets |*x| and |*y| to the affine coordinates
// of |p|. Either |x| or |y| may be NULL to omit it. It returns one on success
// and zero if |p| is the point at infinity.
- //
- // Note: unlike |EC_FELEM|s used as intermediate values internal to the
- // |EC_METHOD|, |*x| and |*y| are not encoded in Montgomery form.
int (*point_get_affine_coordinates)(const EC_GROUP *, const EC_RAW_POINT *p,
EC_FELEM *x, EC_FELEM *y);
@@ -412,7 +443,8 @@
const EC_METHOD *meth;
// Unlike all other |EC_POINT|s, |generator| does not own |generator->group|
- // to avoid a reference cycle.
+ // 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;
BIGNUM order;
@@ -548,6 +580,9 @@
struct ec_key_st {
EC_GROUP *group;
+ // Ideally |pub_key| would be an |EC_AFFINE| so serializing it does not pay an
+ // inversion each time, but the |EC_KEY_get0_public_key| API implies public
+ // keys are stored in an |EC_POINT|-compatible form.
EC_POINT *pub_key;
EC_WRAPPED_SCALAR *priv_key;
diff --git a/crypto/fipsmodule/ec/oct.c b/crypto/fipsmodule/ec/oct.c
index a2a0fc8..ddd0f37 100644
--- a/crypto/fipsmodule/ec/oct.c
+++ b/crypto/fipsmodule/ec/oct.c
@@ -73,7 +73,7 @@
#include "internal.h"
-size_t ec_point_to_bytes(const EC_GROUP *group, const EC_RAW_POINT *point,
+size_t ec_point_to_bytes(const EC_GROUP *group, const EC_AFFINE *point,
point_conversion_form_t form, uint8_t *buf,
size_t len) {
if (form != POINT_CONVERSION_COMPRESSED &&
@@ -82,11 +82,6 @@
return 0;
}
- if (ec_GFp_simple_is_at_infinity(group, point)) {
- OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
- return 0;
- }
-
const size_t field_len = BN_num_bytes(&group->field);
size_t output_len = 1 /* type byte */ + field_len;
if (form == POINT_CONVERSION_UNCOMPRESSED) {
@@ -101,31 +96,25 @@
return 0;
}
- uint8_t y_buf[EC_MAX_BYTES];
size_t field_len_out;
- if (!ec_point_get_affine_coordinate_bytes(
- group, buf + 1 /* x */,
- form == POINT_CONVERSION_COMPRESSED ? y_buf : buf + 1 + field_len,
- &field_len_out, field_len, point)) {
- return 0;
- }
+ ec_felem_to_bytes(group, buf + 1, &field_len_out, &point->X);
+ assert(field_len_out == field_len);
- if (field_len_out != field_len) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
- }
-
- if (form == POINT_CONVERSION_COMPRESSED) {
- buf[0] = form + (y_buf[field_len - 1] & 1);
- } else {
+ if (form == POINT_CONVERSION_UNCOMPRESSED) {
+ ec_felem_to_bytes(group, buf + 1 + field_len, &field_len_out, &point->Y);
+ assert(field_len_out == field_len);
buf[0] = form;
+ } else {
+ uint8_t y_buf[EC_MAX_BYTES];
+ ec_felem_to_bytes(group, y_buf, &field_len_out, &point->Y);
+ buf[0] = form + (y_buf[field_len_out - 1] & 1);
}
}
return output_len;
}
-int ec_point_from_uncompressed(const EC_GROUP *group, EC_RAW_POINT *out,
+int ec_point_from_uncompressed(const EC_GROUP *group, EC_AFFINE *out,
const uint8_t *in, size_t len) {
const size_t field_len = BN_num_bytes(&group->field);
if (len != 1 + 2 * field_len || in[0] != POINT_CONVERSION_UNCOMPRESSED) {
@@ -153,7 +142,15 @@
point_conversion_form_t form = buf[0];
if (form == POINT_CONVERSION_UNCOMPRESSED) {
- return ec_point_from_uncompressed(group, &point->raw, buf, len);
+ EC_AFFINE affine;
+ if (!ec_point_from_uncompressed(group, &affine, buf, len)) {
+ // In the event of an error, defend against the caller not checking the
+ // return value by setting a known safe value.
+ ec_set_to_safe_point(group, &point->raw);
+ return 0;
+ }
+ ec_affine_to_jacobian(group, &point->raw, &affine);
+ return 1;
}
const int y_bit = form & 1;
@@ -165,6 +162,11 @@
return 0;
}
+ // TODO(davidben): Integrate compressed coordinates with the lower-level EC
+ // abstractions. This requires a way to compute square roots, which is tricky
+ // for primes which are not 3 (mod 4), namely P-224 and custom curves. P-224's
+ // prime is particularly inconvenient for compressed coordinates. See
+ // https://cr.yp.to/papers/sqroot.pdf
BN_CTX *new_ctx = NULL;
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
@@ -212,7 +214,11 @@
OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
return 0;
}
- return ec_point_to_bytes(group, &point->raw, form, buf, len);
+ EC_AFFINE affine;
+ if (!ec_jacobian_to_affine(group, &affine, &point->raw)) {
+ return 0;
+ }
+ return ec_point_to_bytes(group, &affine, form, buf, len);
}
int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group,
diff --git a/crypto/fipsmodule/ec/p256-x86_64.c b/crypto/fipsmodule/ec/p256-x86_64.c
index cb82852..973130f 100644
--- a/crypto/fipsmodule/ec/p256-x86_64.c
+++ b/crypto/fipsmodule/ec/p256-x86_64.c
@@ -432,14 +432,12 @@
if (x != NULL) {
ecp_nistz256_mul_mont(x->words, z_inv2, point->X.words);
- ecp_nistz256_from_mont(x->words, x->words);
}
if (y != NULL) {
ecp_nistz256_sqr_mont(z_inv2, z_inv2); // z^-4
ecp_nistz256_mul_mont(y->words, point->Y.words, point->Z.words); // y * z
ecp_nistz256_mul_mont(y->words, y->words, z_inv2); // y * z^-3
- ecp_nistz256_from_mont(y->words, y->words);
}
return 1;
diff --git a/crypto/fipsmodule/ec/p256.c b/crypto/fipsmodule/ec/p256.c
index bf9e64e..542550f 100644
--- a/crypto/fipsmodule/ec/p256.c
+++ b/crypto/fipsmodule/ec/p256.c
@@ -752,7 +752,6 @@
fiat_p256_felem x;
fiat_p256_from_generic(x, &point->X);
fiat_p256_mul(x, x, z2);
- fiat_p256_from_montgomery(x, x);
fiat_p256_to_generic(x_out, x);
}
@@ -762,7 +761,6 @@
fiat_p256_square(z2, z2); // z^-4
fiat_p256_mul(y, y, z1); // y * z
fiat_p256_mul(y, y, z2); // y * z^-3
- fiat_p256_from_montgomery(y, y);
fiat_p256_to_generic(y_out, y);
}
diff --git a/crypto/fipsmodule/ecdh/ecdh.c b/crypto/fipsmodule/ecdh/ecdh.c
index a7b2f08..4e6d0bf 100644
--- a/crypto/fipsmodule/ecdh/ecdh.c
+++ b/crypto/fipsmodule/ecdh/ecdh.c
@@ -94,8 +94,8 @@
uint8_t buf[EC_MAX_BYTES];
size_t buflen;
if (!ec_point_mul_scalar(group, &shared_point, &pub_key->raw, priv) ||
- !ec_point_get_affine_coordinate_bytes(group, buf, NULL, &buflen,
- sizeof(buf), &shared_point)) {
+ !ec_get_x_coordinate_as_bytes(group, buf, &buflen, sizeof(buf),
+ &shared_point)) {
OPENSSL_PUT_ERROR(ECDH, ECDH_R_POINT_ARITHMETIC_FAILURE);
return 0;
}
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c
index 3117b65..b3764b6 100644
--- a/crypto/trust_token/pmbtoken.c
+++ b/crypto/trust_token/pmbtoken.c
@@ -113,23 +113,32 @@
static int point_to_cbb(CBB *out, const EC_GROUP *group,
const EC_RAW_POINT *point) {
+ EC_AFFINE affine;
+ if (!ec_jacobian_to_affine(group, &affine, point)) {
+ return 0;
+ }
size_t len =
- ec_point_to_bytes(group, point, POINT_CONVERSION_UNCOMPRESSED, NULL, 0);
+ ec_point_to_bytes(group, &affine, POINT_CONVERSION_UNCOMPRESSED, NULL, 0);
if (len == 0) {
return 0;
}
uint8_t *p;
return CBB_add_space(out, &p, len) &&
- ec_point_to_bytes(group, point, POINT_CONVERSION_UNCOMPRESSED, p,
+ ec_point_to_bytes(group, &affine, POINT_CONVERSION_UNCOMPRESSED, p,
len) == len;
}
static int cbs_get_prefixed_point(CBS *cbs, const EC_GROUP *group,
EC_RAW_POINT *out) {
CBS child;
- return CBS_get_u16_length_prefixed(cbs, &child) &&
- ec_point_from_uncompressed(group, out, CBS_data(&child),
- CBS_len(&child));
+ EC_AFFINE affine;
+ if (!CBS_get_u16_length_prefixed(cbs, &child) ||
+ !ec_point_from_uncompressed(group, &affine, CBS_data(&child),
+ CBS_len(&child))) {
+ return 0;
+ }
+ ec_affine_to_jacobian(group, out, &affine);
+ return 1;
}
void PMBTOKEN_PRETOKEN_free(PMBTOKEN_PRETOKEN *pretoken) {
@@ -918,7 +927,12 @@
0xcd,
};
- return ec_point_from_uncompressed(method->group, &method->h, kH, sizeof(kH));
+ EC_AFFINE h;
+ if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) {
+ return 0;
+ }
+ ec_affine_to_jacobian(method->group, &method->h, &h);
+ return 1;
}
int pmbtoken_exp0_generate_key(CBB *out_private, CBB *out_public) {
@@ -1057,7 +1071,12 @@
0x87, 0xc3, 0x95, 0xd0, 0x13, 0xb7, 0x0b, 0x5c, 0xc7,
};
- return ec_point_from_uncompressed(method->group, &method->h, kH, sizeof(kH));
+ EC_AFFINE h;
+ if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) {
+ return 0;
+ }
+ ec_affine_to_jacobian(method->group, &method->h, &h);
+ return 1;
}
int pmbtoken_exp1_generate_key(CBB *out_private, CBB *out_public) {
@@ -1134,6 +1153,8 @@
if (!pmbtoken_exp1_init_method(&method)) {
return 0;
}
- return ec_point_to_bytes(method.group, &method.h,
- POINT_CONVERSION_UNCOMPRESSED, out, 97) == 97;
+ EC_AFFINE h;
+ return ec_jacobian_to_affine(method.group, &h, &method.h) &&
+ ec_point_to_bytes(method.group, &h, POINT_CONVERSION_UNCOMPRESSED, out,
+ 97) == 97;
}
diff --git a/crypto/trust_token/trust_token_test.cc b/crypto/trust_token/trust_token_test.cc
index 50ef729..50be906 100644
--- a/crypto/trust_token/trust_token_test.cc
+++ b/crypto/trust_token/trust_token_test.cc
@@ -75,13 +75,14 @@
const uint8_t kHGen[] = "generator";
const uint8_t kHLabel[] = "PMBTokens Experiment V1 HashH";
- EC_RAW_POINT expected_h;
+ bssl::UniquePtr<EC_POINT> expected_h(EC_POINT_new(group));
+ ASSERT_TRUE(expected_h);
ASSERT_TRUE(ec_hash_to_curve_p384_xmd_sha512_sswu_draft07(
- group, &expected_h, kHLabel, sizeof(kHLabel), kHGen, sizeof(kHGen)));
+ group, &expected_h->raw, kHLabel, sizeof(kHLabel), kHGen, sizeof(kHGen)));
uint8_t expected_bytes[1 + 2 * EC_MAX_BYTES];
size_t expected_len =
- ec_point_to_bytes(group, &expected_h, POINT_CONVERSION_UNCOMPRESSED,
- expected_bytes, sizeof(expected_bytes));
+ EC_POINT_point2oct(group, expected_h.get(), POINT_CONVERSION_UNCOMPRESSED,
+ expected_bytes, sizeof(expected_bytes), nullptr);
uint8_t h[97];
ASSERT_TRUE(pmbtoken_exp1_get_h_for_testing(h));
