DO NOT MERGE
Compute ECDSA modular inverses with Fermal's Little Theorem.
This is a partial cherry-pick of
18954938684e269ccd59152027d2244040e2b819.
Bug: 33752052
Change-Id: Iddba4b931f88d2a0d2f7b9b1904b294fff1d8501
(cherry picked from commit 1f170d0b00fbf42c023c3746dd36eb96115e2a6e)
diff --git a/src/crypto/ec/ec.c b/src/crypto/ec/ec.c
index f38eba6..1bc2e26 100644
--- a/src/crypto/ec/ec.c
+++ b/src/crypto/ec/ec.c
@@ -67,6 +67,7 @@
#include <openssl/ec.h>
+#include <assert.h>
#include <string.h>
#include <openssl/bn.h>
@@ -75,6 +76,7 @@
#include <openssl/obj.h>
#include "internal.h"
+#include "../internal.h"
static const struct curve_data P224 = {
@@ -233,6 +235,70 @@
{NID_undef, 0, 0},
};
+/* built_in_curve_scalar_field_monts contains Montgomery contexts for
+ * performing inversions in the scalar fields of each of the built-in
+ * curves. It's protected by |built_in_curve_scalar_field_monts_once|. */
+static const BN_MONT_CTX **built_in_curve_scalar_field_monts;
+
+static CRYPTO_once_t built_in_curve_scalar_field_monts_once;
+
+static void built_in_curve_scalar_field_monts_init(void) {
+ unsigned num_built_in_curves;
+ for (num_built_in_curves = 0;; num_built_in_curves++) {
+ if (OPENSSL_built_in_curves[num_built_in_curves].nid == NID_undef) {
+ break;
+ }
+ }
+
+ assert(0 < num_built_in_curves);
+
+ built_in_curve_scalar_field_monts =
+ OPENSSL_malloc(sizeof(BN_MONT_CTX *) * num_built_in_curves);
+ if (built_in_curve_scalar_field_monts == NULL) {
+ return;
+ }
+
+ BIGNUM *order = BN_new();
+ BN_CTX *bn_ctx = BN_CTX_new();
+ BN_MONT_CTX *mont_ctx = NULL;
+
+ if (bn_ctx == NULL ||
+ order == NULL) {
+ goto err;
+ }
+
+ unsigned i;
+ for (i = 0; i < num_built_in_curves; i++) {
+ const struct curve_data *curve = OPENSSL_built_in_curves[i].data;
+ const unsigned param_len = curve->param_len;
+ const uint8_t *params = curve->data;
+
+ mont_ctx = BN_MONT_CTX_new();
+ if (mont_ctx == NULL) {
+ goto err;
+ }
+
+ if (!BN_bin2bn(params + 5 * param_len, param_len, order) ||
+ !BN_MONT_CTX_set(mont_ctx, order, bn_ctx)) {
+ goto err;
+ }
+
+ built_in_curve_scalar_field_monts[i] = mont_ctx;
+ mont_ctx = NULL;
+ }
+
+ goto out;
+
+err:
+ BN_MONT_CTX_free(mont_ctx);
+ OPENSSL_free(built_in_curve_scalar_field_monts);
+ built_in_curve_scalar_field_monts = NULL;
+
+out:
+ BN_free(order);
+ BN_CTX_free(bn_ctx);
+}
+
EC_GROUP *ec_group_new(const EC_METHOD *meth) {
EC_GROUP *ret;
@@ -325,25 +391,23 @@
return 1;
}
-static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) {
+static EC_GROUP *ec_group_new_from_data(unsigned built_in_index) {
+ const struct built_in_curve *curve = &OPENSSL_built_in_curves[built_in_index];
EC_GROUP *group = NULL;
EC_POINT *P = NULL;
- BN_CTX *ctx = NULL;
BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL, *order = NULL;
- int ok = 0;
- unsigned param_len;
const EC_METHOD *meth;
- const struct curve_data *data;
- const uint8_t *params;
- if ((ctx = BN_CTX_new()) == NULL) {
+ int ok = 0;
+ BN_CTX *ctx = BN_CTX_new();
+ if (ctx == NULL) {
OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_MALLOC_FAILURE);
goto err;
}
- data = curve->data;
- param_len = data->param_len;
- params = data->data;
+ const struct curve_data *data = curve->data;
+ const unsigned param_len = data->param_len;
+ const uint8_t *params = data->data;
if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) ||
!(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) ||
@@ -387,6 +451,12 @@
goto err;
}
+ CRYPTO_once(&built_in_curve_scalar_field_monts_once,
+ built_in_curve_scalar_field_monts_init);
+ if (built_in_curve_scalar_field_monts != NULL) {
+ group->mont_data = built_in_curve_scalar_field_monts[built_in_index];
+ }
+
group->generator = P;
P = NULL;
if (!BN_copy(&group->order, order) ||
@@ -421,7 +491,7 @@
for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) {
curve = &OPENSSL_built_in_curves[i];
if (curve->nid == nid) {
- ret = ec_group_new_from_data(curve);
+ ret = ec_group_new_from_data(i);
break;
}
}
@@ -468,6 +538,7 @@
ec_pre_comp_free(dest->pre_comp);
dest->pre_comp = ec_pre_comp_dup(src->pre_comp);
+ dest->mont_data = src->mont_data;
if (src->generator != NULL) {
if (dest->generator == NULL) {
@@ -480,11 +551,8 @@
return 0;
}
} else {
- /* src->generator == NULL */
- if (dest->generator != NULL) {
- EC_POINT_clear_free(dest->generator);
- dest->generator = NULL;
- }
+ EC_POINT_clear_free(dest->generator);
+ dest->generator = NULL;
}
if (!BN_copy(&dest->order, &src->order) ||
@@ -497,6 +565,10 @@
return dest->meth->group_copy(dest, src);
}
+const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group) {
+ return group->mont_data;
+}
+
EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
EC_GROUP *t = NULL;
int ok = 0;
diff --git a/src/crypto/ec/internal.h b/src/crypto/ec/internal.h
index 71062c1..89d86fd 100644
--- a/src/crypto/ec/internal.h
+++ b/src/crypto/ec/internal.h
@@ -200,6 +200,7 @@
int curve_name; /* optional NID for named curve */
struct ec_pre_comp_st *pre_comp;
+ const BN_MONT_CTX *mont_data; /* data for ECDSA inverse */
/* The following members are handled by the method functions,
* even if they appear generic */
@@ -230,6 +231,11 @@
EC_GROUP *ec_group_new(const EC_METHOD *meth);
int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src);
+/* ec_group_get_mont_data returns a Montgomery context for operations in the
+ * scalar field of |group|. It may return NULL in the case that |group| is not
+ * a built-in group. */
+const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group);
+
int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
BN_CTX *);
@@ -321,6 +327,10 @@
const EC_METHOD *EC_GFp_nistp256_method(void);
+/* Returns GFp methods using montgomery multiplication, with x86-64
+ * optimized P256. See http://eprint.iacr.org/2013/816. */
+const EC_METHOD *EC_GFp_nistz256_method(void);
+
struct ec_key_st {
int version;
diff --git a/src/crypto/ecdsa/ecdsa.c b/src/crypto/ecdsa/ecdsa.c
index b71799e..86e41bb 100644
--- a/src/crypto/ecdsa/ecdsa.c
+++ b/src/crypto/ecdsa/ecdsa.c
@@ -322,7 +322,21 @@
} while (BN_is_zero(r));
/* compute the inverse of k */
- if (!BN_mod_inverse(k, k, order, ctx)) {
+ if (ec_group_get_mont_data(group) != NULL) {
+ /* We want inverse in constant time, therefore we use that the order must
+ * be prime and thus we can use Fermat's Little Theorem. */
+ if (!BN_set_word(X, 2) ||
+ !BN_sub(X, order, X)) {
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
+ goto err;
+ }
+ BN_set_flags(X, BN_FLG_CONSTTIME);
+ if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx,
+ ec_group_get_mont_data(group))) {
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
+ goto err;
+ }
+ } else if (!BN_mod_inverse(k, k, order, ctx)) {
OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
goto err;
}
