Optimize EC_GFp_mont_method's cmp_x_coordinate.
For simplicity, punt order > field or width mismatches. Analogous
optimizations are possible, but the generic path works fine and no
commonly-used curve looks hits those cases.
Before:
Did 5888 ECDSA P-384 verify operations in 3094535us (1902.7 ops/sec)
After [+6.7%]:
Did 6107 ECDSA P-384 verify operations in 3007515us (2030.6 ops/sec)
Also we can fill in p - order generically and avoid extra copies of some
constants.
Change-Id: I38e1b6d51b28ed4f8cb74697b00a4f0fbc5efc3c
Reviewed-on: https://boringssl-review.googlesource.com/c/33068
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index a783b73..4420c08 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -344,9 +344,8 @@
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.
- // Additionally, |generator| must been created from
- // |EC_GROUP_new_curve_GFp|, not a copy, so that
- // |generator->group->generator| is set correctly.
+ // |generator| must have been created from |EC_GROUP_new_curve_GFp|, not a
+ // copy, so that |generator->group->generator| is set correctly.
OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
return 0;
}
@@ -367,25 +366,23 @@
// Note any curve which did not satisfy this must have been invalid or use a
// 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)) {
- BN_free(tmp);
- return 0;
+ goto err;
}
- int ok = BN_cmp(tmp, &group->field) > 0;
- BN_free(tmp);
- if (!ok) {
+ if (BN_cmp(tmp, &group->field) <= 0) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_GROUP_ORDER);
- return 0;
+ goto err;
}
- EC_POINT *copy = EC_POINT_new(group);
+ copy = EC_POINT_new(group);
if (copy == NULL ||
!EC_POINT_copy(copy, generator) ||
!BN_copy(&group->order, order)) {
- EC_POINT_free(copy);
- return 0;
+ goto err;
}
// Store the order in minimal form, so it can be used with |BN_ULONG| arrays.
bn_set_minimal_width(&group->order);
@@ -393,11 +390,26 @@
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;
+ 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);
- return 1;
+ 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) {
@@ -449,6 +461,14 @@
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);
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index 4961a7c..caa1966 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -417,6 +417,51 @@
}
}
+static int ec_GFp_mont_cmp_x_coordinate(const EC_GROUP *group,
+ const EC_RAW_POINT *p,
+ const EC_SCALAR *r) {
+ if (!group->field_greater_than_order ||
+ group->field.width != group->order.width) {
+ // Do not bother optimizing this case. p > order in all commonly-used
+ // curves.
+ return ec_GFp_simple_cmp_x_coordinate(group, p, r);
+ }
+
+ if (ec_GFp_simple_is_at_infinity(group, p)) {
+ return 0;
+ }
+
+ // We wish to compare X/Z^2 with r. This is equivalent to comparing X with
+ // r*Z^2. Note that X and Z are represented in Montgomery form, while r is
+ // not.
+ EC_FELEM r_Z2, Z2_mont, X;
+ ec_GFp_mont_felem_mul(group, &Z2_mont, &p->Z, &p->Z);
+ // r < order < p, so this is valid.
+ OPENSSL_memcpy(r_Z2.words, r->words, group->field.width * sizeof(BN_ULONG));
+ ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
+ ec_GFp_mont_felem_from_montgomery(group, &X, &p->X);
+
+ if (ec_felem_equal(group, &r_Z2, &X)) {
+ return 1;
+ }
+
+ // During signing the x coefficient is reduced modulo the group order.
+ // Therefore there is a small possibility, less than 1/2^128, that group_order
+ // < p.x < P. in that case we need not only to compare against |r| but also to
+ // compare against r+group_order.
+ if (bn_less_than_words(r->words, group->field_minus_order.words,
+ group->field.width)) {
+ // We can ignore the carry because: r + group_order < p < 2^256.
+ bn_add_words(r_Z2.words, r->words, group->order.d, group->field.width);
+ ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
+ if (ec_felem_equal(group, &r_Z2, &X)) {
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) {
out->group_init = ec_GFp_mont_group_init;
out->group_finish = ec_GFp_mont_group_finish;
@@ -432,5 +477,5 @@
out->felem_to_bignum = ec_GFp_mont_felem_to_bignum;
out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery;
out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime;
- out->cmp_x_coordinate = ec_GFp_simple_cmp_x_coordinate;
+ out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate;
}
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 89e945c..be548a3 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -213,7 +213,20 @@
EC_FELEM a, b; // Curve coefficients.
- int a_is_minus3; // enable optimized point arithmetics for special case
+ // a_is_minus3 is one if |a| is -3 mod |field| and zero otherwise. Point
+ // arithmetic is optimized for -3.
+ int a_is_minus3;
+
+ // field_greater_than_order is one if |field| is greate than |order| and zero
+ // otherwise.
+ int field_greater_than_order;
+
+ // field_minus_order, if |field_greater_than_order| is true, is |field| minus
+ // |order| represented as an |EC_FELEM|. Otherwise, it is zero.
+ //
+ // Note: unlike |EC_FELEM|s used as intermediate values internal to the
+ // |EC_METHOD|, this value is not encoded in Montgomery form.
+ EC_FELEM field_minus_order;
CRYPTO_refcount_t references;
diff --git a/crypto/fipsmodule/ec/p256-x86_64.c b/crypto/fipsmodule/ec/p256-x86_64.c
index 3053e2d..c5f2d1c 100644
--- a/crypto/fipsmodule/ec/p256-x86_64.c
+++ b/crypto/fipsmodule/ec/p256-x86_64.c
@@ -44,12 +44,6 @@
TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0xfffffffe),
};
-// P256_ORDER is the order of the P-256 group, not in Montgomery form.
-static const BN_ULONG P256_ORDER[P256_LIMBS] = {
- TOBN(0xf3b9cac2, 0xfc632551), TOBN(0xbce6faad, 0xa7179e84),
- TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0x00000000),
-};
-
// Precomputed tables for the default generator
#include "p256-x86_64-table.h"
@@ -591,7 +585,8 @@
return ec_GFp_simple_mont_inv_mod_ord_vartime(group, out, in);
}
- if (!beeu_mod_inverse_vartime(out->words, in->words, P256_ORDER)) {
+ assert(group->order.width == P256_LIMBS);
+ if (!beeu_mod_inverse_vartime(out->words, in->words, group->order.d)) {
return 0;
}
@@ -607,6 +602,9 @@
return 0;
}
+ assert(group->order.width == P256_LIMBS);
+ assert(group->field.width == P256_LIMBS);
+
// We wish to compare X/Z^2 with r. This is equivalent to comparing X with
// r*Z^2. Note that X and Z are represented in Montgomery form, while r is
// not.
@@ -623,16 +621,10 @@
// Therefore there is a small possibility, less than 1/2^128, that group_order
// < p.x < P. in that case we need not only to compare against |r| but also to
// compare against r+group_order.
-
- // P_MINUS_ORDER is the difference between the field order (p) and the group
- // order (N). This value is not in the Montgomery domain.
- static const BN_ULONG P_MINUS_ORDER[P256_LIMBS] = {
- TOBN(0x0c46353d, 0x039cdaae), TOBN(0x43190553, 0x58e8617b),
- TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)};
-
- if (bn_less_than_words(r->words, P_MINUS_ORDER, P256_LIMBS)) {
+ if (bn_less_than_words(r->words, group->field_minus_order.words,
+ P256_LIMBS)) {
// We can ignore the carry because: r + group_order < p < 2^256.
- bn_add_words(r_Z2, r->words, P256_ORDER, P256_LIMBS);
+ bn_add_words(r_Z2, r->words, group->order.d, P256_LIMBS);
ecp_nistz256_mul_mont(r_Z2, r_Z2, Z2_mont);
if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) {
return 1;
diff --git a/third_party/fiat/p256.c b/third_party/fiat/p256.c
index 638f681..893c9d4 100644
--- a/third_party/fiat/p256.c
+++ b/third_party/fiat/p256.c
@@ -1838,15 +1838,9 @@
// Therefore there is a small possibility, less than 1/2^128, that group_order
// < p.x < P. in that case we need not only to compare against |r| but also to
// compare against r+group_order.
-
- // P_MINUS_ORDER is the difference between the field order (p) and the group
- // order (N). This value is not in the Montgomery domain.
- static const BN_ULONG P_MINUS_ORDER[] = {
- TOBN(0x0c46353d, 0x039cdaae), TOBN(0x43190553, 0x58e8617b),
- TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)};
- assert(OPENSSL_ARRAY_SIZE(P_MINUS_ORDER) == group->order.width);
- if (bn_less_than_words(r->words, P_MINUS_ORDER,
- OPENSSL_ARRAY_SIZE(P_MINUS_ORDER))) {
+ assert(group->field.width == group->order.width);
+ if (bn_less_than_words(r->words, group->field_minus_order.words,
+ group->field.width)) {
// We can ignore the carry because: r + group_order < p < 2^256.
EC_FELEM tmp;
bn_add_words(tmp.words, r->words, group->order.d, group->order.width);
