summaryrefslogtreecommitdiffstats
path: root/src/crypto/ec
diff options
context:
space:
mode:
Diffstat (limited to 'src/crypto/ec')
-rw-r--r--src/crypto/ec/CMakeLists.txt11
-rw-r--r--src/crypto/ec/ec.c53
-rw-r--r--src/crypto/ec/ec_asn1.c61
-rw-r--r--src/crypto/ec/ec_error.c107
-rw-r--r--src/crypto/ec/ec_key.c95
-rw-r--r--src/crypto/ec/ec_montgomery.c129
-rw-r--r--src/crypto/ec/ec_test.c124
-rw-r--r--src/crypto/ec/ec_test.cc185
-rw-r--r--src/crypto/ec/internal.h47
-rw-r--r--src/crypto/ec/oct.c39
-rw-r--r--src/crypto/ec/p256-64.c1936
-rw-r--r--src/crypto/ec/simple.c611
-rw-r--r--src/crypto/ec/util-64.c183
-rw-r--r--src/crypto/ec/wnaf.c180
14 files changed, 2887 insertions, 874 deletions
diff --git a/src/crypto/ec/CMakeLists.txt b/src/crypto/ec/CMakeLists.txt
index 11266c6..a218c0d 100644
--- a/src/crypto/ec/CMakeLists.txt
+++ b/src/crypto/ec/CMakeLists.txt
@@ -6,13 +6,14 @@ add_library(
OBJECT
ec.c
+ ec_asn1.c
+ ec_key.c
+ ec_montgomery.c
oct.c
+ p256-64.c
+ util-64.c
simple.c
- ec_montgomery.c
wnaf.c
- ec_key.c
- ec_asn1.c
- ec_error.c
)
add_executable(
@@ -24,7 +25,7 @@ add_executable(
add_executable(
ec_test
- ec_test.c
+ ec_test.cc
)
target_link_libraries(example_mul crypto)
diff --git a/src/crypto/ec/ec.c b/src/crypto/ec/ec.c
index 6e676c9..5426b8f 100644
--- a/src/crypto/ec/ec.c
+++ b/src/crypto/ec/ec.c
@@ -219,11 +219,18 @@ static const struct curve_data P521 = {
0xB7, 0x1E, 0x91, 0x38, 0x64, 0x09}};
const struct built_in_curve OPENSSL_built_in_curves[] = {
- {NID_secp224r1, &P224, 0},
- {NID_X9_62_prime256v1, &P256, 0},
- {NID_secp384r1, &P384, 0},
- {NID_secp521r1, &P521, 0},
- {NID_undef, 0, 0},
+ {NID_secp224r1, &P224, 0},
+ {
+ NID_X9_62_prime256v1, &P256,
+#if defined(OPENSSL_64_BIT) && !defined(OPENSSL_WINDOWS)
+ EC_GFp_nistp256_method,
+#else
+ 0,
+#endif
+ },
+ {NID_secp384r1, &P384, 0},
+ {NID_secp521r1, &P521, 0},
+ {NID_undef, 0, 0},
};
EC_GROUP *ec_group_new(const EC_METHOD *meth) {
@@ -357,22 +364,14 @@ err:
EC_GROUP_free(group);
group = NULL;
}
- if (P)
- EC_POINT_free(P);
- if (ctx)
- BN_CTX_free(ctx);
- if (p)
- BN_free(p);
- if (a)
- BN_free(a);
- if (b)
- BN_free(b);
- if (order)
- BN_free(order);
- if (x)
- BN_free(x);
- if (y)
- BN_free(y);
+ EC_POINT_free(P);
+ BN_CTX_free(ctx);
+ BN_free(p);
+ BN_free(a);
+ BN_free(b);
+ BN_free(order);
+ BN_free(x);
+ BN_free(y);
return group;
}
@@ -409,16 +408,14 @@ void EC_GROUP_free(EC_GROUP *group) {
ec_pre_comp_free(group->pre_comp);
- if (group->generator != NULL) {
- EC_POINT_free(group->generator);
- }
+ EC_POINT_free(group->generator);
BN_free(&group->order);
BN_free(&group->cofactor);
OPENSSL_free(group);
}
-int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) {
+int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
if (dest->meth->group_copy == 0) {
OPENSSL_PUT_ERROR(EC, EC_GROUP_copy, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
return 0;
@@ -474,7 +471,7 @@ EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
if (t == NULL) {
return NULL;
}
- if (!EC_GROUP_copy(t, a)) {
+ if (!ec_group_copy(t, a)) {
goto err;
}
@@ -482,9 +479,7 @@ EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
err:
if (!ok) {
- if (t) {
- EC_GROUP_free(t);
- }
+ EC_GROUP_free(t);
return NULL;
} else {
return t;
diff --git a/src/crypto/ec/ec_asn1.c b/src/crypto/ec/ec_asn1.c
index ce9b3f4..ff3dca6 100644
--- a/src/crypto/ec/ec_asn1.c
+++ b/src/crypto/ec/ec_asn1.c
@@ -172,9 +172,7 @@ ECPKPARAMETERS *ec_asn1_group2pkparameters(const EC_GROUP *group,
return NULL;
}
} else {
- if (ret->value.named_curve) {
- ASN1_OBJECT_free(ret->value.named_curve);
- }
+ ASN1_OBJECT_free(ret->value.named_curve);
}
/* use the ASN.1 OID to describe the the elliptic curve parameters. */
@@ -257,10 +255,8 @@ static EC_GROUP *d2i_ECPKParameters(EC_GROUP **groupp, const uint8_t **inp,
return NULL;
}
- if (groupp && *groupp) {
- EC_GROUP_free(*groupp);
- }
if (groupp) {
+ EC_GROUP_free(*groupp);
*groupp = group;
}
@@ -290,16 +286,9 @@ EC_KEY *d2i_ECPrivateKey(EC_KEY **a, const uint8_t **in, long len) {
EC_KEY *ret = NULL;
EC_PRIVATEKEY *priv_key = NULL;
- priv_key = EC_PRIVATEKEY_new();
- if (priv_key == NULL) {
- OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_MALLOC_FAILURE);
- return NULL;
- }
-
- priv_key = d2i_EC_PRIVATEKEY(&priv_key, in, len);
+ priv_key = d2i_EC_PRIVATEKEY(NULL, in, len);
if (priv_key == NULL) {
OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB);
- EC_PRIVATEKEY_free(priv_key);
return NULL;
}
@@ -309,17 +298,12 @@ EC_KEY *d2i_ECPrivateKey(EC_KEY **a, const uint8_t **in, long len) {
OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_MALLOC_FAILURE);
goto err;
}
- if (a) {
- *a = ret;
- }
} else {
ret = *a;
}
if (priv_key->parameters) {
- if (ret->group) {
- EC_GROUP_free(ret->group);
- }
+ EC_GROUP_free(ret->group);
ret->group = ec_asn1_pkparameters2group(priv_key->parameters);
}
@@ -343,9 +327,7 @@ EC_KEY *d2i_ECPrivateKey(EC_KEY **a, const uint8_t **in, long len) {
goto err;
}
- if (ret->pub_key) {
- EC_POINT_free(ret->pub_key);
- }
+ EC_POINT_free(ret->pub_key);
ret->pub_key = EC_POINT_new(ret->group);
if (ret->pub_key == NULL) {
OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB);
@@ -380,22 +362,20 @@ EC_KEY *d2i_ECPrivateKey(EC_KEY **a, const uint8_t **in, long len) {
ret->enc_flag |= EC_PKEY_NO_PUBKEY;
}
+ if (a) {
+ *a = ret;
+ }
ok = 1;
err:
if (!ok) {
- if (ret) {
+ if (a == NULL || *a != ret) {
EC_KEY_free(ret);
}
ret = NULL;
- if (a) {
- *a = ret;
- }
}
- if (priv_key) {
- EC_PRIVATEKEY_free(priv_key);
- }
+ EC_PRIVATEKEY_free(priv_key);
return ret;
}
@@ -419,14 +399,14 @@ int i2d_ECPrivateKey(const EC_KEY *key, uint8_t **outp) {
priv_key->version = key->version;
- buf_len = BN_num_bytes(key->priv_key);
+ buf_len = BN_num_bytes(&key->group->order);
buffer = OPENSSL_malloc(buf_len);
if (buffer == NULL) {
OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_MALLOC_FAILURE);
goto err;
}
- if (!BN_bn2bin(key->priv_key, buffer)) {
+ if (!BN_bn2bin_padded(buffer, buf_len, key->priv_key)) {
OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_BN_LIB);
goto err;
}
@@ -488,12 +468,8 @@ int i2d_ECPrivateKey(const EC_KEY *key, uint8_t **outp) {
ok = 1;
err:
- if (buffer) {
- OPENSSL_free(buffer);
- }
- if (priv_key) {
- EC_PRIVATEKEY_free(priv_key);
- }
+ OPENSSL_free(buffer);
+ EC_PRIVATEKEY_free(priv_key);
return (ok ? ret : 0);
}
@@ -519,18 +495,21 @@ EC_KEY *d2i_ECParameters(EC_KEY **key, const uint8_t **inp, long len) {
OPENSSL_PUT_ERROR(EC, d2i_ECParameters, ERR_R_MALLOC_FAILURE);
return NULL;
}
- if (key) {
- *key = ret;
- }
} else {
ret = *key;
}
if (!d2i_ECPKParameters(&ret->group, inp, len)) {
OPENSSL_PUT_ERROR(EC, d2i_ECParameters, ERR_R_EC_LIB);
+ if (key == NULL || *key == NULL) {
+ EC_KEY_free(ret);
+ }
return NULL;
}
+ if (key) {
+ *key = ret;
+ }
return ret;
}
diff --git a/src/crypto/ec/ec_error.c b/src/crypto/ec/ec_error.c
deleted file mode 100644
index 73807c7..0000000
--- a/src/crypto/ec/ec_error.c
+++ /dev/null
@@ -1,107 +0,0 @@
-/* Copyright (c) 2014, Google Inc.
- *
- * Permission to use, copy, modify, and/or distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
- * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
- * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
- * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
-
-#include <openssl/err.h>
-
-#include <openssl/ec.h>
-
-const ERR_STRING_DATA EC_error_string_data[] = {
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_copy, 0), "EC_GROUP_copy"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_get_curve_GFp, 0), "EC_GROUP_get_curve_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_get_degree, 0), "EC_GROUP_get_degree"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_new_by_curve_name, 0), "EC_GROUP_new_by_curve_name"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_check_key, 0), "EC_KEY_check_key"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_copy, 0), "EC_KEY_copy"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_generate_key, 0), "EC_KEY_generate_key"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_new_method, 0), "EC_KEY_new_method"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_set_public_key_affine_coordinates, 0), "EC_KEY_set_public_key_affine_coordinates"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_add, 0), "EC_POINT_add"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_cmp, 0), "EC_POINT_cmp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_copy, 0), "EC_POINT_copy"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_dbl, 0), "EC_POINT_dbl"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_dup, 0), "EC_POINT_dup"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_get_affine_coordinates_GFp, 0), "EC_POINT_get_affine_coordinates_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_invert, 0), "EC_POINT_invert"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_is_at_infinity, 0), "EC_POINT_is_at_infinity"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_is_on_curve, 0), "EC_POINT_is_on_curve"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_make_affine, 0), "EC_POINT_make_affine"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_new, 0), "EC_POINT_new"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_oct2point, 0), "EC_POINT_oct2point"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_point2oct, 0), "EC_POINT_point2oct"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_affine_coordinates_GFp, 0), "EC_POINT_set_affine_coordinates_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_compressed_coordinates_GFp, 0), "EC_POINT_set_compressed_coordinates_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_to_infinity, 0), "EC_POINT_set_to_infinity"},
- {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTs_make_affine, 0), "EC_POINTs_make_affine"},
- {ERR_PACK(ERR_LIB_EC, EC_F_compute_wNAF, 0), "compute_wNAF"},
- {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECPKParameters, 0), "d2i_ECPKParameters"},
- {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECParameters, 0), "d2i_ECParameters"},
- {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECPrivateKey, 0), "d2i_ECPrivateKey"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_decode, 0), "ec_GFp_mont_field_decode"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_encode, 0), "ec_GFp_mont_field_encode"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_mul, 0), "ec_GFp_mont_field_mul"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_set_to_one, 0), "ec_GFp_mont_field_set_to_one"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_sqr, 0), "ec_GFp_mont_field_sqr"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_group_set_curve, 0), "ec_GFp_mont_group_set_curve"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_group_check_discriminant, 0), "ec_GFp_simple_group_check_discriminant"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_group_set_curve, 0), "ec_GFp_simple_group_set_curve"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_make_affine, 0), "ec_GFp_simple_make_affine"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_oct2point, 0), "ec_GFp_simple_oct2point"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point2oct, 0), "ec_GFp_simple_point2oct"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point_get_affine_coordinates, 0), "ec_GFp_simple_point_get_affine_coordinates"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point_set_affine_coordinates, 0), "ec_GFp_simple_point_set_affine_coordinates"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_points_make_affine, 0), "ec_GFp_simple_points_make_affine"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_set_compressed_coordinates, 0), "ec_GFp_simple_set_compressed_coordinates"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_asn1_group2pkparameters, 0), "ec_asn1_group2pkparameters"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_asn1_pkparameters2group, 0), "ec_asn1_pkparameters2group"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new, 0), "ec_group_new"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new_curve_GFp, 0), "ec_group_new_curve_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new_from_data, 0), "ec_group_new_from_data"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_point_set_Jprojective_coordinates_GFp, 0), "ec_point_set_Jprojective_coordinates_GFp"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_pre_comp_new, 0), "ec_pre_comp_new"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_wNAF_mul, 0), "ec_wNAF_mul"},
- {ERR_PACK(ERR_LIB_EC, EC_F_ec_wNAF_precompute_mult, 0), "ec_wNAF_precompute_mult"},
- {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECPKParameters, 0), "i2d_ECPKParameters"},
- {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECParameters, 0), "i2d_ECParameters"},
- {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECPrivateKey, 0), "i2d_ECPrivateKey"},
- {ERR_PACK(ERR_LIB_EC, EC_F_i2o_ECPublicKey, 0), "i2o_ECPublicKey"},
- {ERR_PACK(ERR_LIB_EC, EC_F_o2i_ECPublicKey, 0), "o2i_ECPublicKey"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_BUFFER_TOO_SMALL), "BUFFER_TOO_SMALL"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_COORDINATES_OUT_OF_RANGE), "COORDINATES_OUT_OF_RANGE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_D2I_ECPKPARAMETERS_FAILURE), "D2I_ECPKPARAMETERS_FAILURE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_EC_GROUP_NEW_BY_NAME_FAILURE), "EC_GROUP_NEW_BY_NAME_FAILURE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_GF2M_NOT_SUPPORTED), "GF2M_NOT_SUPPORTED"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_GROUP2PKPARAMETERS_FAILURE), "GROUP2PKPARAMETERS_FAILURE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_I2D_ECPKPARAMETERS_FAILURE), "I2D_ECPKPARAMETERS_FAILURE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INCOMPATIBLE_OBJECTS), "INCOMPATIBLE_OBJECTS"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_COMPRESSED_POINT), "INVALID_COMPRESSED_POINT"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_COMPRESSION_BIT), "INVALID_COMPRESSION_BIT"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_ENCODING), "INVALID_ENCODING"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_FIELD), "INVALID_FIELD"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_FORM), "INVALID_FORM"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_GROUP_ORDER), "INVALID_GROUP_ORDER"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_PRIVATE_KEY), "INVALID_PRIVATE_KEY"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PARAMETERS), "MISSING_PARAMETERS"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PRIVATE_KEY), "MISSING_PRIVATE_KEY"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_NON_NAMED_CURVE), "NON_NAMED_CURVE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_NOT_INITIALIZED), "NOT_INITIALIZED"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_PKPARAMETERS2GROUP_FAILURE), "PKPARAMETERS2GROUP_FAILURE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_AT_INFINITY), "POINT_AT_INFINITY"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_IS_NOT_ON_CURVE), "POINT_IS_NOT_ON_CURVE"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_SLOT_FULL), "SLOT_FULL"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_GENERATOR), "UNDEFINED_GENERATOR"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_GROUP), "UNKNOWN_GROUP"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_ORDER), "UNKNOWN_ORDER"},
- {ERR_PACK(ERR_LIB_EC, 0, EC_R_WRONG_ORDER), "WRONG_ORDER"},
- {0, NULL},
-};
diff --git a/src/crypto/ec/ec_key.c b/src/crypto/ec/ec_key.c
index 471ea9c..3652ba5 100644
--- a/src/crypto/ec/ec_key.c
+++ b/src/crypto/ec/ec_key.c
@@ -74,10 +74,14 @@
#include <openssl/err.h>
#include <openssl/ex_data.h>
#include <openssl/mem.h>
+#include <openssl/thread.h>
#include "internal.h"
+#include "../internal.h"
+static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT;
+
EC_KEY *EC_KEY_new(void) { return EC_KEY_new_method(NULL); }
EC_KEY *EC_KEY_new_method(const ENGINE *engine) {
@@ -100,7 +104,7 @@ EC_KEY *EC_KEY_new_method(const ENGINE *engine) {
ret->conv_form = POINT_CONVERSION_UNCOMPRESSED;
ret->references = 1;
- if (!CRYPTO_new_ex_data(CRYPTO_EX_INDEX_EC_KEY, ret, &ret->ex_data)) {
+ if (!CRYPTO_new_ex_data(&g_ex_data_class, ret, &ret->ex_data)) {
goto err1;
}
@@ -111,7 +115,7 @@ EC_KEY *EC_KEY_new_method(const ENGINE *engine) {
return ret;
err2:
- CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, ret, &ret->ex_data);
+ CRYPTO_free_ex_data(&g_ex_data_class, ret, &ret->ex_data);
err1:
if (ret->ecdsa_meth) {
METHOD_unref(ret->ecdsa_meth);
@@ -123,6 +127,7 @@ err1:
EC_KEY *EC_KEY_new_by_curve_name(int nid) {
EC_KEY *ret = EC_KEY_new();
if (ret == NULL) {
+ OPENSSL_PUT_ERROR(EC, EC_KEY_new_by_curve_name, ERR_R_MALLOC_FAILURE);
return NULL;
}
ret->group = EC_GROUP_new_by_curve_name(nid);
@@ -149,17 +154,11 @@ void EC_KEY_free(EC_KEY *r) {
METHOD_unref(r->ecdsa_meth);
}
- if (r->group != NULL) {
- EC_GROUP_free(r->group);
- }
- if (r->pub_key != NULL) {
- EC_POINT_free(r->pub_key);
- }
- if (r->priv_key != NULL) {
- BN_clear_free(r->priv_key);
- }
+ EC_GROUP_free(r->group);
+ EC_POINT_free(r->pub_key);
+ BN_clear_free(r->priv_key);
- CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, r, &r->ex_data);
+ CRYPTO_free_ex_data(&g_ex_data_class, r, &r->ex_data);
OPENSSL_cleanse((void *)r, sizeof(EC_KEY));
OPENSSL_free(r);
@@ -170,35 +169,23 @@ EC_KEY *EC_KEY_copy(EC_KEY *dest, const EC_KEY *src) {
OPENSSL_PUT_ERROR(EC, EC_KEY_copy, ERR_R_PASSED_NULL_PARAMETER);
return NULL;
}
- /* copy the parameters */
+ /* Copy the parameters. */
if (src->group) {
/* TODO(fork): duplicating the group seems wasteful. */
- const EC_METHOD *meth = src->group->meth;
- /* clear the old group */
- if (dest->group) {
- EC_GROUP_free(dest->group);
- }
- dest->group = ec_group_new(meth);
+ EC_GROUP_free(dest->group);
+ dest->group = EC_GROUP_dup(src->group);
if (dest->group == NULL) {
return NULL;
}
- if (!EC_GROUP_copy(dest->group, src->group)) {
- return NULL;
- }
}
- /* copy the public key */
+ /* Copy the public key. */
if (src->pub_key && src->group) {
- if (dest->pub_key) {
- EC_POINT_free(dest->pub_key);
- }
- dest->pub_key = EC_POINT_new(src->group);
+ EC_POINT_free(dest->pub_key);
+ dest->pub_key = EC_POINT_dup(src->pub_key, src->group);
if (dest->pub_key == NULL) {
return NULL;
}
- if (!EC_POINT_copy(dest->pub_key, src->pub_key)) {
- return NULL;
- }
}
/* copy the private key */
@@ -214,8 +201,8 @@ EC_KEY *EC_KEY_copy(EC_KEY *dest, const EC_KEY *src) {
}
}
/* copy method/extra data */
- CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, dest, &dest->ex_data);
- if (!CRYPTO_dup_ex_data(CRYPTO_EX_INDEX_EC_KEY, &dest->ex_data,
+ CRYPTO_free_ex_data(&g_ex_data_class, dest, &dest->ex_data);
+ if (!CRYPTO_dup_ex_data(&g_ex_data_class, &dest->ex_data,
&src->ex_data)) {
return NULL;
}
@@ -252,9 +239,7 @@ int EC_KEY_is_opaque(const EC_KEY *key) {
const EC_GROUP *EC_KEY_get0_group(const EC_KEY *key) { return key->group; }
int EC_KEY_set_group(EC_KEY *key, const EC_GROUP *group) {
- if (key->group != NULL) {
- EC_GROUP_free(key->group);
- }
+ EC_GROUP_free(key->group);
/* TODO(fork): duplicating the group seems wasteful but see
* |EC_KEY_set_conv_form|. */
key->group = EC_GROUP_dup(group);
@@ -266,9 +251,7 @@ const BIGNUM *EC_KEY_get0_private_key(const EC_KEY *key) {
}
int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *priv_key) {
- if (key->priv_key) {
- BN_clear_free(key->priv_key);
- }
+ BN_clear_free(key->priv_key);
key->priv_key = BN_dup(priv_key);
return (key->priv_key == NULL) ? 0 : 1;
}
@@ -278,9 +261,7 @@ const EC_POINT *EC_KEY_get0_public_key(const EC_KEY *key) {
}
int EC_KEY_set_public_key(EC_KEY *key, const EC_POINT *pub_key) {
- if (key->pub_key != NULL) {
- EC_POINT_free(key->pub_key);
- }
+ EC_POINT_free(key->pub_key);
key->pub_key = EC_POINT_dup(pub_key, key->group);
return (key->pub_key == NULL) ? 0 : 1;
}
@@ -371,10 +352,8 @@ int EC_KEY_check_key(const EC_KEY *eckey) {
ok = 1;
err:
- if (ctx != NULL)
- BN_CTX_free(ctx);
- if (point != NULL)
- EC_POINT_free(point);
+ BN_CTX_free(ctx);
+ EC_POINT_free(point);
return ok;
}
@@ -425,10 +404,8 @@ int EC_KEY_set_public_key_affine_coordinates(EC_KEY *key, BIGNUM *x,
ok = 1;
err:
- if (ctx)
- BN_CTX_free(ctx);
- if (point)
- EC_POINT_free(point);
+ BN_CTX_free(ctx);
+ EC_POINT_free(point);
return ok;
}
@@ -489,22 +466,26 @@ int EC_KEY_generate_key(EC_KEY *eckey) {
ok = 1;
err:
- if (order)
- BN_free(order);
- if (pub_key != NULL && eckey->pub_key == NULL)
+ BN_free(order);
+ if (eckey->pub_key == NULL) {
EC_POINT_free(pub_key);
- if (priv_key != NULL && eckey->priv_key == NULL)
+ }
+ if (eckey->priv_key == NULL) {
BN_free(priv_key);
- if (ctx != NULL)
- BN_CTX_free(ctx);
+ }
+ BN_CTX_free(ctx);
return ok;
}
int EC_KEY_get_ex_new_index(long argl, void *argp, CRYPTO_EX_new *new_func,
CRYPTO_EX_dup *dup_func,
CRYPTO_EX_free *free_func) {
- return CRYPTO_get_ex_new_index(CRYPTO_EX_INDEX_EC_KEY, argl, argp, new_func,
- dup_func, free_func);
+ int index;
+ if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp, new_func,
+ dup_func, free_func)) {
+ return -1;
+ }
+ return index;
}
int EC_KEY_set_ex_data(EC_KEY *d, int idx, void *arg) {
diff --git a/src/crypto/ec/ec_montgomery.c b/src/crypto/ec/ec_montgomery.c
index ab04556..74dbc6c 100644
--- a/src/crypto/ec/ec_montgomery.c
+++ b/src/crypto/ec/ec_montgomery.c
@@ -121,68 +121,58 @@ int ec_GFp_mont_group_init(EC_GROUP *group) {
int ok;
ok = ec_GFp_simple_group_init(group);
- group->field_data1 = NULL;
- group->field_data2 = NULL;
+ group->mont = NULL;
+ group->one = NULL;
return ok;
}
void ec_GFp_mont_group_finish(EC_GROUP *group) {
- if (group->field_data1 != NULL) {
- BN_MONT_CTX_free(group->field_data1);
- group->field_data1 = NULL;
- }
- if (group->field_data2 != NULL) {
- BN_free(group->field_data2);
- group->field_data2 = NULL;
- }
+ BN_MONT_CTX_free(group->mont);
+ group->mont = NULL;
+ BN_free(group->one);
+ group->one = NULL;
ec_GFp_simple_group_finish(group);
}
void ec_GFp_mont_group_clear_finish(EC_GROUP *group) {
- if (group->field_data1 != NULL) {
- BN_MONT_CTX_free(group->field_data1);
- group->field_data1 = NULL;
- }
- if (group->field_data2 != NULL) {
- BN_clear_free(group->field_data2);
- group->field_data2 = NULL;
- }
+ BN_MONT_CTX_free(group->mont);
+ group->mont = NULL;
+ BN_clear_free(group->one);
+ group->one = NULL;
ec_GFp_simple_group_clear_finish(group);
}
int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
- if (dest->field_data1 != NULL) {
- BN_MONT_CTX_free(dest->field_data1);
- dest->field_data1 = NULL;
- }
- if (dest->field_data2 != NULL) {
- BN_clear_free(dest->field_data2);
- dest->field_data2 = NULL;
- }
+ BN_MONT_CTX_free(dest->mont);
+ dest->mont = NULL;
+ BN_clear_free(dest->one);
+ dest->one = NULL;
- if (!ec_GFp_simple_group_copy(dest, src))
+ if (!ec_GFp_simple_group_copy(dest, src)) {
return 0;
+ }
- if (src->field_data1 != NULL) {
- dest->field_data1 = BN_MONT_CTX_new();
- if (dest->field_data1 == NULL)
+ if (src->mont != NULL) {
+ dest->mont = BN_MONT_CTX_new();
+ if (dest->mont == NULL) {
return 0;
- if (!BN_MONT_CTX_copy(dest->field_data1, src->field_data1))
+ }
+ if (!BN_MONT_CTX_copy(dest->mont, src->mont)) {
goto err;
+ }
}
- if (src->field_data2 != NULL) {
- dest->field_data2 = BN_dup(src->field_data2);
- if (dest->field_data2 == NULL)
+ if (src->one != NULL) {
+ dest->one = BN_dup(src->one);
+ if (dest->one == NULL) {
goto err;
+ }
}
return 1;
err:
- if (dest->field_data1 != NULL) {
- BN_MONT_CTX_free(dest->field_data1);
- dest->field_data1 = NULL;
- }
+ BN_MONT_CTX_free(dest->mont);
+ dest->mont = NULL;
return 0;
}
@@ -193,104 +183,101 @@ int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p,
BIGNUM *one = NULL;
int ret = 0;
- if (group->field_data1 != NULL) {
- BN_MONT_CTX_free(group->field_data1);
- group->field_data1 = NULL;
- }
- if (group->field_data2 != NULL) {
- BN_free(group->field_data2);
- group->field_data2 = NULL;
- }
+ BN_MONT_CTX_free(group->mont);
+ group->mont = NULL;
+ BN_free(group->one);
+ group->one = NULL;
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
mont = BN_MONT_CTX_new();
- if (mont == NULL)
+ if (mont == NULL) {
goto err;
+ }
if (!BN_MONT_CTX_set(mont, p, ctx)) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_group_set_curve, ERR_R_BN_LIB);
goto err;
}
one = BN_new();
- if (one == NULL)
- goto err;
- if (!BN_to_montgomery(one, BN_value_one(), mont, ctx))
+ if (one == NULL || !BN_to_montgomery(one, BN_value_one(), mont, ctx)) {
goto err;
+ }
- group->field_data1 = mont;
+ group->mont = mont;
mont = NULL;
- group->field_data2 = one;
+ group->one = one;
one = NULL;
ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
if (!ret) {
- BN_MONT_CTX_free(group->field_data1);
- group->field_data1 = NULL;
- BN_free(group->field_data2);
- group->field_data2 = NULL;
+ BN_MONT_CTX_free(group->mont);
+ group->mont = NULL;
+ BN_free(group->one);
+ group->one = NULL;
}
err:
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- if (mont != NULL)
- BN_MONT_CTX_free(mont);
+ BN_CTX_free(new_ctx);
+ BN_MONT_CTX_free(mont);
+ BN_free(one);
return ret;
}
int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
const BIGNUM *b, BN_CTX *ctx) {
- if (group->field_data1 == NULL) {
+ if (group->mont == NULL) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_mul, EC_R_NOT_INITIALIZED);
return 0;
}
- return BN_mod_mul_montgomery(r, a, b, group->field_data1, ctx);
+ return BN_mod_mul_montgomery(r, a, b, group->mont, ctx);
}
int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
BN_CTX *ctx) {
- if (group->field_data1 == NULL) {
+ if (group->mont == NULL) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_sqr, EC_R_NOT_INITIALIZED);
return 0;
}
- return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx);
+ return BN_mod_mul_montgomery(r, a, a, group->mont, ctx);
}
int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
BN_CTX *ctx) {
- if (group->field_data1 == NULL) {
+ if (group->mont == NULL) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_encode, EC_R_NOT_INITIALIZED);
return 0;
}
- return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data1, ctx);
+ return BN_to_montgomery(r, a, group->mont, ctx);
}
int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
BN_CTX *ctx) {
- if (group->field_data1 == NULL) {
+ if (group->mont == NULL) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_decode, EC_R_NOT_INITIALIZED);
return 0;
}
- return BN_from_montgomery(r, a, group->field_data1, ctx);
+ return BN_from_montgomery(r, a, group->mont, ctx);
}
int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r,
BN_CTX *ctx) {
- if (group->field_data2 == NULL) {
+ if (group->one == NULL) {
OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_set_to_one, EC_R_NOT_INITIALIZED);
return 0;
}
- if (!BN_copy(r, group->field_data2))
+ if (!BN_copy(r, group->one)) {
return 0;
+ }
return 1;
}
diff --git a/src/crypto/ec/ec_test.c b/src/crypto/ec/ec_test.c
deleted file mode 100644
index 8d53f87..0000000
--- a/src/crypto/ec/ec_test.c
+++ /dev/null
@@ -1,124 +0,0 @@
-/* Copyright (c) 2014, Google Inc.
- *
- * Permission to use, copy, modify, and/or distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
- * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
- * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
- * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
-
-#include <stdio.h>
-#include <string.h>
-
-#include <openssl/bio.h>
-#include <openssl/crypto.h>
-#include <openssl/ec_key.h>
-#include <openssl/err.h>
-
-#include "internal.h"
-
-
-static const uint8_t kECKeyWithoutPublic[] = {
- 0x30, 0x31, 0x02, 0x01, 0x01, 0x04, 0x20, 0xc6, 0xc1, 0xaa, 0xda, 0x15, 0xb0,
- 0x76, 0x61, 0xf8, 0x14, 0x2c, 0x6c, 0xaf, 0x0f, 0xdb, 0x24, 0x1a, 0xff, 0x2e,
- 0xfe, 0x46, 0xc0, 0x93, 0x8b, 0x74, 0xf2, 0xbc, 0xc5, 0x30, 0x52, 0xb0, 0x77,
- 0xa0, 0x0a, 0x06, 0x08, 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07,
-};
-
-int test_d2i_ECPrivateKey(void) {
- int len, ret = 0;
- uint8_t *out = NULL, *outp;
- const uint8_t *inp;
- EC_KEY *key = NULL;
- BIGNUM *x = NULL, *y = NULL;
- const EC_POINT *public;
- char *x_hex = NULL, *y_hex = NULL;
-
- inp = kECKeyWithoutPublic;
- key = d2i_ECPrivateKey(NULL, &inp, sizeof(kECKeyWithoutPublic));
-
- if (key == NULL || inp != kECKeyWithoutPublic + sizeof(kECKeyWithoutPublic)) {
- fprintf(stderr, "Failed to parse private key.\n");
- BIO_print_errors_fp(stderr);
- goto out;
- }
-
- len = i2d_ECPrivateKey(key, NULL);
- out = malloc(len);
- outp = out;
- if (len != i2d_ECPrivateKey(key, &outp)) {
- fprintf(stderr, "Failed to serialize private key.\n");
- BIO_print_errors_fp(stderr);
- goto out;
- }
-
- if (0 != memcmp(out, kECKeyWithoutPublic, len)) {
- fprintf(stderr, "Serialisation of key doesn't match original.\n");
- goto out;
- }
-
- public = EC_KEY_get0_public_key(key);
- if (public == NULL) {
- fprintf(stderr, "Public key missing.\n");
- goto out;
- }
-
- x = BN_new();
- y = BN_new();
- if (x == NULL || y == NULL) {
- goto out;
- }
- if (!EC_POINT_get_affine_coordinates_GFp(EC_KEY_get0_group(key), public, x, y,
- NULL)) {
- fprintf(stderr, "Failed to get public key in affine coordinates.\n");
- goto out;
- }
- x_hex = BN_bn2hex(x);
- y_hex = BN_bn2hex(y);
- if (0 != strcmp(x_hex, "c81561ecf2e54edefe6617db1c7a34a70744ddb261f269b83dacfcd2ade5a681") ||
- 0 != strcmp(y_hex, "e0e2afa3f9b6abe4c698ef6495f1be49a3196c5056acb3763fe4507eec596e88")) {
- fprintf(stderr, "Incorrect public key: %s %s\n", x_hex, y_hex);
- goto out;
- }
-
- ret = 1;
-
-out:
- if (key != NULL) {
- EC_KEY_free(key);
- }
- if (out != NULL) {
- free(out);
- }
- if (x != NULL) {
- BN_free(x);
- }
- if (y != NULL) {
- BN_free(y);
- }
- if (x_hex != NULL) {
- OPENSSL_free(x_hex);
- }
- if (y_hex != NULL) {
- OPENSSL_free(y_hex);
- }
- return ret;
-}
-
-int main(void) {
- CRYPTO_library_init();
- ERR_load_crypto_strings();
-
- if (!test_d2i_ECPrivateKey()) {
- fprintf(stderr, "failed\n");
- return 1;
- }
-
- printf("PASS\n");
- return 0;
-}
diff --git a/src/crypto/ec/ec_test.cc b/src/crypto/ec/ec_test.cc
new file mode 100644
index 0000000..74685eb
--- /dev/null
+++ b/src/crypto/ec/ec_test.cc
@@ -0,0 +1,185 @@
+/* Copyright (c) 2014, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <stdio.h>
+#include <string.h>
+
+#include <vector>
+
+#include <openssl/crypto.h>
+#include <openssl/ec_key.h>
+#include <openssl/err.h>
+#include <openssl/mem.h>
+
+#include "../test/scoped_types.h"
+#include "../test/stl_compat.h"
+
+
+// kECKeyWithoutPublic is an ECPrivateKey with the optional publicKey field
+// omitted.
+static const uint8_t kECKeyWithoutPublic[] = {
+ 0x30, 0x31, 0x02, 0x01, 0x01, 0x04, 0x20, 0xc6, 0xc1, 0xaa, 0xda, 0x15, 0xb0,
+ 0x76, 0x61, 0xf8, 0x14, 0x2c, 0x6c, 0xaf, 0x0f, 0xdb, 0x24, 0x1a, 0xff, 0x2e,
+ 0xfe, 0x46, 0xc0, 0x93, 0x8b, 0x74, 0xf2, 0xbc, 0xc5, 0x30, 0x52, 0xb0, 0x77,
+ 0xa0, 0x0a, 0x06, 0x08, 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07,
+};
+
+// kECKeyMissingZeros is an ECPrivateKey containing a degenerate P-256 key where
+// the private key is one. The private key is incorrectly encoded without zero
+// padding.
+static const uint8_t kECKeyMissingZeros[] = {
+ 0x30, 0x58, 0x02, 0x01, 0x01, 0x04, 0x01, 0x01, 0xa0, 0x0a, 0x06, 0x08, 0x2a,
+ 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07, 0xa1, 0x44, 0x03, 0x42, 0x00, 0x04,
+ 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, 0xf8, 0xbc, 0xe6, 0xe5, 0x63,
+ 0xa4, 0x40, 0xf2, 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0, 0xf4, 0xa1,
+ 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96, 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f,
+ 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57,
+ 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5,
+};
+
+// kECKeyMissingZeros is an ECPrivateKey containing a degenerate P-256 key where
+// the private key is one. The private key is encoded with the required zero
+// padding.
+static const uint8_t kECKeyWithZeros[] = {
+ 0x30, 0x77, 0x02, 0x01, 0x01, 0x04, 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
+ 0xa0, 0x0a, 0x06, 0x08, 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07, 0xa1,
+ 0x44, 0x03, 0x42, 0x00, 0x04, 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
+ 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2, 0x77, 0x03, 0x7d, 0x81, 0x2d,
+ 0xeb, 0x33, 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96, 0x4f, 0xe3,
+ 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e,
+ 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68,
+ 0x37, 0xbf, 0x51, 0xf5,
+};
+
+// DecodeECPrivateKey decodes |in| as an ECPrivateKey structure and returns the
+// result or nullptr on error.
+static ScopedEC_KEY DecodeECPrivateKey(const uint8_t *in, size_t in_len) {
+ const uint8_t *inp = in;
+ ScopedEC_KEY ret(d2i_ECPrivateKey(NULL, &inp, in_len));
+ if (!ret || inp != in + in_len) {
+ return nullptr;
+ }
+ return ret;
+}
+
+// EncodeECPrivateKey encodes |key| as an ECPrivateKey structure into |*out|. It
+// returns true on success or false on error.
+static bool EncodeECPrivateKey(std::vector<uint8_t> *out, EC_KEY *key) {
+ int len = i2d_ECPrivateKey(key, NULL);
+ out->resize(len);
+ uint8_t *outp = bssl::vector_data(out);
+ return i2d_ECPrivateKey(key, &outp) == len;
+}
+
+bool Testd2i_ECPrivateKey() {
+ ScopedEC_KEY key = DecodeECPrivateKey(kECKeyWithoutPublic,
+ sizeof(kECKeyWithoutPublic));
+ if (!key) {
+ fprintf(stderr, "Failed to parse private key.\n");
+ ERR_print_errors_fp(stderr);
+ return false;
+ }
+
+ std::vector<uint8_t> out;
+ if (!EncodeECPrivateKey(&out, key.get())) {
+ fprintf(stderr, "Failed to serialize private key.\n");
+ ERR_print_errors_fp(stderr);
+ return false;
+ }
+
+ if (std::vector<uint8_t>(kECKeyWithoutPublic,
+ kECKeyWithoutPublic + sizeof(kECKeyWithoutPublic)) !=
+ out) {
+ fprintf(stderr, "Serialisation of key doesn't match original.\n");
+ return false;
+ }
+
+ const EC_POINT *pub_key = EC_KEY_get0_public_key(key.get());
+ if (pub_key == NULL) {
+ fprintf(stderr, "Public key missing.\n");
+ return false;
+ }
+
+ ScopedBIGNUM x(BN_new());
+ ScopedBIGNUM y(BN_new());
+ if (!x || !y) {
+ return false;
+ }
+ if (!EC_POINT_get_affine_coordinates_GFp(EC_KEY_get0_group(key.get()),
+ pub_key, x.get(), y.get(), NULL)) {
+ fprintf(stderr, "Failed to get public key in affine coordinates.\n");
+ return false;
+ }
+ ScopedOpenSSLString x_hex(BN_bn2hex(x.get()));
+ ScopedOpenSSLString y_hex(BN_bn2hex(y.get()));
+ if (0 != strcmp(
+ x_hex.get(),
+ "c81561ecf2e54edefe6617db1c7a34a70744ddb261f269b83dacfcd2ade5a681") ||
+ 0 != strcmp(
+ y_hex.get(),
+ "e0e2afa3f9b6abe4c698ef6495f1be49a3196c5056acb3763fe4507eec596e88")) {
+ fprintf(stderr, "Incorrect public key: %s %s\n", x_hex.get(), y_hex.get());
+ return false;
+ }
+
+ return true;
+}
+
+static bool TestZeroPadding() {
+ // Check that the correct encoding round-trips.
+ ScopedEC_KEY key = DecodeECPrivateKey(kECKeyWithZeros,
+ sizeof(kECKeyWithZeros));
+ std::vector<uint8_t> out;
+ if (!key || !EncodeECPrivateKey(&out, key.get())) {
+ ERR_print_errors_fp(stderr);
+ return false;
+ }
+
+ if (std::vector<uint8_t>(kECKeyWithZeros,
+ kECKeyWithZeros + sizeof(kECKeyWithZeros)) != out) {
+ fprintf(stderr, "Serialisation of key was incorrect.\n");
+ return false;
+ }
+
+ // Keys without leading zeros also parse, but they encode correctly.
+ key = DecodeECPrivateKey(kECKeyMissingZeros, sizeof(kECKeyMissingZeros));
+ if (!key || !EncodeECPrivateKey(&out, key.get())) {
+ ERR_print_errors_fp(stderr);
+ return false;
+ }
+
+ if (std::vector<uint8_t>(kECKeyWithZeros,
+ kECKeyWithZeros + sizeof(kECKeyWithZeros)) != out) {
+ fprintf(stderr, "Serialisation of key was incorrect.\n");
+ return false;
+ }
+
+ return true;
+}
+
+int main(void) {
+ CRYPTO_library_init();
+ ERR_load_crypto_strings();
+
+ if (!Testd2i_ECPrivateKey() ||
+ !TestZeroPadding()) {
+ fprintf(stderr, "failed\n");
+ return 1;
+ }
+
+ printf("PASS\n");
+ return 0;
+}
diff --git a/src/crypto/ec/internal.h b/src/crypto/ec/internal.h
index da116c4..0a8bf24 100644
--- a/src/crypto/ec/internal.h
+++ b/src/crypto/ec/internal.h
@@ -81,8 +81,6 @@ extern "C" {
/* Use default functions for poin2oct, oct2point and compressed coordinates */
#define EC_FLAGS_DEFAULT_OCT 0x1
-typedef struct ec_method_st EC_METHOD;
-
struct ec_method_st {
/* Various method flags */
int flags;
@@ -205,35 +203,14 @@ struct ec_group_st {
/* The following members are handled by the method functions,
* even if they appear generic */
- BIGNUM field; /* Field specification.
- * For curves over GF(p), this is the modulus;
- * for curves over GF(2^m), this is the
- * irreducible polynomial defining the field. */
-
- int poly[6]; /* Field specification for curves over GF(2^m).
- * The irreducible f(t) is then of the form:
- * t^poly[0] + t^poly[1] + ... + t^poly[k]
- * where m = poly[0] > poly[1] > ... > poly[k] = 0.
- * The array is terminated with poly[k+1]=-1.
- * All elliptic curve irreducibles have at most 5
- * non-zero terms. */
-
- BIGNUM a, b; /* Curve coefficients.
- * (Here the assumption is that BIGNUMs can be used
- * or abused for all kinds of fields, not just GF(p).)
- * For characteristic > 3, the curve is defined
- * by a Weierstrass equation of the form
- * y^2 = x^3 + a*x + b.
- * For characteristic 2, the curve is defined by
- * an equation of the form
- * y^2 + x*y = x^3 + a*x^2 + b. */
+ BIGNUM field; /* For curves over GF(p), this is the modulus. */
+
+ BIGNUM a, b; /* Curve coefficients. */
int a_is_minus3; /* enable optimized point arithmetics for special case */
- void *field_data1; /* method-specific (e.g., Montgomery structure) */
- void *field_data2; /* method-specific */
- int (*field_mod_func)(BIGNUM *, const BIGNUM *, const BIGNUM *,
- BN_CTX *); /* method-specific */
+ BN_MONT_CTX *mont; /* Montgomery structure. */
+ BIGNUM *one; /* The value one */
} /* EC_GROUP */;
struct ec_point_st {
@@ -250,6 +227,7 @@ struct ec_point_st {
} /* EC_POINT */;
EC_GROUP *ec_group_new(const EC_METHOD *meth);
+int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src);
int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
@@ -329,6 +307,19 @@ int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
const BIGNUM *y, const BIGNUM *z,
BN_CTX *ctx);
+void ec_GFp_nistp_points_make_affine_internal(
+ size_t num, void *point_array, size_t felem_size, void *tmp_felems,
+ void (*felem_one)(void *out), int (*felem_is_zero)(const void *in),
+ void (*felem_assign)(void *out, const void *in),
+ void (*felem_square)(void *out, const void *in),
+ void (*felem_mul)(void *out, const void *in1, const void *in2),
+ void (*felem_inv)(void *out, const void *in),
+ void (*felem_contract)(void *out, const void *in));
+
+void ec_GFp_nistp_recode_scalar_bits(uint8_t *sign, uint8_t *digit, uint8_t in);
+
+const EC_METHOD *EC_GFp_nistp256_method(void);
+
struct ec_key_st {
int version;
diff --git a/src/crypto/ec/oct.c b/src/crypto/ec/oct.c
index c4729ef..816a42f 100644
--- a/src/crypto/ec/oct.c
+++ b/src/crypto/ec/oct.c
@@ -164,18 +164,14 @@ static size_t ec_GFp_simple_point2oct(const EC_GROUP *group,
if (used_ctx) {
BN_CTX_end(ctx);
}
- if (new_ctx != NULL) {
- BN_CTX_free(new_ctx);
- }
+ BN_CTX_free(new_ctx);
return ret;
err:
if (used_ctx) {
BN_CTX_end(ctx);
}
- if (new_ctx != NULL) {
- BN_CTX_free(new_ctx);
- }
+ BN_CTX_free(new_ctx);
return 0;
}
@@ -227,40 +223,46 @@ static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
- if (y == NULL)
+ if (y == NULL) {
goto err;
+ }
- if (!BN_bin2bn(buf + 1, field_len, x))
+ if (!BN_bin2bn(buf + 1, field_len, x)) {
goto err;
+ }
if (BN_ucmp(x, &group->field) >= 0) {
OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
goto err;
}
if (form == POINT_CONVERSION_COMPRESSED) {
- if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx))
+ if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) {
goto err;
+ }
} else {
- if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
+ if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) {
goto err;
+ }
if (BN_ucmp(y, &group->field) >= 0) {
OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
goto err;
}
- if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
+ if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
goto err;
+ }
}
- if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
- {
+ /* test required by X9.62 */
+ if (!EC_POINT_is_on_curve(group, point, ctx)) {
OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_POINT_IS_NOT_ON_CURVE);
goto err;
}
@@ -269,8 +271,7 @@ static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -441,15 +442,15 @@ int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
goto err;
}
- if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
+ if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
goto err;
+ }
ret = 1;
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
diff --git a/src/crypto/ec/p256-64.c b/src/crypto/ec/p256-64.c
new file mode 100644
index 0000000..8f824de
--- /dev/null
+++ b/src/crypto/ec/p256-64.c
@@ -0,0 +1,1936 @@
+/* Copyright (c) 2015, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+/* A 64-bit implementation of the NIST P-256 elliptic curve point
+ * multiplication
+ *
+ * OpenSSL integration was taken from Emilia Kasper's work in ecp_nistp224.c.
+ * Otherwise based on Emilia's P224 work, which was inspired by my curve25519
+ * work which got its smarts from Daniel J. Bernstein's work on the same. */
+
+#include <openssl/base.h>
+
+#if defined(OPENSSL_64_BIT) && !defined(OPENSSL_WINDOWS)
+
+#include <openssl/bn.h>
+#include <openssl/ec.h>
+#include <openssl/err.h>
+#include <openssl/mem.h>
+#include <openssl/obj.h>
+
+#include <string.h>
+
+#include "internal.h"
+
+
+typedef uint8_t u8;
+typedef uint64_t u64;
+typedef int64_t s64;
+typedef __uint128_t uint128_t;
+typedef __int128_t int128_t;
+
+/* The underlying field. P256 operates over GF(2^256-2^224+2^192+2^96-1). We
+ * can serialise an element of this field into 32 bytes. We call this an
+ * felem_bytearray. */
+typedef u8 felem_bytearray[32];
+
+/* These are the parameters of P256, taken from FIPS 186-3, page 86. These
+ * values are big-endian. */
+static const felem_bytearray nistp256_curve_params[5] = {
+ {0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, /* p */
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
+ {0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, /* a = -3 */
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xfc}, /* b */
+ {0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7, 0xb3, 0xeb, 0xbd, 0x55,
+ 0x76, 0x98, 0x86, 0xbc, 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
+ 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b},
+ {0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, /* x */
+ 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2, 0x77, 0x03, 0x7d, 0x81,
+ 0x2d, 0xeb, 0x33, 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96},
+ {0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, /* y */
+ 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57,
+ 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5}};
+
+/* The representation of field elements.
+ * ------------------------------------
+ *
+ * We represent field elements with either four 128-bit values, eight 128-bit
+ * values, or four 64-bit values. The field element represented is:
+ * v[0]*2^0 + v[1]*2^64 + v[2]*2^128 + v[3]*2^192 (mod p)
+ * or:
+ * v[0]*2^0 + v[1]*2^64 + v[2]*2^128 + ... + v[8]*2^512 (mod p)
+ *
+ * 128-bit values are called 'limbs'. Since the limbs are spaced only 64 bits
+ * apart, but are 128-bits wide, the most significant bits of each limb overlap
+ * with the least significant bits of the next.
+ *
+ * A field element with four limbs is an 'felem'. One with eight limbs is a
+ * 'longfelem'
+ *
+ * A field element with four, 64-bit values is called a 'smallfelem'. Small
+ * values are used as intermediate values before multiplication. */
+
+#define NLIMBS 4
+
+typedef uint128_t limb;
+typedef limb felem[NLIMBS];
+typedef limb longfelem[NLIMBS * 2];
+typedef u64 smallfelem[NLIMBS];
+
+/* This is the value of the prime as four 64-bit words, little-endian. */
+static const u64 kPrime[4] = {0xfffffffffffffffful, 0xffffffff, 0,
+ 0xffffffff00000001ul};
+static const u64 bottom63bits = 0x7ffffffffffffffful;
+
+/* bin32_to_felem takes a little-endian byte array and converts it into felem
+ * form. This assumes that the CPU is little-endian. */
+static void bin32_to_felem(felem out, const u8 in[32]) {
+ out[0] = *((u64 *)&in[0]);
+ out[1] = *((u64 *)&in[8]);
+ out[2] = *((u64 *)&in[16]);
+ out[3] = *((u64 *)&in[24]);
+}
+
+/* smallfelem_to_bin32 takes a smallfelem and serialises into a little endian,
+ * 32 byte array. This assumes that the CPU is little-endian. */
+static void smallfelem_to_bin32(u8 out[32], const smallfelem in) {
+ *((u64 *)&out[0]) = in[0];
+ *((u64 *)&out[8]) = in[1];
+ *((u64 *)&out[16]) = in[2];
+ *((u64 *)&out[24]) = in[3];
+}
+
+/* To preserve endianness when using BN_bn2bin and BN_bin2bn. */
+static void flip_endian(u8 *out, const u8 *in, unsigned len) {
+ unsigned i;
+ for (i = 0; i < len; ++i) {
+ out[i] = in[len - 1 - i];
+ }
+}
+
+/* BN_to_felem converts an OpenSSL BIGNUM into an felem. */
+static int BN_to_felem(felem out, const BIGNUM *bn) {
+ if (BN_is_negative(bn)) {
+ OPENSSL_PUT_ERROR(EC, BN_to_felem, EC_R_BIGNUM_OUT_OF_RANGE);
+ return 0;
+ }
+
+ felem_bytearray b_out;
+ /* BN_bn2bin eats leading zeroes */
+ memset(b_out, 0, sizeof(b_out));
+ unsigned num_bytes = BN_num_bytes(bn);
+ if (num_bytes > sizeof(b_out)) {
+ OPENSSL_PUT_ERROR(EC, BN_to_felem, EC_R_BIGNUM_OUT_OF_RANGE);
+ return 0;
+ }
+
+ felem_bytearray b_in;
+ num_bytes = BN_bn2bin(bn, b_in);
+ flip_endian(b_out, b_in, num_bytes);
+ bin32_to_felem(out, b_out);
+ return 1;
+}
+
+/* felem_to_BN converts an felem into an OpenSSL BIGNUM. */
+static BIGNUM *smallfelem_to_BN(BIGNUM *out, const smallfelem in) {
+ felem_bytearray b_in, b_out;
+ smallfelem_to_bin32(b_in, in);
+ flip_endian(b_out, b_in, sizeof(b_out));
+ return BN_bin2bn(b_out, sizeof(b_out), out);
+}
+
+/* Field operations. */
+
+static void smallfelem_one(smallfelem out) {
+ out[0] = 1;
+ out[1] = 0;
+ out[2] = 0;
+ out[3] = 0;
+}
+
+static void smallfelem_assign(smallfelem out, const smallfelem in) {
+ out[0] = in[0];
+ out[1] = in[1];
+ out[2] = in[2];
+ out[3] = in[3];
+}
+
+static void felem_assign(felem out, const felem in) {
+ out[0] = in[0];
+ out[1] = in[1];
+ out[2] = in[2];
+ out[3] = in[3];
+}
+
+/* felem_sum sets out = out + in. */
+static void felem_sum(felem out, const felem in) {
+ out[0] += in[0];
+ out[1] += in[1];
+ out[2] += in[2];
+ out[3] += in[3];
+}
+
+/* felem_small_sum sets out = out + in. */
+static void felem_small_sum(felem out, const smallfelem in) {
+ out[0] += in[0];
+ out[1] += in[1];
+ out[2] += in[2];
+ out[3] += in[3];
+}
+
+/* felem_scalar sets out = out * scalar */
+static void felem_scalar(felem out, const u64 scalar) {
+ out[0] *= scalar;
+ out[1] *= scalar;
+ out[2] *= scalar;
+ out[3] *= scalar;
+}
+
+/* longfelem_scalar sets out = out * scalar */
+static void longfelem_scalar(longfelem out, const u64 scalar) {
+ out[0] *= scalar;
+ out[1] *= scalar;
+ out[2] *= scalar;
+ out[3] *= scalar;
+ out[4] *= scalar;
+ out[5] *= scalar;
+ out[6] *= scalar;
+ out[7] *= scalar;
+}
+
+#define two105m41m9 (((limb)1) << 105) - (((limb)1) << 41) - (((limb)1) << 9)
+#define two105 (((limb)1) << 105)
+#define two105m41p9 (((limb)1) << 105) - (((limb)1) << 41) + (((limb)1) << 9)
+
+/* zero105 is 0 mod p */
+static const felem zero105 = {two105m41m9, two105, two105m41p9, two105m41p9};
+
+/* smallfelem_neg sets |out| to |-small|
+ * On exit:
+ * out[i] < out[i] + 2^105 */
+static void smallfelem_neg(felem out, const smallfelem small) {
+ /* In order to prevent underflow, we subtract from 0 mod p. */
+ out[0] = zero105[0] - small[0];
+ out[1] = zero105[1] - small[1];
+ out[2] = zero105[2] - small[2];
+ out[3] = zero105[3] - small[3];
+}
+
+/* felem_diff subtracts |in| from |out|
+ * On entry:
+ * in[i] < 2^104
+ * On exit:
+ * out[i] < out[i] + 2^105. */
+static void felem_diff(felem out, const felem in) {
+ /* In order to prevent underflow, we add 0 mod p before subtracting. */
+ out[0] += zero105[0];
+ out[1] += zero105[1];
+ out[2] += zero105[2];
+ out[3] += zero105[3];
+
+ out[0] -= in[0];
+ out[1] -= in[1];
+ out[2] -= in[2];
+ out[3] -= in[3];
+}
+
+#define two107m43m11 (((limb)1) << 107) - (((limb)1) << 43) - (((limb)1) << 11)
+#define two107 (((limb)1) << 107)
+#define two107m43p11 (((limb)1) << 107) - (((limb)1) << 43) + (((limb)1) << 11)
+
+/* zero107 is 0 mod p */
+static const felem zero107 = {two107m43m11, two107, two107m43p11, two107m43p11};
+
+/* An alternative felem_diff for larger inputs |in|
+ * felem_diff_zero107 subtracts |in| from |out|
+ * On entry:
+ * in[i] < 2^106
+ * On exit:
+ * out[i] < out[i] + 2^107. */
+static void felem_diff_zero107(felem out, const felem in) {
+ /* In order to prevent underflow, we add 0 mod p before subtracting. */
+ out[0] += zero107[0];
+ out[1] += zero107[1];
+ out[2] += zero107[2];
+ out[3] += zero107[3];
+
+ out[0] -= in[0];
+ out[1] -= in[1];
+ out[2] -= in[2];
+ out[3] -= in[3];
+}
+
+/* longfelem_diff subtracts |in| from |out|
+ * On entry:
+ * in[i] < 7*2^67
+ * On exit:
+ * out[i] < out[i] + 2^70 + 2^40. */
+static void longfelem_diff(longfelem out, const longfelem in) {
+ static const limb two70m8p6 =
+ (((limb)1) << 70) - (((limb)1) << 8) + (((limb)1) << 6);
+ static const limb two70p40 = (((limb)1) << 70) + (((limb)1) << 40);
+ static const limb two70 = (((limb)1) << 70);
+ static const limb two70m40m38p6 = (((limb)1) << 70) - (((limb)1) << 40) -
+ (((limb)1) << 38) + (((limb)1) << 6);
+ static const limb two70m6 = (((limb)1) << 70) - (((limb)1) << 6);
+
+ /* add 0 mod p to avoid underflow */
+ out[0] += two70m8p6;
+ out[1] += two70p40;
+ out[2] += two70;
+ out[3] += two70m40m38p6;
+ out[4] += two70m6;
+ out[5] += two70m6;
+ out[6] += two70m6;
+ out[7] += two70m6;
+
+ /* in[i] < 7*2^67 < 2^70 - 2^40 - 2^38 + 2^6 */
+ out[0] -= in[0];
+ out[1] -= in[1];
+ out[2] -= in[2];
+ out[3] -= in[3];
+ out[4] -= in[4];
+ out[5] -= in[5];
+ out[6] -= in[6];
+ out[7] -= in[7];
+}
+
+#define two64m0 (((limb)1) << 64) - 1
+#define two110p32m0 (((limb)1) << 110) + (((limb)1) << 32) - 1
+#define two64m46 (((limb)1) << 64) - (((limb)1) << 46)
+#define two64m32 (((limb)1) << 64) - (((limb)1) << 32)
+
+/* zero110 is 0 mod p. */
+static const felem zero110 = {two64m0, two110p32m0, two64m46, two64m32};
+
+/* felem_shrink converts an felem into a smallfelem. The result isn't quite
+ * minimal as the value may be greater than p.
+ *
+ * On entry:
+ * in[i] < 2^109
+ * On exit:
+ * out[i] < 2^64. */
+static void felem_shrink(smallfelem out, const felem in) {
+ felem tmp;
+ u64 a, b, mask;
+ s64 high, low;
+ static const u64 kPrime3Test = 0x7fffffff00000001ul; /* 2^63 - 2^32 + 1 */
+
+ /* Carry 2->3 */
+ tmp[3] = zero110[3] + in[3] + ((u64)(in[2] >> 64));
+ /* tmp[3] < 2^110 */
+
+ tmp[2] = zero110[2] + (u64)in[2];
+ tmp[0] = zero110[0] + in[0];
+ tmp[1] = zero110[1] + in[1];
+ /* tmp[0] < 2**110, tmp[1] < 2^111, tmp[2] < 2**65 */
+
+ /* We perform two partial reductions where we eliminate the high-word of
+ * tmp[3]. We don't update the other words till the end. */
+ a = tmp[3] >> 64; /* a < 2^46 */
+ tmp[3] = (u64)tmp[3];
+ tmp[3] -= a;
+ tmp[3] += ((limb)a) << 32;
+ /* tmp[3] < 2^79 */
+
+ b = a;
+ a = tmp[3] >> 64; /* a < 2^15 */
+ b += a; /* b < 2^46 + 2^15 < 2^47 */
+ tmp[3] = (u64)tmp[3];
+ tmp[3] -= a;
+ tmp[3] += ((limb)a) << 32;
+ /* tmp[3] < 2^64 + 2^47 */
+
+ /* This adjusts the other two words to complete the two partial
+ * reductions. */
+ tmp[0] += b;
+ tmp[1] -= (((limb)b) << 32);
+
+ /* In order to make space in tmp[3] for the carry from 2 -> 3, we
+ * conditionally subtract kPrime if tmp[3] is large enough. */
+ high = tmp[3] >> 64;
+ /* As tmp[3] < 2^65, high is either 1 or 0 */
+ high <<= 63;
+ high >>= 63;
+ /* high is:
+ * all ones if the high word of tmp[3] is 1
+ * all zeros if the high word of tmp[3] if 0 */
+ low = tmp[3];
+ mask = low >> 63;
+ /* mask is:
+ * all ones if the MSB of low is 1
+ * all zeros if the MSB of low if 0 */
+ low &= bottom63bits;
+ low -= kPrime3Test;
+ /* if low was greater than kPrime3Test then the MSB is zero */
+ low = ~low;
+ low >>= 63;
+ /* low is:
+ * all ones if low was > kPrime3Test
+ * all zeros if low was <= kPrime3Test */
+ mask = (mask & low) | high;
+ tmp[0] -= mask & kPrime[0];
+ tmp[1] -= mask & kPrime[1];
+ /* kPrime[2] is zero, so omitted */
+ tmp[3] -= mask & kPrime[3];
+ /* tmp[3] < 2**64 - 2**32 + 1 */
+
+ tmp[1] += ((u64)(tmp[0] >> 64));
+ tmp[0] = (u64)tmp[0];
+ tmp[2] += ((u64)(tmp[1] >> 64));
+ tmp[1] = (u64)tmp[1];
+ tmp[3] += ((u64)(tmp[2] >> 64));
+ tmp[2] = (u64)tmp[2];
+ /* tmp[i] < 2^64 */
+
+ out[0] = tmp[0];
+ out[1] = tmp[1];
+ out[2] = tmp[2];
+ out[3] = tmp[3];
+}
+
+/* smallfelem_expand converts a smallfelem to an felem */
+static void smallfelem_expand(felem out, const smallfelem in) {
+ out[0] = in[0];
+ out[1] = in[1];
+ out[2] = in[2];
+ out[3] = in[3];
+}
+
+/* smallfelem_square sets |out| = |small|^2
+ * On entry:
+ * small[i] < 2^64
+ * On exit:
+ * out[i] < 7 * 2^64 < 2^67 */
+static void smallfelem_square(longfelem out, const smallfelem small) {
+ limb a;
+ u64 high, low;
+
+ a = ((uint128_t)small[0]) * small[0];
+ low = a;
+ high = a >> 64;
+ out[0] = low;
+ out[1] = high;
+
+ a = ((uint128_t)small[0]) * small[1];
+ low = a;
+ high = a >> 64;
+ out[1] += low;
+ out[1] += low;
+ out[2] = high;
+
+ a = ((uint128_t)small[0]) * small[2];
+ low = a;
+ high = a >> 64;
+ out[2] += low;
+ out[2] *= 2;
+ out[3] = high;
+
+ a = ((uint128_t)small[0]) * small[3];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[4] = high;
+
+ a = ((uint128_t)small[1]) * small[2];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[3] *= 2;
+ out[4] += high;
+
+ a = ((uint128_t)small[1]) * small[1];
+ low = a;
+ high = a >> 64;
+ out[2] += low;
+ out[3] += high;
+
+ a = ((uint128_t)small[1]) * small[3];
+ low = a;
+ high = a >> 64;
+ out[4] += low;
+ out[4] *= 2;
+ out[5] = high;
+
+ a = ((uint128_t)small[2]) * small[3];
+ low = a;
+ high = a >> 64;
+ out[5] += low;
+ out[5] *= 2;
+ out[6] = high;
+ out[6] += high;
+
+ a = ((uint128_t)small[2]) * small[2];
+ low = a;
+ high = a >> 64;
+ out[4] += low;
+ out[5] += high;
+
+ a = ((uint128_t)small[3]) * small[3];
+ low = a;
+ high = a >> 64;
+ out[6] += low;
+ out[7] = high;
+}
+
+/*felem_square sets |out| = |in|^2
+ * On entry:
+ * in[i] < 2^109
+ * On exit:
+ * out[i] < 7 * 2^64 < 2^67. */
+static void felem_square(longfelem out, const felem in) {
+ u64 small[4];
+ felem_shrink(small, in);
+ smallfelem_square(out, small);
+}
+
+/* smallfelem_mul sets |out| = |small1| * |small2|
+ * On entry:
+ * small1[i] < 2^64
+ * small2[i] < 2^64
+ * On exit:
+ * out[i] < 7 * 2^64 < 2^67. */
+static void smallfelem_mul(longfelem out, const smallfelem small1,
+ const smallfelem small2) {
+ limb a;
+ u64 high, low;
+
+ a = ((uint128_t)small1[0]) * small2[0];
+ low = a;
+ high = a >> 64;
+ out[0] = low;
+ out[1] = high;
+
+ a = ((uint128_t)small1[0]) * small2[1];
+ low = a;
+ high = a >> 64;
+ out[1] += low;
+ out[2] = high;
+
+ a = ((uint128_t)small1[1]) * small2[0];
+ low = a;
+ high = a >> 64;
+ out[1] += low;
+ out[2] += high;
+
+ a = ((uint128_t)small1[0]) * small2[2];
+ low = a;
+ high = a >> 64;
+ out[2] += low;
+ out[3] = high;
+
+ a = ((uint128_t)small1[1]) * small2[1];
+ low = a;
+ high = a >> 64;
+ out[2] += low;
+ out[3] += high;
+
+ a = ((uint128_t)small1[2]) * small2[0];
+ low = a;
+ high = a >> 64;
+ out[2] += low;
+ out[3] += high;
+
+ a = ((uint128_t)small1[0]) * small2[3];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[4] = high;
+
+ a = ((uint128_t)small1[1]) * small2[2];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[4] += high;
+
+ a = ((uint128_t)small1[2]) * small2[1];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[4] += high;
+
+ a = ((uint128_t)small1[3]) * small2[0];
+ low = a;
+ high = a >> 64;
+ out[3] += low;
+ out[4] += high;
+
+ a = ((uint128_t)small1[1]) * small2[3];
+ low = a;
+ high = a >> 64;
+ out[4] += low;
+ out[5] = high;
+
+ a = ((uint128_t)small1[2]) * small2[2];
+ low = a;
+ high = a >> 64;
+ out[4] += low;
+ out[5] += high;
+
+ a = ((uint128_t)small1[3]) * small2[1];
+ low = a;
+ high = a >> 64;
+ out[4] += low;
+ out[5] += high;
+
+ a = ((uint128_t)small1[2]) * small2[3];
+ low = a;
+ high = a >> 64;
+ out[5] += low;
+ out[6] = high;
+
+ a = ((uint128_t)small1[3]) * small2[2];
+ low = a;
+ high = a >> 64;
+ out[5] += low;
+ out[6] += high;
+
+ a = ((uint128_t)small1[3]) * small2[3];
+ low = a;
+ high = a >> 64;
+ out[6] += low;
+ out[7] = high;
+}
+
+/* felem_mul sets |out| = |in1| * |in2|
+ * On entry:
+ * in1[i] < 2^109
+ * in2[i] < 2^109
+ * On exit:
+ * out[i] < 7 * 2^64 < 2^67 */
+static void felem_mul(longfelem out, const felem in1, const felem in2) {
+ smallfelem small1, small2;
+ felem_shrink(small1, in1);
+ felem_shrink(small2, in2);
+ smallfelem_mul(out, small1, small2);
+}
+
+/* felem_small_mul sets |out| = |small1| * |in2|
+ * On entry:
+ * small1[i] < 2^64
+ * in2[i] < 2^109
+ * On exit:
+ * out[i] < 7 * 2^64 < 2^67 */
+static void felem_small_mul(longfelem out, const smallfelem small1,
+ const felem in2) {
+ smallfelem small2;
+ felem_shrink(small2, in2);
+ smallfelem_mul(out, small1, small2);
+}
+
+#define two100m36m4 (((limb)1) << 100) - (((limb)1) << 36) - (((limb)1) << 4)
+#define two100 (((limb)1) << 100)
+#define two100m36p4 (((limb)1) << 100) - (((limb)1) << 36) + (((limb)1) << 4)
+
+/* zero100 is 0 mod p */
+static const felem zero100 = {two100m36m4, two100, two100m36p4, two100m36p4};
+
+/* Internal function for the different flavours of felem_reduce.
+ * felem_reduce_ reduces the higher coefficients in[4]-in[7].
+ * On entry:
+ * out[0] >= in[6] + 2^32*in[6] + in[7] + 2^32*in[7]
+ * out[1] >= in[7] + 2^32*in[4]
+ * out[2] >= in[5] + 2^32*in[5]
+ * out[3] >= in[4] + 2^32*in[5] + 2^32*in[6]
+ * On exit:
+ * out[0] <= out[0] + in[4] + 2^32*in[5]
+ * out[1] <= out[1] + in[5] + 2^33*in[6]
+ * out[2] <= out[2] + in[7] + 2*in[6] + 2^33*in[7]
+ * out[3] <= out[3] + 2^32*in[4] + 3*in[7] */
+static void felem_reduce_(felem out, const longfelem in) {
+ int128_t c;
+ /* combine common terms from below */
+ c = in[4] + (in[5] << 32);
+ out[0] += c;
+ out[3] -= c;
+
+ c = in[5] - in[7];
+ out[1] += c;
+ out[2] -= c;
+
+ /* the remaining terms */
+ /* 256: [(0,1),(96,-1),(192,-1),(224,1)] */
+ out[1] -= (in[4] << 32);
+ out[3] += (in[4] << 32);
+
+ /* 320: [(32,1),(64,1),(128,-1),(160,-1),(224,-1)] */
+ out[2] -= (in[5] << 32);
+
+ /* 384: [(0,-1),(32,-1),(96,2),(128,2),(224,-1)] */
+ out[0] -= in[6];
+ out[0] -= (in[6] << 32);
+ out[1] += (in[6] << 33);
+ out[2] += (in[6] * 2);
+ out[3] -= (in[6] << 32);
+
+ /* 448: [(0,-1),(32,-1),(64,-1),(128,1),(160,2),(192,3)] */
+ out[0] -= in[7];
+ out[0] -= (in[7] << 32);
+ out[2] += (in[7] << 33);
+ out[3] += (in[7] * 3);
+}
+
+/* felem_reduce converts a longfelem into an felem.
+ * To be called directly after felem_square or felem_mul.
+ * On entry:
+ * in[0] < 2^64, in[1] < 3*2^64, in[2] < 5*2^64, in[3] < 7*2^64
+ * in[4] < 7*2^64, in[5] < 5*2^64, in[6] < 3*2^64, in[7] < 2*64
+ * On exit:
+ * out[i] < 2^101 */
+static void felem_reduce(felem out, const longfelem in) {
+ out[0] = zero100[0] + in[0];
+ out[1] = zero100[1] + in[1];
+ out[2] = zero100[2] + in[2];
+ out[3] = zero100[3] + in[3];
+
+ felem_reduce_(out, in);
+
+ /* out[0] > 2^100 - 2^36 - 2^4 - 3*2^64 - 3*2^96 - 2^64 - 2^96 > 0
+ * out[1] > 2^100 - 2^64 - 7*2^96 > 0
+ * out[2] > 2^100 - 2^36 + 2^4 - 5*2^64 - 5*2^96 > 0
+ * out[3] > 2^100 - 2^36 + 2^4 - 7*2^64 - 5*2^96 - 3*2^96 > 0
+ *
+ * out[0] < 2^100 + 2^64 + 7*2^64 + 5*2^96 < 2^101
+ * out[1] < 2^100 + 3*2^64 + 5*2^64 + 3*2^97 < 2^101
+ * out[2] < 2^100 + 5*2^64 + 2^64 + 3*2^65 + 2^97 < 2^101
+ * out[3] < 2^100 + 7*2^64 + 7*2^96 + 3*2^64 < 2^101 */
+}
+
+/* felem_reduce_zero105 converts a larger longfelem into an felem.
+ * On entry:
+ * in[0] < 2^71
+ * On exit:
+ * out[i] < 2^106 */
+static void felem_reduce_zero105(felem out, const longfelem in) {
+ out[0] = zero105[0] + in[0];
+ out[1] = zero105[1] + in[1];
+ out[2] = zero105[2] + in[2];
+ out[3] = zero105[3] + in[3];
+
+ felem_reduce_(out, in);
+
+ /* out[0] > 2^105 - 2^41 - 2^9 - 2^71 - 2^103 - 2^71 - 2^103 > 0
+ * out[1] > 2^105 - 2^71 - 2^103 > 0
+ * out[2] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 > 0
+ * out[3] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 - 2^103 > 0
+ *
+ * out[0] < 2^105 + 2^71 + 2^71 + 2^103 < 2^106
+ * out[1] < 2^105 + 2^71 + 2^71 + 2^103 < 2^106
+ * out[2] < 2^105 + 2^71 + 2^71 + 2^71 + 2^103 < 2^106
+ * out[3] < 2^105 + 2^71 + 2^103 + 2^71 < 2^106 */
+}
+
+/* subtract_u64 sets *result = *result - v and *carry to one if the
+ * subtraction underflowed. */
+static void subtract_u64(u64 *result, u64 *carry, u64 v) {
+ uint128_t r = *result;
+ r -= v;
+ *carry = (r >> 64) & 1;
+ *result = (u64)r;
+}
+
+/* felem_contract converts |in| to its unique, minimal representation. On
+ * entry: in[i] < 2^109. */
+static void felem_contract(smallfelem out, const felem in) {
+ u64 all_equal_so_far = 0, result = 0;
+
+ felem_shrink(out, in);
+ /* small is minimal except that the value might be > p */
+
+ all_equal_so_far--;
+ /* We are doing a constant time test if out >= kPrime. We need to compare
+ * each u64, from most-significant to least significant. For each one, if
+ * all words so far have been equal (m is all ones) then a non-equal
+ * result is the answer. Otherwise we continue. */
+ unsigned i;
+ for (i = 3; i < 4; i--) {
+ u64 equal;
+ uint128_t a = ((uint128_t)kPrime[i]) - out[i];
+ /* if out[i] > kPrime[i] then a will underflow and the high 64-bits
+ * will all be set. */
+ result |= all_equal_so_far & ((u64)(a >> 64));
+
+ /* if kPrime[i] == out[i] then |equal| will be all zeros and the
+ * decrement will make it all ones. */
+ equal = kPrime[i] ^ out[i];
+ equal--;
+ equal &= equal << 32;
+ equal &= equal << 16;
+ equal &= equal << 8;
+ equal &= equal << 4;
+ equal &= equal << 2;
+ equal &= equal << 1;
+ equal = ((s64)equal) >> 63;
+
+ all_equal_so_far &= equal;
+ }
+
+ /* if all_equal_so_far is still all ones then the two values are equal
+ * and so out >= kPrime is true. */
+ result |= all_equal_so_far;
+
+ /* if out >= kPrime then we subtract kPrime. */
+ u64 carry;
+ subtract_u64(&out[0], &carry, result & kPrime[0]);
+ subtract_u64(&out[1], &carry, carry);
+ subtract_u64(&out[2], &carry, carry);
+ subtract_u64(&out[3], &carry, carry);
+
+ subtract_u64(&out[1], &carry, result & kPrime[1]);
+ subtract_u64(&out[2], &carry, carry);
+ subtract_u64(&out[3], &carry, carry);
+
+ subtract_u64(&out[2], &carry, result & kPrime[2]);
+ subtract_u64(&out[3], &carry, carry);
+
+ subtract_u64(&out[3], &carry, result & kPrime[3]);
+}
+
+static void smallfelem_square_contract(smallfelem out, const smallfelem in) {
+ longfelem longtmp;
+ felem tmp;
+
+ smallfelem_square(longtmp, in);
+ felem_reduce(tmp, longtmp);
+ felem_contract(out, tmp);
+}
+
+static void smallfelem_mul_contract(smallfelem out, const smallfelem in1,
+ const smallfelem in2) {
+ longfelem longtmp;
+ felem tmp;
+
+ smallfelem_mul(longtmp, in1, in2);
+ felem_reduce(tmp, longtmp);
+ felem_contract(out, tmp);
+}
+
+/* felem_is_zero returns a limb with all bits set if |in| == 0 (mod p) and 0
+ * otherwise.
+ * On entry:
+ * small[i] < 2^64 */
+static limb smallfelem_is_zero(const smallfelem small) {
+ limb result;
+ u64 is_p;
+
+ u64 is_zero = small[0] | small[1] | small[2] | small[3];
+ is_zero--;
+ is_zero &= is_zero << 32;
+ is_zero &= is_zero << 16;
+ is_zero &= is_zero << 8;
+ is_zero &= is_zero << 4;
+ is_zero &= is_zero << 2;
+ is_zero &= is_zero << 1;
+ is_zero = ((s64)is_zero) >> 63;
+
+ is_p = (small[0] ^ kPrime[0]) | (small[1] ^ kPrime[1]) |
+ (small[2] ^ kPrime[2]) | (small[3] ^ kPrime[3]);
+ is_p--;
+ is_p &= is_p << 32;
+ is_p &= is_p << 16;
+ is_p &= is_p << 8;
+ is_p &= is_p << 4;
+ is_p &= is_p << 2;
+ is_p &= is_p << 1;
+ is_p = ((s64)is_p) >> 63;
+
+ is_zero |= is_p;
+
+ result = is_zero;
+ result |= ((limb)is_zero) << 64;
+ return result;
+}
+
+static int smallfelem_is_zero_int(const smallfelem small) {
+ return (int)(smallfelem_is_zero(small) & ((limb)1));
+}
+
+/* felem_inv calculates |out| = |in|^{-1}
+ *
+ * Based on Fermat's Little Theorem:
+ * a^p = a (mod p)
+ * a^{p-1} = 1 (mod p)
+ * a^{p-2} = a^{-1} (mod p) */
+static void felem_inv(felem out, const felem in) {
+ felem ftmp, ftmp2;
+ /* each e_I will hold |in|^{2^I - 1} */
+ felem e2, e4, e8, e16, e32, e64;
+ longfelem tmp;
+ unsigned i;
+
+ felem_square(tmp, in);
+ felem_reduce(ftmp, tmp); /* 2^1 */
+ felem_mul(tmp, in, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^2 - 2^0 */
+ felem_assign(e2, ftmp);
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^3 - 2^1 */
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^4 - 2^2 */
+ felem_mul(tmp, ftmp, e2);
+ felem_reduce(ftmp, tmp); /* 2^4 - 2^0 */
+ felem_assign(e4, ftmp);
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^5 - 2^1 */
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^6 - 2^2 */
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^7 - 2^3 */
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp); /* 2^8 - 2^4 */
+ felem_mul(tmp, ftmp, e4);
+ felem_reduce(ftmp, tmp); /* 2^8 - 2^0 */
+ felem_assign(e8, ftmp);
+ for (i = 0; i < 8; i++) {
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp);
+ } /* 2^16 - 2^8 */
+ felem_mul(tmp, ftmp, e8);
+ felem_reduce(ftmp, tmp); /* 2^16 - 2^0 */
+ felem_assign(e16, ftmp);
+ for (i = 0; i < 16; i++) {
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp);
+ } /* 2^32 - 2^16 */
+ felem_mul(tmp, ftmp, e16);
+ felem_reduce(ftmp, tmp); /* 2^32 - 2^0 */
+ felem_assign(e32, ftmp);
+ for (i = 0; i < 32; i++) {
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp);
+ } /* 2^64 - 2^32 */
+ felem_assign(e64, ftmp);
+ felem_mul(tmp, ftmp, in);
+ felem_reduce(ftmp, tmp); /* 2^64 - 2^32 + 2^0 */
+ for (i = 0; i < 192; i++) {
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp);
+ } /* 2^256 - 2^224 + 2^192 */
+
+ felem_mul(tmp, e64, e32);
+ felem_reduce(ftmp2, tmp); /* 2^64 - 2^0 */
+ for (i = 0; i < 16; i++) {
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp);
+ } /* 2^80 - 2^16 */
+ felem_mul(tmp, ftmp2, e16);
+ felem_reduce(ftmp2, tmp); /* 2^80 - 2^0 */
+ for (i = 0; i < 8; i++) {
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp);
+ } /* 2^88 - 2^8 */
+ felem_mul(tmp, ftmp2, e8);
+ felem_reduce(ftmp2, tmp); /* 2^88 - 2^0 */
+ for (i = 0; i < 4; i++) {
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp);
+ } /* 2^92 - 2^4 */
+ felem_mul(tmp, ftmp2, e4);
+ felem_reduce(ftmp2, tmp); /* 2^92 - 2^0 */
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp); /* 2^93 - 2^1 */
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp); /* 2^94 - 2^2 */
+ felem_mul(tmp, ftmp2, e2);
+ felem_reduce(ftmp2, tmp); /* 2^94 - 2^0 */
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp); /* 2^95 - 2^1 */
+ felem_square(tmp, ftmp2);
+ felem_reduce(ftmp2, tmp); /* 2^96 - 2^2 */
+ felem_mul(tmp, ftmp2, in);
+ felem_reduce(ftmp2, tmp); /* 2^96 - 3 */
+
+ felem_mul(tmp, ftmp2, ftmp);
+ felem_reduce(out, tmp); /* 2^256 - 2^224 + 2^192 + 2^96 - 3 */
+}
+
+static void smallfelem_inv_contract(smallfelem out, const smallfelem in) {
+ felem tmp;
+
+ smallfelem_expand(tmp, in);
+ felem_inv(tmp, tmp);
+ felem_contract(out, tmp);
+}
+
+/* Group operations
+ * ----------------
+ *
+ * Building on top of the field operations we have the operations on the
+ * elliptic curve group itself. Points on the curve are represented in Jacobian
+ * coordinates. */
+
+/* point_double calculates 2*(x_in, y_in, z_in)
+ *
+ * The method is taken from:
+ * http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
+ *
+ * Outputs can equal corresponding inputs, i.e., x_out == x_in is allowed.
+ * while x_out == y_in is not (maybe this works, but it's not tested). */
+static void point_double(felem x_out, felem y_out, felem z_out,
+ const felem x_in, const felem y_in, const felem z_in) {
+ longfelem tmp, tmp2;
+ felem delta, gamma, beta, alpha, ftmp, ftmp2;
+ smallfelem small1, small2;
+
+ felem_assign(ftmp, x_in);
+ /* ftmp[i] < 2^106 */
+ felem_assign(ftmp2, x_in);
+ /* ftmp2[i] < 2^106 */
+
+ /* delta = z^2 */
+ felem_square(tmp, z_in);
+ felem_reduce(delta, tmp);
+ /* delta[i] < 2^101 */
+
+ /* gamma = y^2 */
+ felem_square(tmp, y_in);
+ felem_reduce(gamma, tmp);
+ /* gamma[i] < 2^101 */
+ felem_shrink(small1, gamma);
+
+ /* beta = x*gamma */
+ felem_small_mul(tmp, small1, x_in);
+ felem_reduce(beta, tmp);
+ /* beta[i] < 2^101 */
+
+ /* alpha = 3*(x-delta)*(x+delta) */
+ felem_diff(ftmp, delta);
+ /* ftmp[i] < 2^105 + 2^106 < 2^107 */
+ felem_sum(ftmp2, delta);
+ /* ftmp2[i] < 2^105 + 2^106 < 2^107 */
+ felem_scalar(ftmp2, 3);
+ /* ftmp2[i] < 3 * 2^107 < 2^109 */
+ felem_mul(tmp, ftmp, ftmp2);
+ felem_reduce(alpha, tmp);
+ /* alpha[i] < 2^101 */
+ felem_shrink(small2, alpha);
+
+ /* x' = alpha^2 - 8*beta */
+ smallfelem_square(tmp, small2);
+ felem_reduce(x_out, tmp);
+ felem_assign(ftmp, beta);
+ felem_scalar(ftmp, 8);
+ /* ftmp[i] < 8 * 2^101 = 2^104 */
+ felem_diff(x_out, ftmp);
+ /* x_out[i] < 2^105 + 2^101 < 2^106 */
+
+ /* z' = (y + z)^2 - gamma - delta */
+ felem_sum(delta, gamma);
+ /* delta[i] < 2^101 + 2^101 = 2^102 */
+ felem_assign(ftmp, y_in);
+ felem_sum(ftmp, z_in);
+ /* ftmp[i] < 2^106 + 2^106 = 2^107 */
+ felem_square(tmp, ftmp);
+ felem_reduce(z_out, tmp);
+ felem_diff(z_out, delta);
+ /* z_out[i] < 2^105 + 2^101 < 2^106 */
+
+ /* y' = alpha*(4*beta - x') - 8*gamma^2 */
+ felem_scalar(beta, 4);
+ /* beta[i] < 4 * 2^101 = 2^103 */
+ felem_diff_zero107(beta, x_out);
+ /* beta[i] < 2^107 + 2^103 < 2^108 */
+ felem_small_mul(tmp, small2, beta);
+ /* tmp[i] < 7 * 2^64 < 2^67 */
+ smallfelem_square(tmp2, small1);
+ /* tmp2[i] < 7 * 2^64 */
+ longfelem_scalar(tmp2, 8);
+ /* tmp2[i] < 8 * 7 * 2^64 = 7 * 2^67 */
+ longfelem_diff(tmp, tmp2);
+ /* tmp[i] < 2^67 + 2^70 + 2^40 < 2^71 */
+ felem_reduce_zero105(y_out, tmp);
+ /* y_out[i] < 2^106 */
+}
+
+/* point_double_small is the same as point_double, except that it operates on
+ * smallfelems. */
+static void point_double_small(smallfelem x_out, smallfelem y_out,
+ smallfelem z_out, const smallfelem x_in,
+ const smallfelem y_in, const smallfelem z_in) {
+ felem felem_x_out, felem_y_out, felem_z_out;
+ felem felem_x_in, felem_y_in, felem_z_in;
+
+ smallfelem_expand(felem_x_in, x_in);
+ smallfelem_expand(felem_y_in, y_in);
+ smallfelem_expand(felem_z_in, z_in);
+ point_double(felem_x_out, felem_y_out, felem_z_out, felem_x_in, felem_y_in,
+ felem_z_in);
+ felem_shrink(x_out, felem_x_out);
+ felem_shrink(y_out, felem_y_out);
+ felem_shrink(z_out, felem_z_out);
+}
+
+/* copy_conditional copies in to out iff mask is all ones. */
+static void copy_conditional(felem out, const felem in, limb mask) {
+ unsigned i;
+ for (i = 0; i < NLIMBS; ++i) {
+ const limb tmp = mask & (in[i] ^ out[i]);
+ out[i] ^= tmp;
+ }
+}
+
+/* copy_small_conditional copies in to out iff mask is all ones. */
+static void copy_small_conditional(felem out, const smallfelem in, limb mask) {
+ unsigned i;
+ const u64 mask64 = mask;
+ for (i = 0; i < NLIMBS; ++i) {
+ out[i] = ((limb)(in[i] & mask64)) | (out[i] & ~mask);
+ }
+}
+
+/* point_add calcuates (x1, y1, z1) + (x2, y2, z2)
+ *
+ * The method is taken from:
+ * http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl,
+ * adapted for mixed addition (z2 = 1, or z2 = 0 for the point at infinity).
+ *
+ * This function includes a branch for checking whether the two input points
+ * are equal, (while not equal to the point at infinity). This case never
+ * happens during single point multiplication, so there is no timing leak for
+ * ECDH or ECDSA signing. */
+static void point_add(felem x3, felem y3, felem z3, const felem x1,
+ const felem y1, const felem z1, const int mixed,
+ const smallfelem x2, const smallfelem y2,
+ const smallfelem z2) {
+ felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, ftmp6, x_out, y_out, z_out;
+ longfelem tmp, tmp2;
+ smallfelem small1, small2, small3, small4, small5;
+ limb x_equal, y_equal, z1_is_zero, z2_is_zero;
+
+ felem_shrink(small3, z1);
+
+ z1_is_zero = smallfelem_is_zero(small3);
+ z2_is_zero = smallfelem_is_zero(z2);
+
+ /* ftmp = z1z1 = z1**2 */
+ smallfelem_square(tmp, small3);
+ felem_reduce(ftmp, tmp);
+ /* ftmp[i] < 2^101 */
+ felem_shrink(small1, ftmp);
+
+ if (!mixed) {
+ /* ftmp2 = z2z2 = z2**2 */
+ smallfelem_square(tmp, z2);
+ felem_reduce(ftmp2, tmp);
+ /* ftmp2[i] < 2^101 */
+ felem_shrink(small2, ftmp2);
+
+ felem_shrink(small5, x1);
+
+ /* u1 = ftmp3 = x1*z2z2 */
+ smallfelem_mul(tmp, small5, small2);
+ felem_reduce(ftmp3, tmp);
+ /* ftmp3[i] < 2^101 */
+
+ /* ftmp5 = z1 + z2 */
+ felem_assign(ftmp5, z1);
+ felem_small_sum(ftmp5, z2);
+ /* ftmp5[i] < 2^107 */
+
+ /* ftmp5 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2 */
+ felem_square(tmp, ftmp5);
+ felem_reduce(ftmp5, tmp);
+ /* ftmp2 = z2z2 + z1z1 */
+ felem_sum(ftmp2, ftmp);
+ /* ftmp2[i] < 2^101 + 2^101 = 2^102 */
+ felem_diff(ftmp5, ftmp2);
+ /* ftmp5[i] < 2^105 + 2^101 < 2^106 */
+
+ /* ftmp2 = z2 * z2z2 */
+ smallfelem_mul(tmp, small2, z2);
+ felem_reduce(ftmp2, tmp);
+
+ /* s1 = ftmp2 = y1 * z2**3 */
+ felem_mul(tmp, y1, ftmp2);
+ felem_reduce(ftmp6, tmp);
+ /* ftmp6[i] < 2^101 */
+ } else {
+ /* We'll assume z2 = 1 (special case z2 = 0 is handled later). */
+
+ /* u1 = ftmp3 = x1*z2z2 */
+ felem_assign(ftmp3, x1);
+ /* ftmp3[i] < 2^106 */
+
+ /* ftmp5 = 2z1z2 */
+ felem_assign(ftmp5, z1);
+ felem_scalar(ftmp5, 2);
+ /* ftmp5[i] < 2*2^106 = 2^107 */
+
+ /* s1 = ftmp2 = y1 * z2**3 */
+ felem_assign(ftmp6, y1);
+ /* ftmp6[i] < 2^106 */
+ }
+
+ /* u2 = x2*z1z1 */
+ smallfelem_mul(tmp, x2, small1);
+ felem_reduce(ftmp4, tmp);
+
+ /* h = ftmp4 = u2 - u1 */
+ felem_diff_zero107(ftmp4, ftmp3);
+ /* ftmp4[i] < 2^107 + 2^101 < 2^108 */
+ felem_shrink(small4, ftmp4);
+
+ x_equal = smallfelem_is_zero(small4);
+
+ /* z_out = ftmp5 * h */
+ felem_small_mul(tmp, small4, ftmp5);
+ felem_reduce(z_out, tmp);
+ /* z_out[i] < 2^101 */
+
+ /* ftmp = z1 * z1z1 */
+ smallfelem_mul(tmp, small1, small3);
+ felem_reduce(ftmp, tmp);
+
+ /* s2 = tmp = y2 * z1**3 */
+ felem_small_mul(tmp, y2, ftmp);
+ felem_reduce(ftmp5, tmp);
+
+ /* r = ftmp5 = (s2 - s1)*2 */
+ felem_diff_zero107(ftmp5, ftmp6);
+ /* ftmp5[i] < 2^107 + 2^107 = 2^108 */
+ felem_scalar(ftmp5, 2);
+ /* ftmp5[i] < 2^109 */
+ felem_shrink(small1, ftmp5);
+ y_equal = smallfelem_is_zero(small1);
+
+ if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) {
+ point_double(x3, y3, z3, x1, y1, z1);
+ return;
+ }
+
+ /* I = ftmp = (2h)**2 */
+ felem_assign(ftmp, ftmp4);
+ felem_scalar(ftmp, 2);
+ /* ftmp[i] < 2*2^108 = 2^109 */
+ felem_square(tmp, ftmp);
+ felem_reduce(ftmp, tmp);
+
+ /* J = ftmp2 = h * I */
+ felem_mul(tmp, ftmp4, ftmp);
+ felem_reduce(ftmp2, tmp);
+
+ /* V = ftmp4 = U1 * I */
+ felem_mul(tmp, ftmp3, ftmp);
+ felem_reduce(ftmp4, tmp);
+
+ /* x_out = r**2 - J - 2V */
+ smallfelem_square(tmp, small1);
+ felem_reduce(x_out, tmp);
+ felem_assign(ftmp3, ftmp4);
+ felem_scalar(ftmp4, 2);
+ felem_sum(ftmp4, ftmp2);
+ /* ftmp4[i] < 2*2^101 + 2^101 < 2^103 */
+ felem_diff(x_out, ftmp4);
+ /* x_out[i] < 2^105 + 2^101 */
+
+ /* y_out = r(V-x_out) - 2 * s1 * J */
+ felem_diff_zero107(ftmp3, x_out);
+ /* ftmp3[i] < 2^107 + 2^101 < 2^108 */
+ felem_small_mul(tmp, small1, ftmp3);
+ felem_mul(tmp2, ftmp6, ftmp2);
+ longfelem_scalar(tmp2, 2);
+ /* tmp2[i] < 2*2^67 = 2^68 */
+ longfelem_diff(tmp, tmp2);
+ /* tmp[i] < 2^67 + 2^70 + 2^40 < 2^71 */
+ felem_reduce_zero105(y_out, tmp);
+ /* y_out[i] < 2^106 */
+
+ copy_small_conditional(x_out, x2, z1_is_zero);
+ copy_conditional(x_out, x1, z2_is_zero);
+ copy_small_conditional(y_out, y2, z1_is_zero);
+ copy_conditional(y_out, y1, z2_is_zero);
+ copy_small_conditional(z_out, z2, z1_is_zero);
+ copy_conditional(z_out, z1, z2_is_zero);
+ felem_assign(x3, x_out);
+ felem_assign(y3, y_out);
+ felem_assign(z3, z_out);
+}
+
+/* point_add_small is the same as point_add, except that it operates on
+ * smallfelems. */
+static void point_add_small(smallfelem x3, smallfelem y3, smallfelem z3,
+ smallfelem x1, smallfelem y1, smallfelem z1,
+ smallfelem x2, smallfelem y2, smallfelem z2) {
+ felem felem_x3, felem_y3, felem_z3;
+ felem felem_x1, felem_y1, felem_z1;
+ smallfelem_expand(felem_x1, x1);
+ smallfelem_expand(felem_y1, y1);
+ smallfelem_expand(felem_z1, z1);
+ point_add(felem_x3, felem_y3, felem_z3, felem_x1, felem_y1, felem_z1, 0, x2,
+ y2, z2);
+ felem_shrink(x3, felem_x3);
+ felem_shrink(y3, felem_y3);
+ felem_shrink(z3, felem_z3);
+}
+
+/* Base point pre computation
+ * --------------------------
+ *
+ * Two different sorts of precomputed tables are used in the following code.
+ * Each contain various points on the curve, where each point is three field
+ * elements (x, y, z).
+ *
+ * For the base point table, z is usually 1 (0 for the point at infinity).
+ * This table has 2 * 16 elements, starting with the following:
+ * index | bits | point
+ * ------+---------+------------------------------
+ * 0 | 0 0 0 0 | 0G
+ * 1 | 0 0 0 1 | 1G
+ * 2 | 0 0 1 0 | 2^64G
+ * 3 | 0 0 1 1 | (2^64 + 1)G
+ * 4 | 0 1 0 0 | 2^128G
+ * 5 | 0 1 0 1 | (2^128 + 1)G
+ * 6 | 0 1 1 0 | (2^128 + 2^64)G
+ * 7 | 0 1 1 1 | (2^128 + 2^64 + 1)G
+ * 8 | 1 0 0 0 | 2^192G
+ * 9 | 1 0 0 1 | (2^192 + 1)G
+ * 10 | 1 0 1 0 | (2^192 + 2^64)G
+ * 11 | 1 0 1 1 | (2^192 + 2^64 + 1)G
+ * 12 | 1 1 0 0 | (2^192 + 2^128)G
+ * 13 | 1 1 0 1 | (2^192 + 2^128 + 1)G
+ * 14 | 1 1 1 0 | (2^192 + 2^128 + 2^64)G
+ * 15 | 1 1 1 1 | (2^192 + 2^128 + 2^64 + 1)G
+ * followed by a copy of this with each element multiplied by 2^32.
+ *
+ * The reason for this is so that we can clock bits into four different
+ * locations when doing simple scalar multiplies against the base point,
+ * and then another four locations using the second 16 elements.
+ *
+ * Tables for other points have table[i] = iG for i in 0 .. 16. */
+
+/* gmul is the table of precomputed base points */
+static const smallfelem gmul[2][16][3] = {
+ {{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}},
+ {{0xf4a13945d898c296, 0x77037d812deb33a0, 0xf8bce6e563a440f2,
+ 0x6b17d1f2e12c4247},
+ {0xcbb6406837bf51f5, 0x2bce33576b315ece, 0x8ee7eb4a7c0f9e16,
+ 0x4fe342e2fe1a7f9b},
+ {1, 0, 0, 0}},
+ {{0x90e75cb48e14db63, 0x29493baaad651f7e, 0x8492592e326e25de,
+ 0x0fa822bc2811aaa5},
+ {0xe41124545f462ee7, 0x34b1a65050fe82f5, 0x6f4ad4bcb3df188b,
+ 0xbff44ae8f5dba80d},
+ {1, 0, 0, 0}},
+ {{0x93391ce2097992af, 0xe96c98fd0d35f1fa, 0xb257c0de95e02789,
+ 0x300a4bbc89d6726f},
+ {0xaa54a291c08127a0, 0x5bb1eeada9d806a5, 0x7f1ddb25ff1e3c6f,
+ 0x72aac7e0d09b4644},
+ {1, 0, 0, 0}},
+ {{0x57c84fc9d789bd85, 0xfc35ff7dc297eac3, 0xfb982fd588c6766e,
+ 0x447d739beedb5e67},
+ {0x0c7e33c972e25b32, 0x3d349b95a7fae500, 0xe12e9d953a4aaff7,
+ 0x2d4825ab834131ee},
+ {1, 0, 0, 0}},
+ {{0x13949c932a1d367f, 0xef7fbd2b1a0a11b7, 0xddc6068bb91dfc60,
+ 0xef9519328a9c72ff},
+ {0x196035a77376d8a8, 0x23183b0895ca1740, 0xc1ee9807022c219c,
+ 0x611e9fc37dbb2c9b},
+ {1, 0, 0, 0}},
+ {{0xcae2b1920b57f4bc, 0x2936df5ec6c9bc36, 0x7dea6482e11238bf,
+ 0x550663797b51f5d8},
+ {0x44ffe216348a964c, 0x9fb3d576dbdefbe1, 0x0afa40018d9d50e5,
+ 0x157164848aecb851},
+ {1, 0, 0, 0}},
+ {{0xe48ecafffc5cde01, 0x7ccd84e70d715f26, 0xa2e8f483f43e4391,
+ 0xeb5d7745b21141ea},
+ {0xcac917e2731a3479, 0x85f22cfe2844b645, 0x0990e6a158006cee,
+ 0xeafd72ebdbecc17b},
+ {1, 0, 0, 0}},
+ {{0x6cf20ffb313728be, 0x96439591a3c6b94a, 0x2736ff8344315fc5,
+ 0xa6d39677a7849276},
+ {0xf2bab833c357f5f4, 0x824a920c2284059b, 0x66b8babd2d27ecdf,
+ 0x674f84749b0b8816},
+ {1, 0, 0, 0}},
+ {{0x2df48c04677c8a3e, 0x74e02f080203a56b, 0x31855f7db8c7fedb,
+ 0x4e769e7672c9ddad},
+ {0xa4c36165b824bbb0, 0xfb9ae16f3b9122a5, 0x1ec0057206947281,
+ 0x42b99082de830663},
+ {1, 0, 0, 0}},
+ {{0x6ef95150dda868b9, 0xd1f89e799c0ce131, 0x7fdc1ca008a1c478,
+ 0x78878ef61c6ce04d},
+ {0x9c62b9121fe0d976, 0x6ace570ebde08d4f, 0xde53142c12309def,
+ 0xb6cb3f5d7b72c321},
+ {1, 0, 0, 0}},
+ {{0x7f991ed2c31a3573, 0x5b82dd5bd54fb496, 0x595c5220812ffcae,
+ 0x0c88bc4d716b1287},
+ {0x3a57bf635f48aca8, 0x7c8181f4df2564f3, 0x18d1b5b39c04e6aa,
+ 0xdd5ddea3f3901dc6},
+ {1, 0, 0, 0}},
+ {{0xe96a79fb3e72ad0c, 0x43a0a28c42ba792f, 0xefe0a423083e49f3,
+ 0x68f344af6b317466},
+ {0xcdfe17db3fb24d4a, 0x668bfc2271f5c626, 0x604ed93c24d67ff3,
+ 0x31b9c405f8540a20},
+ {1, 0, 0, 0}},
+ {{0xd36b4789a2582e7f, 0x0d1a10144ec39c28, 0x663c62c3edbad7a0,
+ 0x4052bf4b6f461db9},
+ {0x235a27c3188d25eb, 0xe724f33999bfcc5b, 0x862be6bd71d70cc8,
+ 0xfecf4d5190b0fc61},
+ {1, 0, 0, 0}},
+ {{0x74346c10a1d4cfac, 0xafdf5cc08526a7a4, 0x123202a8f62bff7a,
+ 0x1eddbae2c802e41a},
+ {0x8fa0af2dd603f844, 0x36e06b7e4c701917, 0x0c45f45273db33a0,
+ 0x43104d86560ebcfc},
+ {1, 0, 0, 0}},
+ {{0x9615b5110d1d78e5, 0x66b0de3225c4744b, 0x0a4a46fb6aaf363a,
+ 0xb48e26b484f7a21c},
+ {0x06ebb0f621a01b2d, 0xc004e4048b7b0f98, 0x64131bcdfed6f668,
+ 0xfac015404d4d3dab},
+ {1, 0, 0, 0}}},
+ {{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}},
+ {{0x3a5a9e22185a5943, 0x1ab919365c65dfb6, 0x21656b32262c71da,
+ 0x7fe36b40af22af89},
+ {0xd50d152c699ca101, 0x74b3d5867b8af212, 0x9f09f40407dca6f1,
+ 0xe697d45825b63624},
+ {1, 0, 0, 0}},
+ {{0xa84aa9397512218e, 0xe9a521b074ca0141, 0x57880b3a18a2e902,
+ 0x4a5b506612a677a6},
+ {0x0beada7a4c4f3840, 0x626db15419e26d9d, 0xc42604fbe1627d40,
+ 0xeb13461ceac089f1},
+ {1, 0, 0, 0}},
+ {{0xf9faed0927a43281, 0x5e52c4144103ecbc, 0xc342967aa815c857,
+ 0x0781b8291c6a220a},
+ {0x5a8343ceeac55f80, 0x88f80eeee54a05e3, 0x97b2a14f12916434,
+ 0x690cde8df0151593},
+ {1, 0, 0, 0}},
+ {{0xaee9c75df7f82f2a, 0x9e4c35874afdf43a, 0xf5622df437371326,
+ 0x8a535f566ec73617},
+ {0xc5f9a0ac223094b7, 0xcde533864c8c7669, 0x37e02819085a92bf,
+ 0x0455c08468b08bd7},
+ {1, 0, 0, 0}},
+ {{0x0c0a6e2c9477b5d9, 0xf9a4bf62876dc444, 0x5050a949b6cdc279,
+ 0x06bada7ab77f8276},
+ {0xc8b4aed1ea48dac9, 0xdebd8a4b7ea1070f, 0x427d49101366eb70,
+ 0x5b476dfd0e6cb18a},
+ {1, 0, 0, 0}},
+ {{0x7c5c3e44278c340a, 0x4d54606812d66f3b, 0x29a751b1ae23c5d8,
+ 0x3e29864e8a2ec908},
+ {0x142d2a6626dbb850, 0xad1744c4765bd780, 0x1f150e68e322d1ed,
+ 0x239b90ea3dc31e7e},
+ {1, 0, 0, 0}},
+ {{0x78c416527a53322a, 0x305dde6709776f8e, 0xdbcab759f8862ed4,
+ 0x820f4dd949f72ff7},
+ {0x6cc544a62b5debd4, 0x75be5d937b4e8cc4, 0x1b481b1b215c14d3,
+ 0x140406ec783a05ec},
+ {1, 0, 0, 0}},
+ {{0x6a703f10e895df07, 0xfd75f3fa01876bd8, 0xeb5b06e70ce08ffe,
+ 0x68f6b8542783dfee},
+ {0x90c76f8a78712655, 0xcf5293d2f310bf7f, 0xfbc8044dfda45028,
+ 0xcbe1feba92e40ce6},
+ {1, 0, 0, 0}},
+ {{0xe998ceea4396e4c1, 0xfc82ef0b6acea274, 0x230f729f2250e927,
+ 0xd0b2f94d2f420109},
+ {0x4305adddb38d4966, 0x10b838f8624c3b45, 0x7db2636658954e7a,
+ 0x971459828b0719e5},
+ {1, 0, 0, 0}},
+ {{0x4bd6b72623369fc9, 0x57f2929e53d0b876, 0xc2d5cba4f2340687,
+ 0x961610004a866aba},
+ {0x49997bcd2e407a5e, 0x69ab197d92ddcb24, 0x2cf1f2438fe5131c,
+ 0x7acb9fadcee75e44},
+ {1, 0, 0, 0}},
+ {{0x254e839423d2d4c0, 0xf57f0c917aea685b, 0xa60d880f6f75aaea,
+ 0x24eb9acca333bf5b},
+ {0xe3de4ccb1cda5dea, 0xfeef9341c51a6b4f, 0x743125f88bac4c4d,
+ 0x69f891c5acd079cc},
+ {1, 0, 0, 0}},
+ {{0xeee44b35702476b5, 0x7ed031a0e45c2258, 0xb422d1e7bd6f8514,
+ 0xe51f547c5972a107},
+ {0xa25bcd6fc9cf343d, 0x8ca922ee097c184e, 0xa62f98b3a9fe9a06,
+ 0x1c309a2b25bb1387},
+ {1, 0, 0, 0}},
+ {{0x9295dbeb1967c459, 0xb00148833472c98e, 0xc504977708011828,
+ 0x20b87b8aa2c4e503},
+ {0x3063175de057c277, 0x1bd539338fe582dd, 0x0d11adef5f69a044,
+ 0xf5c6fa49919776be},
+ {1, 0, 0, 0}},
+ {{0x8c944e760fd59e11, 0x3876cba1102fad5f, 0xa454c3fad83faa56,
+ 0x1ed7d1b9332010b9},
+ {0xa1011a270024b889, 0x05e4d0dcac0cd344, 0x52b520f0eb6a2a24,
+ 0x3a2b03f03217257a},
+ {1, 0, 0, 0}},
+ {{0xf20fc2afdf1d043d, 0xf330240db58d5a62, 0xfc7d229ca0058c3b,
+ 0x15fee545c78dd9f6},
+ {0x501e82885bc98cda, 0x41ef80e5d046ac04, 0x557d9f49461210fb,
+ 0x4ab5b6b2b8753f81},
+ {1, 0, 0, 0}}}};
+
+/* select_point selects the |idx|th point from a precomputation table and
+ * copies it to out. */
+static void select_point(const u64 idx, unsigned int size,
+ const smallfelem pre_comp[16][3], smallfelem out[3]) {
+ unsigned i, j;
+ u64 *outlimbs = &out[0][0];
+ memset(outlimbs, 0, 3 * sizeof(smallfelem));
+
+ for (i = 0; i < size; i++) {
+ const u64 *inlimbs = (u64 *)&pre_comp[i][0][0];
+ u64 mask = i ^ idx;
+ mask |= mask >> 4;
+ mask |= mask >> 2;
+ mask |= mask >> 1;
+ mask &= 1;
+ mask--;
+ for (j = 0; j < NLIMBS * 3; j++) {
+ outlimbs[j] |= inlimbs[j] & mask;
+ }
+ }
+}
+
+/* get_bit returns the |i|th bit in |in| */
+static char get_bit(const felem_bytearray in, int i) {
+ if (i < 0 || i >= 256) {
+ return 0;
+ }
+ return (in[i >> 3] >> (i & 7)) & 1;
+}
+
+/* Interleaved point multiplication using precomputed point multiples: The
+ * small point multiples 0*P, 1*P, ..., 17*P are in pre_comp[], the scalars
+ * in scalars[]. If g_scalar is non-NULL, we also add this multiple of the
+ * generator, using certain (large) precomputed multiples in g_pre_comp.
+ * Output point (X, Y, Z) is stored in x_out, y_out, z_out. */
+static void batch_mul(felem x_out, felem y_out, felem z_out,
+ const felem_bytearray scalars[],
+ const unsigned num_points, const u8 *g_scalar,
+ const int mixed, const smallfelem pre_comp[][17][3],
+ const smallfelem g_pre_comp[2][16][3]) {
+ int i, skip;
+ unsigned num, gen_mul = (g_scalar != NULL);
+ felem nq[3], ftmp;
+ smallfelem tmp[3];
+ u64 bits;
+ u8 sign, digit;
+
+ /* set nq to the point at infinity */
+ memset(nq, 0, 3 * sizeof(felem));
+
+ /* Loop over all scalars msb-to-lsb, interleaving additions of multiples
+ * of the generator (two in each of the last 32 rounds) and additions of
+ * other points multiples (every 5th round). */
+
+ skip = 1; /* save two point operations in the first
+ * round */
+ for (i = (num_points ? 255 : 31); i >= 0; --i) {
+ /* double */
+ if (!skip) {
+ point_double(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2]);
+ }
+
+ /* add multiples of the generator */
+ if (gen_mul && i <= 31) {
+ /* first, look 32 bits upwards */
+ bits = get_bit(g_scalar, i + 224) << 3;
+ bits |= get_bit(g_scalar, i + 160) << 2;
+ bits |= get_bit(g_scalar, i + 96) << 1;
+ bits |= get_bit(g_scalar, i + 32);
+ /* select the point to add, in constant time */
+ select_point(bits, 16, g_pre_comp[1], tmp);
+
+ if (!skip) {
+ /* Arg 1 below is for "mixed" */
+ point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1, tmp[0], tmp[1],
+ tmp[2]);
+ } else {
+ smallfelem_expand(nq[0], tmp[0]);
+ smallfelem_expand(nq[1], tmp[1]);
+ smallfelem_expand(nq[2], tmp[2]);
+ skip = 0;
+ }
+
+ /* second, look at the current position */
+ bits = get_bit(g_scalar, i + 192) << 3;
+ bits |= get_bit(g_scalar, i + 128) << 2;
+ bits |= get_bit(g_scalar, i + 64) << 1;
+ bits |= get_bit(g_scalar, i);
+ /* select the point to add, in constant time */
+ select_point(bits, 16, g_pre_comp[0], tmp);
+ /* Arg 1 below is for "mixed" */
+ point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1, tmp[0], tmp[1],
+ tmp[2]);
+ }
+
+ /* do other additions every 5 doublings */
+ if (num_points && (i % 5 == 0)) {
+ /* loop over all scalars */
+ for (num = 0; num < num_points; ++num) {
+ bits = get_bit(scalars[num], i + 4) << 5;
+ bits |= get_bit(scalars[num], i + 3) << 4;
+ bits |= get_bit(scalars[num], i + 2) << 3;
+ bits |= get_bit(scalars[num], i + 1) << 2;
+ bits |= get_bit(scalars[num], i) << 1;
+ bits |= get_bit(scalars[num], i - 1);
+ ec_GFp_nistp_recode_scalar_bits(&sign, &digit, bits);
+
+ /* select the point to add or subtract, in constant time. */
+ select_point(digit, 17, pre_comp[num], tmp);
+ smallfelem_neg(ftmp, tmp[1]); /* (X, -Y, Z) is the negative
+ * point */
+ copy_small_conditional(ftmp, tmp[1], (((limb)sign) - 1));
+ felem_contract(tmp[1], ftmp);
+
+ if (!skip) {
+ point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], mixed, tmp[0],
+ tmp[1], tmp[2]);
+ } else {
+ smallfelem_expand(nq[0], tmp[0]);
+ smallfelem_expand(nq[1], tmp[1]);
+ smallfelem_expand(nq[2], tmp[2]);
+ skip = 0;
+ }
+ }
+ }
+ }
+ felem_assign(x_out, nq[0]);
+ felem_assign(y_out, nq[1]);
+ felem_assign(z_out, nq[2]);
+}
+
+/* Precomputation for the group generator. */
+typedef struct {
+ smallfelem g_pre_comp[2][16][3];
+ int references;
+} NISTP256_PRE_COMP;
+
+/******************************************************************************/
+/*
+ * OPENSSL EC_METHOD FUNCTIONS
+ */
+
+int ec_GFp_nistp256_group_init(EC_GROUP *group) {
+ int ret = ec_GFp_simple_group_init(group);
+ group->a_is_minus3 = 1;
+ return ret;
+}
+
+int ec_GFp_nistp256_group_set_curve(EC_GROUP *group, const BIGNUM *p,
+ const BIGNUM *a, const BIGNUM *b,
+ BN_CTX *ctx) {
+ int ret = 0;
+ BN_CTX *new_ctx = NULL;
+ BIGNUM *curve_p, *curve_a, *curve_b;
+
+ if (ctx == NULL) {
+ if ((ctx = new_ctx = BN_CTX_new()) == NULL) {
+ return 0;
+ }
+ }
+ BN_CTX_start(ctx);
+ if (((curve_p = BN_CTX_get(ctx)) == NULL) ||
+ ((curve_a = BN_CTX_get(ctx)) == NULL) ||
+ ((curve_b = BN_CTX_get(ctx)) == NULL)) {
+ goto err;
+ }
+ BN_bin2bn(nistp256_curve_params[0], sizeof(felem_bytearray), curve_p);
+ BN_bin2bn(nistp256_curve_params[1], sizeof(felem_bytearray), curve_a);
+ BN_bin2bn(nistp256_curve_params[2], sizeof(felem_bytearray), curve_b);
+ if (BN_cmp(curve_p, p) ||
+ BN_cmp(curve_a, a) ||
+ BN_cmp(curve_b, b)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_group_set_curve,
+ EC_R_WRONG_CURVE_PARAMETERS);
+ goto err;
+ }
+ ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
+
+err:
+ BN_CTX_end(ctx);
+ BN_CTX_free(new_ctx);
+ return ret;
+}
+
+/* Takes the Jacobian coordinates (X, Y, Z) of a point and returns (X', Y') =
+ * (X/Z^2, Y/Z^3). */
+int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group,
+ const EC_POINT *point,
+ BIGNUM *x, BIGNUM *y,
+ BN_CTX *ctx) {
+ felem z1, z2, x_in, y_in;
+ smallfelem x_out, y_out;
+ longfelem tmp;
+
+ if (EC_POINT_is_at_infinity(group, point)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_point_get_affine_coordinates,
+ EC_R_POINT_AT_INFINITY);
+ return 0;
+ }
+ if (!BN_to_felem(x_in, &point->X) ||
+ !BN_to_felem(y_in, &point->Y) ||
+ !BN_to_felem(z1, &point->Z)) {
+ return 0;
+ }
+ felem_inv(z2, z1);
+ felem_square(tmp, z2);
+ felem_reduce(z1, tmp);
+ felem_mul(tmp, x_in, z1);
+ felem_reduce(x_in, tmp);
+ felem_contract(x_out, x_in);
+ if (x != NULL && !smallfelem_to_BN(x, x_out)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_point_get_affine_coordinates,
+ ERR_R_BN_LIB);
+ return 0;
+ }
+ felem_mul(tmp, z1, z2);
+ felem_reduce(z1, tmp);
+ felem_mul(tmp, y_in, z1);
+ felem_reduce(y_in, tmp);
+ felem_contract(y_out, y_in);
+ if (y != NULL && !smallfelem_to_BN(y, y_out)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_point_get_affine_coordinates,
+ ERR_R_BN_LIB);
+ return 0;
+ }
+ return 1;
+}
+
+/* points below is of size |num|, and tmp_smallfelems is of size |num+1| */
+static void make_points_affine(size_t num, smallfelem points[][3],
+ smallfelem tmp_smallfelems[]) {
+ /* Runs in constant time, unless an input is the point at infinity (which
+ * normally shouldn't happen). */
+ ec_GFp_nistp_points_make_affine_internal(
+ num, points, sizeof(smallfelem), tmp_smallfelems,
+ (void (*)(void *))smallfelem_one,
+ (int (*)(const void *))smallfelem_is_zero_int,
+ (void (*)(void *, const void *))smallfelem_assign,
+ (void (*)(void *, const void *))smallfelem_square_contract,
+ (void (*)(void *, const void *, const void *))smallfelem_mul_contract,
+ (void (*)(void *, const void *))smallfelem_inv_contract,
+ /* nothing to contract */
+ (void (*)(void *, const void *))smallfelem_assign);
+}
+
+/* Computes scalar*generator + \sum scalars[i]*points[i], ignoring NULL
+ * values Result is stored in r (r can equal one of the inputs). */
+int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
+ const BIGNUM *scalar, size_t num,
+ const EC_POINT *points[],
+ const BIGNUM *scalars[], BN_CTX *ctx) {
+ int ret = 0;
+ int j;
+ int mixed = 0;
+ BN_CTX *new_ctx = NULL;
+ BIGNUM *x, *y, *z, *tmp_scalar;
+ felem_bytearray g_secret;
+ felem_bytearray *secrets = NULL;
+ smallfelem(*pre_comp)[17][3] = NULL;
+ smallfelem *tmp_smallfelems = NULL;
+ felem_bytearray tmp;
+ unsigned i, num_bytes;
+ int have_pre_comp = 0;
+ size_t num_points = num;
+ smallfelem x_in, y_in, z_in;
+ felem x_out, y_out, z_out;
+ const smallfelem(*g_pre_comp)[16][3] = NULL;
+ EC_POINT *generator = NULL;
+ const EC_POINT *p = NULL;
+ const BIGNUM *p_scalar = NULL;
+
+ if (ctx == NULL) {
+ ctx = new_ctx = BN_CTX_new();
+ if (ctx == NULL) {
+ return 0;
+ }
+ }
+
+ BN_CTX_start(ctx);
+ if ((x = BN_CTX_get(ctx)) == NULL ||
+ (y = BN_CTX_get(ctx)) == NULL ||
+ (z = BN_CTX_get(ctx)) == NULL ||
+ (tmp_scalar = BN_CTX_get(ctx)) == NULL) {
+ goto err;
+ }
+
+ if (scalar != NULL) {
+ /* try to use the standard precomputation */
+ g_pre_comp = &gmul[0];
+ generator = EC_POINT_new(group);
+ if (generator == NULL) {
+ goto err;
+ }
+ /* get the generator from precomputation */
+ if (!smallfelem_to_BN(x, g_pre_comp[0][1][0]) ||
+ !smallfelem_to_BN(y, g_pre_comp[0][1][1]) ||
+ !smallfelem_to_BN(z, g_pre_comp[0][1][2])) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_points_mul, ERR_R_BN_LIB);
+ goto err;
+ }
+ if (!ec_point_set_Jprojective_coordinates_GFp(group, generator, x, y, z,
+ ctx)) {
+ goto err;
+ }
+ if (0 == EC_POINT_cmp(group, generator, group->generator, ctx)) {
+ /* precomputation matches generator */
+ have_pre_comp = 1;
+ } else {
+ /* we don't have valid precomputation: treat the generator as a
+ * random point. */
+ num_points++;
+ }
+ }
+
+ if (num_points > 0) {
+ if (num_points >= 3) {
+ /* unless we precompute multiples for just one or two points,
+ * converting those into affine form is time well spent */
+ mixed = 1;
+ }
+ secrets = OPENSSL_malloc(num_points * sizeof(felem_bytearray));
+ pre_comp = OPENSSL_malloc(num_points * 17 * 3 * sizeof(smallfelem));
+ if (mixed) {
+ tmp_smallfelems =
+ OPENSSL_malloc((num_points * 17 + 1) * sizeof(smallfelem));
+ }
+ if (secrets == NULL || pre_comp == NULL ||
+ (mixed && tmp_smallfelems == NULL)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_points_mul, ERR_R_MALLOC_FAILURE);
+ goto err;
+ }
+
+ /* we treat NULL scalars as 0, and NULL points as points at infinity,
+ * i.e., they contribute nothing to the linear combination. */
+ memset(secrets, 0, num_points * sizeof(felem_bytearray));
+ memset(pre_comp, 0, num_points * 17 * 3 * sizeof(smallfelem));
+ for (i = 0; i < num_points; ++i) {
+ if (i == num) {
+ /* we didn't have a valid precomputation, so we pick the generator. */
+ p = EC_GROUP_get0_generator(group);
+ p_scalar = scalar;
+ } else {
+ /* the i^th point */
+ p = points[i];
+ p_scalar = scalars[i];
+ }
+ if (p_scalar != NULL && p != NULL) {
+ /* reduce scalar to 0 <= scalar < 2^256 */
+ if (BN_num_bits(p_scalar) > 256 || BN_is_negative(p_scalar)) {
+ /* this is an unusual input, and we don't guarantee
+ * constant-timeness. */
+ if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_points_mul, ERR_R_BN_LIB);
+ goto err;
+ }
+ num_bytes = BN_bn2bin(tmp_scalar, tmp);
+ } else {
+ num_bytes = BN_bn2bin(p_scalar, tmp);
+ }
+ flip_endian(secrets[i], tmp, num_bytes);
+ /* precompute multiples */
+ if (!BN_to_felem(x_out, &p->X) ||
+ !BN_to_felem(y_out, &p->Y) ||
+ !BN_to_felem(z_out, &p->Z)) {
+ goto err;
+ }
+ felem_shrink(pre_comp[i][1][0], x_out);
+ felem_shrink(pre_comp[i][1][1], y_out);
+ felem_shrink(pre_comp[i][1][2], z_out);
+ for (j = 2; j <= 16; ++j) {
+ if (j & 1) {
+ point_add_small(pre_comp[i][j][0], pre_comp[i][j][1],
+ pre_comp[i][j][2], pre_comp[i][1][0],
+ pre_comp[i][1][1], pre_comp[i][1][2],
+ pre_comp[i][j - 1][0], pre_comp[i][j - 1][1],
+ pre_comp[i][j - 1][2]);
+ } else {
+ point_double_small(pre_comp[i][j][0], pre_comp[i][j][1],
+ pre_comp[i][j][2], pre_comp[i][j / 2][0],
+ pre_comp[i][j / 2][1], pre_comp[i][j / 2][2]);
+ }
+ }
+ }
+ }
+ if (mixed) {
+ make_points_affine(num_points * 17, pre_comp[0], tmp_smallfelems);
+ }
+ }
+
+ /* the scalar for the generator */
+ if (scalar != NULL && have_pre_comp) {
+ memset(g_secret, 0, sizeof(g_secret));
+ /* reduce scalar to 0 <= scalar < 2^256 */
+ if (BN_num_bits(scalar) > 256 || BN_is_negative(scalar)) {
+ /* this is an unusual input, and we don't guarantee
+ * constant-timeness. */
+ if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_points_mul, ERR_R_BN_LIB);
+ goto err;
+ }
+ num_bytes = BN_bn2bin(tmp_scalar, tmp);
+ } else {
+ num_bytes = BN_bn2bin(scalar, tmp);
+ }
+ flip_endian(g_secret, tmp, num_bytes);
+ /* do the multiplication with generator precomputation */
+ batch_mul(x_out, y_out, z_out, (const felem_bytearray(*))secrets,
+ num_points, g_secret, mixed, (const smallfelem(*)[17][3])pre_comp,
+ g_pre_comp);
+ } else {
+ /* do the multiplication without generator precomputation */
+ batch_mul(x_out, y_out, z_out, (const felem_bytearray(*))secrets,
+ num_points, NULL, mixed, (const smallfelem(*)[17][3])pre_comp,
+ NULL);
+ }
+
+ /* reduce the output to its unique minimal representation */
+ felem_contract(x_in, x_out);
+ felem_contract(y_in, y_out);
+ felem_contract(z_in, z_out);
+ if (!smallfelem_to_BN(x, x_in) ||
+ !smallfelem_to_BN(y, y_in) ||
+ !smallfelem_to_BN(z, z_in)) {
+ OPENSSL_PUT_ERROR(EC, ec_GFp_nistp256_points_mul, ERR_R_BN_LIB);
+ goto err;
+ }
+ ret = ec_point_set_Jprojective_coordinates_GFp(group, r, x, y, z, ctx);
+
+err:
+ BN_CTX_end(ctx);
+ EC_POINT_free(generator);
+ BN_CTX_free(new_ctx);
+ OPENSSL_free(secrets);
+ OPENSSL_free(pre_comp);
+ OPENSSL_free(tmp_smallfelems);
+ return ret;
+}
+
+const EC_METHOD *EC_GFp_nistp256_method(void) {
+ static const EC_METHOD ret = {
+ EC_FLAGS_DEFAULT_OCT,
+ ec_GFp_nistp256_group_init,
+ ec_GFp_simple_group_finish,
+ ec_GFp_simple_group_clear_finish,
+ ec_GFp_simple_group_copy, ec_GFp_nistp256_group_set_curve,
+ ec_GFp_simple_group_get_curve, ec_GFp_simple_group_get_degree,
+ ec_GFp_simple_group_check_discriminant, ec_GFp_simple_point_init,
+ ec_GFp_simple_point_finish, ec_GFp_simple_point_clear_finish,
+ ec_GFp_simple_point_copy, ec_GFp_simple_point_set_to_infinity,
+ ec_GFp_simple_set_Jprojective_coordinates_GFp,
+ ec_GFp_simple_get_Jprojective_coordinates_GFp,
+ ec_GFp_simple_point_set_affine_coordinates,
+ ec_GFp_nistp256_point_get_affine_coordinates,
+ 0 /* point_set_compressed_coordinates */, 0 /* point2oct */,
+ 0 /* oct2point */, ec_GFp_simple_add, ec_GFp_simple_dbl,
+ ec_GFp_simple_invert, ec_GFp_simple_is_at_infinity,
+ ec_GFp_simple_is_on_curve, ec_GFp_simple_cmp, ec_GFp_simple_make_affine,
+ ec_GFp_simple_points_make_affine, ec_GFp_nistp256_points_mul,
+ 0 /* precompute_mult */, 0 /* have_precompute_mult */,
+ ec_GFp_simple_field_mul, ec_GFp_simple_field_sqr, 0 /* field_div */,
+ 0 /* field_encode */, 0 /* field_decode */, 0 /* field_set_to_one */
+ };
+
+ return &ret;
+}
+
+#endif /* 64_BIT && !WINDOWS */
diff --git a/src/crypto/ec/simple.c b/src/crypto/ec/simple.c
index b3f96fa..69fd2e4 100644
--- a/src/crypto/ec/simple.c
+++ b/src/crypto/ec/simple.c
@@ -178,47 +178,55 @@ int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
tmp_a = BN_CTX_get(ctx);
- if (tmp_a == NULL)
+ if (tmp_a == NULL) {
goto err;
+ }
/* group->field */
- if (!BN_copy(&group->field, p))
+ if (!BN_copy(&group->field, p)) {
goto err;
+ }
BN_set_negative(&group->field, 0);
/* group->a */
- if (!BN_nnmod(tmp_a, a, p, ctx))
+ if (!BN_nnmod(tmp_a, a, p, ctx)) {
goto err;
+ }
if (group->meth->field_encode) {
- if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
+ if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) {
goto err;
- } else if (!BN_copy(&group->a, tmp_a))
+ }
+ } else if (!BN_copy(&group->a, tmp_a)) {
goto err;
+ }
/* group->b */
- if (!BN_nnmod(&group->b, b, p, ctx))
+ if (!BN_nnmod(&group->b, b, p, ctx)) {
goto err;
- if (group->meth->field_encode)
- if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
- goto err;
+ }
+ if (group->meth->field_encode &&
+ !group->meth->field_encode(group, &group->b, &group->b, ctx)) {
+ goto err;
+ }
/* group->a_is_minus3 */
- if (!BN_add_word(tmp_a, 3))
+ if (!BN_add_word(tmp_a, 3)) {
goto err;
+ }
group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
ret = 1;
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -227,34 +235,30 @@ int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
int ret = 0;
BN_CTX *new_ctx = NULL;
- if (p != NULL) {
- if (!BN_copy(p, &group->field))
- return 0;
+ if (p != NULL && !BN_copy(p, &group->field)) {
+ return 0;
}
if (a != NULL || b != NULL) {
if (group->meth->field_decode) {
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
- if (a != NULL) {
- if (!group->meth->field_decode(group, a, &group->a, ctx))
- goto err;
+ if (a != NULL && !group->meth->field_decode(group, a, &group->a, ctx)) {
+ goto err;
}
- if (b != NULL) {
- if (!group->meth->field_decode(group, b, &group->b, ctx))
- goto err;
+ if (b != NULL && !group->meth->field_decode(group, b, &group->b, ctx)) {
+ goto err;
}
} else {
- if (a != NULL) {
- if (!BN_copy(a, &group->a))
- goto err;
+ if (a != NULL && !BN_copy(a, &group->a)) {
+ goto err;
}
- if (b != NULL) {
- if (!BN_copy(b, &group->b))
- goto err;
+ if (b != NULL && !BN_copy(b, &group->b)) {
+ goto err;
}
}
}
@@ -262,8 +266,7 @@ int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
ret = 1;
err:
- if (new_ctx)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -291,54 +294,54 @@ int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) {
tmp_1 = BN_CTX_get(ctx);
tmp_2 = BN_CTX_get(ctx);
order = BN_CTX_get(ctx);
- if (order == NULL)
+ if (order == NULL) {
goto err;
+ }
if (group->meth->field_decode) {
- if (!group->meth->field_decode(group, a, &group->a, ctx))
- goto err;
- if (!group->meth->field_decode(group, b, &group->b, ctx))
+ if (!group->meth->field_decode(group, a, &group->a, ctx) ||
+ !group->meth->field_decode(group, b, &group->b, ctx)) {
goto err;
+ }
} else {
- if (!BN_copy(a, &group->a))
- goto err;
- if (!BN_copy(b, &group->b))
+ if (!BN_copy(a, &group->a) || !BN_copy(b, &group->b)) {
goto err;
+ }
}
/* check the discriminant:
* y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
* 0 =< a, b < p */
if (BN_is_zero(a)) {
- if (BN_is_zero(b))
+ if (BN_is_zero(b)) {
goto err;
+ }
} else if (!BN_is_zero(b)) {
- if (!BN_mod_sqr(tmp_1, a, p, ctx))
- goto err;
- if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
- goto err;
- if (!BN_lshift(tmp_1, tmp_2, 2))
+ if (!BN_mod_sqr(tmp_1, a, p, ctx) ||
+ !BN_mod_mul(tmp_2, tmp_1, a, p, ctx) ||
+ !BN_lshift(tmp_1, tmp_2, 2)) {
goto err;
+ }
/* tmp_1 = 4*a^3 */
- if (!BN_mod_sqr(tmp_2, b, p, ctx))
- goto err;
- if (!BN_mul_word(tmp_2, 27))
+ if (!BN_mod_sqr(tmp_2, b, p, ctx) ||
+ !BN_mul_word(tmp_2, 27)) {
goto err;
+ }
/* tmp_2 = 27*b^2 */
- if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
- goto err;
- if (BN_is_zero(a))
+ if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx) ||
+ BN_is_zero(a)) {
goto err;
+ }
}
ret = 1;
err:
- if (ctx != NULL)
+ if (ctx != NULL) {
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ }
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -365,12 +368,11 @@ void ec_GFp_simple_point_clear_finish(EC_POINT *point) {
}
int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) {
- if (!BN_copy(&dest->X, &src->X))
- return 0;
- if (!BN_copy(&dest->Y, &src->Y))
- return 0;
- if (!BN_copy(&dest->Z, &src->Z))
+ if (!BN_copy(&dest->X, &src->X) ||
+ !BN_copy(&dest->Y, &src->Y) ||
+ !BN_copy(&dest->Z, &src->Z)) {
return 0;
+ }
dest->Z_is_one = src->Z_is_one;
return 1;
@@ -391,41 +393,45 @@ int ec_GFp_simple_set_Jprojective_coordinates_GFp(
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
if (x != NULL) {
- if (!BN_nnmod(&point->X, x, &group->field, ctx))
+ if (!BN_nnmod(&point->X, x, &group->field, ctx)) {
+ goto err;
+ }
+ if (group->meth->field_encode &&
+ !group->meth->field_encode(group, &point->X, &point->X, ctx)) {
goto err;
- if (group->meth->field_encode) {
- if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
- goto err;
}
}
if (y != NULL) {
- if (!BN_nnmod(&point->Y, y, &group->field, ctx))
+ if (!BN_nnmod(&point->Y, y, &group->field, ctx)) {
+ goto err;
+ }
+ if (group->meth->field_encode &&
+ !group->meth->field_encode(group, &point->Y, &point->Y, ctx)) {
goto err;
- if (group->meth->field_encode) {
- if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
- goto err;
}
}
if (z != NULL) {
int Z_is_one;
- if (!BN_nnmod(&point->Z, z, &group->field, ctx))
+ if (!BN_nnmod(&point->Z, z, &group->field, ctx)) {
goto err;
+ }
Z_is_one = BN_is_one(&point->Z);
if (group->meth->field_encode) {
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))
+ 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;
@@ -434,8 +440,7 @@ int ec_GFp_simple_set_Jprojective_coordinates_GFp(
ret = 1;
err:
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -449,42 +454,36 @@ int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
if (group->meth->field_decode != 0) {
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
- if (x != NULL) {
- if (!group->meth->field_decode(group, x, &point->X, ctx))
- goto err;
+ if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) {
+ goto err;
}
- if (y != NULL) {
- if (!group->meth->field_decode(group, y, &point->Y, ctx))
- goto err;
+ if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) {
+ goto err;
}
- if (z != NULL) {
- if (!group->meth->field_decode(group, z, &point->Z, ctx))
- goto err;
+ if (z != NULL && !group->meth->field_decode(group, z, &point->Z, ctx)) {
+ goto err;
}
} else {
- if (x != NULL) {
- if (!BN_copy(x, &point->X))
- goto err;
+ if (x != NULL && !BN_copy(x, &point->X)) {
+ goto err;
}
- if (y != NULL) {
- if (!BN_copy(y, &point->Y))
- goto err;
+ if (y != NULL && !BN_copy(y, &point->Y)) {
+ goto err;
}
- if (z != NULL) {
- if (!BN_copy(z, &point->Z))
- goto err;
+ if (z != NULL && !BN_copy(z, &point->Z)) {
+ goto err;
}
}
ret = 1;
err:
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -518,8 +517,9 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
@@ -527,14 +527,16 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
Z_1 = BN_CTX_get(ctx);
Z_2 = BN_CTX_get(ctx);
Z_3 = BN_CTX_get(ctx);
- if (Z_3 == NULL)
+ if (Z_3 == NULL) {
goto err;
+ }
/* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
if (group->meth->field_decode) {
- if (!group->meth->field_decode(group, Z, &point->Z, ctx))
+ if (!group->meth->field_decode(group, Z, &point->Z, ctx)) {
goto err;
+ }
Z_ = Z;
} else {
Z_ = &point->Z;
@@ -542,22 +544,18 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
if (BN_is_one(Z_)) {
if (group->meth->field_decode) {
- if (x != NULL) {
- if (!group->meth->field_decode(group, x, &point->X, ctx))
- goto err;
+ if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) {
+ goto err;
}
- if (y != NULL) {
- if (!group->meth->field_decode(group, y, &point->Y, ctx))
- goto err;
+ if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) {
+ goto err;
}
} else {
- if (x != NULL) {
- if (!BN_copy(x, &point->X))
- goto err;
+ if (x != NULL && !BN_copy(x, &point->X)) {
+ goto err;
}
- if (y != NULL) {
- if (!BN_copy(y, &point->Y))
- goto err;
+ if (y != NULL && !BN_copy(y, &point->Y)) {
+ goto err;
}
}
} else {
@@ -569,34 +567,34 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
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))
+ 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) {
- /* in the Montgomery case, field_mul will cancel out Montgomery factor in
- * X: */
- if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
- goto err;
+ /* in the Montgomery case, field_mul will cancel out Montgomery factor in
+ * X: */
+ if (x != NULL && !group->meth->field_mul(group, x, &point->X, Z_2, ctx)) {
+ goto err;
}
if (y != NULL) {
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;
- } else {
- if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
+ if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) {
goto err;
+ }
+ } else if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) {
+ goto err;
}
/* in the Montgomery case, field_mul will cancel out Montgomery factor in
* Y: */
- if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
+ if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) {
goto err;
+ }
}
}
@@ -604,8 +602,7 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -619,12 +616,15 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
int ret = 0;
- if (a == b)
+ if (a == b) {
return EC_POINT_dbl(group, r, a, ctx);
- if (EC_POINT_is_at_infinity(group, a))
+ }
+ if (EC_POINT_is_at_infinity(group, a)) {
return EC_POINT_copy(r, b);
- if (EC_POINT_is_at_infinity(group, b))
+ }
+ if (EC_POINT_is_at_infinity(group, b)) {
return EC_POINT_copy(r, a);
+ }
field_mul = group->meth->field_mul;
field_sqr = group->meth->field_sqr;
@@ -632,8 +632,9 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
@@ -644,8 +645,9 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
n4 = BN_CTX_get(ctx);
n5 = BN_CTX_get(ctx);
n6 = BN_CTX_get(ctx);
- if (n6 == NULL)
+ if (n6 == NULL) {
goto end;
+ }
/* Note that in this function we must not read components of 'a' or 'b'
* once we have written the corresponding components of 'r'.
@@ -654,53 +656,51 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
/* n1, n2 */
if (b->Z_is_one) {
- if (!BN_copy(n1, &a->X))
- goto end;
- if (!BN_copy(n2, &a->Y))
+ if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) {
goto end;
+ }
/* n1 = X_a */
/* n2 = Y_a */
} else {
- if (!field_sqr(group, n0, &b->Z, ctx))
- goto end;
- if (!field_mul(group, n1, &a->X, n0, ctx))
+ if (!field_sqr(group, n0, &b->Z, ctx) ||
+ !field_mul(group, n1, &a->X, n0, ctx)) {
goto end;
+ }
/* n1 = X_a * Z_b^2 */
- if (!field_mul(group, n0, n0, &b->Z, ctx))
- goto end;
- if (!field_mul(group, n2, &a->Y, n0, ctx))
+ if (!field_mul(group, n0, n0, &b->Z, ctx) ||
+ !field_mul(group, n2, &a->Y, n0, ctx)) {
goto end;
+ }
/* n2 = Y_a * Z_b^3 */
}
/* n3, n4 */
if (a->Z_is_one) {
- if (!BN_copy(n3, &b->X))
- goto end;
- if (!BN_copy(n4, &b->Y))
+ if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) {
goto end;
+ }
/* n3 = X_b */
/* n4 = Y_b */
} else {
- if (!field_sqr(group, n0, &a->Z, ctx))
- goto end;
- if (!field_mul(group, n3, &b->X, n0, ctx))
+ if (!field_sqr(group, n0, &a->Z, ctx) ||
+ !field_mul(group, n3, &b->X, n0, ctx)) {
goto end;
+ }
/* n3 = X_b * Z_a^2 */
- if (!field_mul(group, n0, n0, &a->Z, ctx))
- goto end;
- if (!field_mul(group, n4, &b->Y, n0, ctx))
+ if (!field_mul(group, n0, n0, &a->Z, ctx) ||
+ !field_mul(group, n4, &b->Y, n0, ctx)) {
goto end;
+ }
/* n4 = Y_b * Z_a^3 */
}
/* n5, n6 */
- if (!BN_mod_sub_quick(n5, n1, n3, p))
- goto end;
- if (!BN_mod_sub_quick(n6, n2, n4, p))
+ if (!BN_mod_sub_quick(n5, n1, n3, p) ||
+ !BN_mod_sub_quick(n6, n2, n4, p)) {
goto end;
+ }
/* n5 = n1 - n3 */
/* n6 = n2 - n4 */
@@ -721,76 +721,79 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
}
/* 'n7', 'n8' */
- if (!BN_mod_add_quick(n1, n1, n3, p))
- goto end;
- if (!BN_mod_add_quick(n2, n2, n4, p))
+ if (!BN_mod_add_quick(n1, n1, n3, p) ||
+ !BN_mod_add_quick(n2, n2, n4, p)) {
goto end;
+ }
/* 'n7' = n1 + n3 */
/* 'n8' = n2 + n4 */
/* Z_r */
if (a->Z_is_one && b->Z_is_one) {
- if (!BN_copy(&r->Z, n5))
+ if (!BN_copy(&r->Z, n5)) {
goto end;
+ }
} else {
if (a->Z_is_one) {
- if (!BN_copy(n0, &b->Z))
+ if (!BN_copy(n0, &b->Z)) {
goto end;
+ }
} else if (b->Z_is_one) {
- if (!BN_copy(n0, &a->Z))
- goto end;
- } else {
- if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
+ if (!BN_copy(n0, &a->Z)) {
goto end;
+ }
+ } else if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) {
+ goto end;
}
- if (!field_mul(group, &r->Z, n0, n5, ctx))
+ if (!field_mul(group, &r->Z, n0, n5, ctx)) {
goto end;
+ }
}
r->Z_is_one = 0;
/* Z_r = Z_a * Z_b * n5 */
/* X_r */
- if (!field_sqr(group, n0, n6, ctx))
- goto end;
- if (!field_sqr(group, n4, n5, ctx))
- goto end;
- if (!field_mul(group, n3, n1, n4, ctx))
- goto end;
- if (!BN_mod_sub_quick(&r->X, n0, n3, p))
+ if (!field_sqr(group, n0, n6, ctx) ||
+ !field_sqr(group, n4, n5, ctx) ||
+ !field_mul(group, n3, n1, n4, ctx) ||
+ !BN_mod_sub_quick(&r->X, n0, n3, p)) {
goto end;
+ }
/* X_r = n6^2 - n5^2 * 'n7' */
/* 'n9' */
- if (!BN_mod_lshift1_quick(n0, &r->X, p))
- goto end;
- if (!BN_mod_sub_quick(n0, n3, n0, p))
+ if (!BN_mod_lshift1_quick(n0, &r->X, p) ||
+ !BN_mod_sub_quick(n0, n3, n0, p)) {
goto end;
+ }
/* n9 = n5^2 * 'n7' - 2 * X_r */
/* Y_r */
- if (!field_mul(group, n0, n0, n6, ctx))
- goto end;
- if (!field_mul(group, n5, n4, n5, ctx))
+ if (!field_mul(group, n0, n0, n6, ctx) ||
+ !field_mul(group, n5, n4, n5, ctx)) {
goto end; /* now n5 is n5^3 */
- if (!field_mul(group, n1, n2, n5, ctx))
+ }
+ if (!field_mul(group, n1, n2, n5, ctx) ||
+ !BN_mod_sub_quick(n0, n0, n1, p)) {
goto end;
- if (!BN_mod_sub_quick(n0, n0, n1, p))
+ }
+ if (BN_is_odd(n0) && !BN_add(n0, n0, p)) {
goto end;
- if (BN_is_odd(n0))
- if (!BN_add(n0, n0, p))
- goto end;
+ }
/* now 0 <= n0 < 2*p, and n0 is even */
- if (!BN_rshift1(&r->Y, n0))
+ if (!BN_rshift1(&r->Y, n0)) {
goto end;
+ }
/* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
ret = 1;
end:
- if (ctx) /* otherwise we already called BN_CTX_end */
+ if (ctx) {
+ /* otherwise we already called BN_CTX_end */
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ }
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -816,8 +819,9 @@ int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
@@ -825,8 +829,9 @@ int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
n1 = BN_CTX_get(ctx);
n2 = BN_CTX_get(ctx);
n3 = BN_CTX_get(ctx);
- if (n3 == NULL)
+ if (n3 == NULL) {
goto err;
+ }
/* Note that in this function we must not read components of 'a'
* once we have written the corresponding components of 'r'.
@@ -835,108 +840,95 @@ int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
/* n1 */
if (a->Z_is_one) {
- if (!field_sqr(group, n0, &a->X, ctx))
- goto err;
- if (!BN_mod_lshift1_quick(n1, n0, p))
- goto err;
- if (!BN_mod_add_quick(n0, n0, n1, p))
- goto err;
- if (!BN_mod_add_quick(n1, n0, &group->a, p))
+ if (!field_sqr(group, n0, &a->X, ctx) ||
+ !BN_mod_lshift1_quick(n1, n0, p) ||
+ !BN_mod_add_quick(n0, n0, n1, p) ||
+ !BN_mod_add_quick(n1, n0, &group->a, p)) {
goto err;
+ }
/* n1 = 3 * X_a^2 + a_curve */
} else if (group->a_is_minus3) {
- if (!field_sqr(group, n1, &a->Z, ctx))
- goto err;
- if (!BN_mod_add_quick(n0, &a->X, n1, p))
- goto err;
- if (!BN_mod_sub_quick(n2, &a->X, n1, p))
- goto err;
- if (!field_mul(group, n1, n0, n2, ctx))
- goto err;
- if (!BN_mod_lshift1_quick(n0, n1, p))
- goto err;
- if (!BN_mod_add_quick(n1, n0, n1, p))
+ if (!field_sqr(group, n1, &a->Z, ctx) ||
+ !BN_mod_add_quick(n0, &a->X, n1, p) ||
+ !BN_mod_sub_quick(n2, &a->X, n1, p) ||
+ !field_mul(group, n1, n0, n2, ctx) ||
+ !BN_mod_lshift1_quick(n0, n1, p) ||
+ !BN_mod_add_quick(n1, n0, n1, p)) {
goto err;
+ }
/* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
* = 3 * X_a^2 - 3 * Z_a^4 */
} else {
- if (!field_sqr(group, n0, &a->X, ctx))
- goto err;
- if (!BN_mod_lshift1_quick(n1, n0, p))
- goto err;
- if (!BN_mod_add_quick(n0, n0, n1, p))
- goto err;
- if (!field_sqr(group, n1, &a->Z, ctx))
- goto err;
- if (!field_sqr(group, n1, n1, ctx))
- goto err;
- if (!field_mul(group, n1, n1, &group->a, ctx))
- goto err;
- if (!BN_mod_add_quick(n1, n1, n0, p))
+ if (!field_sqr(group, n0, &a->X, ctx) ||
+ !BN_mod_lshift1_quick(n1, n0, p) ||
+ !BN_mod_add_quick(n0, n0, n1, p) ||
+ !field_sqr(group, n1, &a->Z, ctx) ||
+ !field_sqr(group, n1, n1, ctx) ||
+ !field_mul(group, n1, n1, &group->a, ctx) ||
+ !BN_mod_add_quick(n1, n1, n0, p)) {
goto err;
+ }
/* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
}
/* Z_r */
if (a->Z_is_one) {
- if (!BN_copy(n0, &a->Y))
- goto err;
- } else {
- if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
+ if (!BN_copy(n0, &a->Y)) {
goto err;
+ }
+ } else if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) {
+ goto err;
}
- if (!BN_mod_lshift1_quick(&r->Z, n0, p))
+ if (!BN_mod_lshift1_quick(&r->Z, n0, p)) {
goto err;
+ }
r->Z_is_one = 0;
/* Z_r = 2 * Y_a * Z_a */
/* n2 */
- if (!field_sqr(group, n3, &a->Y, ctx))
- goto err;
- if (!field_mul(group, n2, &a->X, n3, ctx))
- goto err;
- if (!BN_mod_lshift_quick(n2, n2, 2, p))
+ if (!field_sqr(group, n3, &a->Y, ctx) ||
+ !field_mul(group, n2, &a->X, n3, ctx) ||
+ !BN_mod_lshift_quick(n2, n2, 2, p)) {
goto err;
+ }
/* n2 = 4 * X_a * Y_a^2 */
/* X_r */
- if (!BN_mod_lshift1_quick(n0, n2, p))
- goto err;
- if (!field_sqr(group, &r->X, n1, ctx))
- goto err;
- if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
+ if (!BN_mod_lshift1_quick(n0, n2, p) ||
+ !field_sqr(group, &r->X, n1, ctx) ||
+ !BN_mod_sub_quick(&r->X, &r->X, n0, p)) {
goto err;
+ }
/* X_r = n1^2 - 2 * n2 */
/* n3 */
- if (!field_sqr(group, n0, n3, ctx))
- goto err;
- if (!BN_mod_lshift_quick(n3, n0, 3, p))
+ if (!field_sqr(group, n0, n3, ctx) ||
+ !BN_mod_lshift_quick(n3, n0, 3, p)) {
goto err;
+ }
/* n3 = 8 * Y_a^4 */
/* Y_r */
- if (!BN_mod_sub_quick(n0, n2, &r->X, p))
- goto err;
- if (!field_mul(group, n0, n1, n0, ctx))
- goto err;
- if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
+ if (!BN_mod_sub_quick(n0, n2, &r->X, p) ||
+ !field_mul(group, n0, n1, n0, ctx) ||
+ !BN_mod_sub_quick(&r->Y, n0, n3, p)) {
goto err;
+ }
/* Y_r = n1 * (n2 - X_r) - n3 */
ret = 1;
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) {
- if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
+ if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) {
/* point is its own inverse */
return 1;
+ }
return BN_usub(&point->Y, &group->field, &point->Y);
}
@@ -955,8 +947,9 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
BIGNUM *rh, *tmp, *Z4, *Z6;
int ret = -1;
- if (EC_POINT_is_at_infinity(group, point))
+ if (EC_POINT_is_at_infinity(group, point)) {
return 1;
+ }
field_mul = group->meth->field_mul;
field_sqr = group->meth->field_sqr;
@@ -964,8 +957,9 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return -1;
+ }
}
BN_CTX_start(ctx);
@@ -973,8 +967,9 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
tmp = BN_CTX_get(ctx);
Z4 = BN_CTX_get(ctx);
Z6 = BN_CTX_get(ctx);
- if (Z6 == NULL)
+ if (Z6 == NULL) {
goto err;
+ }
/* We have a curve defined by a Weierstrass equation
* y^2 = x^3 + a*x + b.
@@ -987,64 +982,62 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
*/
/* rh := X^2 */
- if (!field_sqr(group, rh, &point->X, ctx))
+ if (!field_sqr(group, rh, &point->X, ctx)) {
goto err;
+ }
if (!point->Z_is_one) {
- if (!field_sqr(group, tmp, &point->Z, ctx))
- goto err;
- if (!field_sqr(group, Z4, tmp, ctx))
- goto err;
- if (!field_mul(group, Z6, Z4, tmp, ctx))
+ if (!field_sqr(group, tmp, &point->Z, ctx) ||
+ !field_sqr(group, Z4, tmp, ctx) ||
+ !field_mul(group, Z6, Z4, tmp, ctx)) {
goto err;
+ }
/* rh := (rh + a*Z^4)*X */
if (group->a_is_minus3) {
- if (!BN_mod_lshift1_quick(tmp, Z4, p))
- goto err;
- if (!BN_mod_add_quick(tmp, tmp, Z4, p))
- goto err;
- if (!BN_mod_sub_quick(rh, rh, tmp, p))
- goto err;
- if (!field_mul(group, rh, rh, &point->X, ctx))
+ if (!BN_mod_lshift1_quick(tmp, Z4, p) ||
+ !BN_mod_add_quick(tmp, tmp, Z4, p) ||
+ !BN_mod_sub_quick(rh, rh, tmp, p) ||
+ !field_mul(group, rh, rh, &point->X, ctx)) {
goto err;
+ }
} else {
- if (!field_mul(group, tmp, Z4, &group->a, ctx))
- goto err;
- if (!BN_mod_add_quick(rh, rh, tmp, p))
- goto err;
- if (!field_mul(group, rh, rh, &point->X, ctx))
+ if (!field_mul(group, tmp, Z4, &group->a, ctx) ||
+ !BN_mod_add_quick(rh, rh, tmp, p) ||
+ !field_mul(group, rh, rh, &point->X, ctx)) {
goto err;
+ }
}
/* rh := rh + b*Z^6 */
- if (!field_mul(group, tmp, &group->b, Z6, ctx))
- goto err;
- if (!BN_mod_add_quick(rh, rh, tmp, p))
+ if (!field_mul(group, tmp, &group->b, Z6, ctx) ||
+ !BN_mod_add_quick(rh, rh, tmp, p)) {
goto err;
+ }
} else {
/* point->Z_is_one */
/* rh := (rh + a)*X */
- if (!BN_mod_add_quick(rh, rh, &group->a, p))
- goto err;
- if (!field_mul(group, rh, rh, &point->X, ctx))
+ if (!BN_mod_add_quick(rh, rh, &group->a, p) ||
+ !field_mul(group, rh, rh, &point->X, ctx)) {
goto err;
+ }
/* rh := rh + b */
- if (!BN_mod_add_quick(rh, rh, &group->b, p))
+ if (!BN_mod_add_quick(rh, rh, &group->b, p)) {
goto err;
+ }
}
/* 'lh' := Y^2 */
- if (!field_sqr(group, tmp, &point->Y, ctx))
+ if (!field_sqr(group, tmp, &point->Y, ctx)) {
goto err;
+ }
ret = (0 == BN_ucmp(tmp, rh));
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -1068,8 +1061,9 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
}
- if (EC_POINT_is_at_infinity(group, b))
+ if (EC_POINT_is_at_infinity(group, b)) {
return 1;
+ }
if (a->Z_is_one && b->Z_is_one) {
return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
@@ -1080,8 +1074,9 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return -1;
+ }
}
BN_CTX_start(ctx);
@@ -1089,8 +1084,9 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
tmp2 = BN_CTX_get(ctx);
Za23 = BN_CTX_get(ctx);
Zb23 = BN_CTX_get(ctx);
- if (Zb23 == NULL)
+ if (Zb23 == NULL) {
goto end;
+ }
/* We have to decide whether
* (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
@@ -1099,21 +1095,23 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
*/
if (!b->Z_is_one) {
- if (!field_sqr(group, Zb23, &b->Z, ctx))
- goto end;
- if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
+ if (!field_sqr(group, Zb23, &b->Z, ctx) ||
+ !field_mul(group, tmp1, &a->X, Zb23, ctx)) {
goto end;
+ }
tmp1_ = tmp1;
- } else
+ } else {
tmp1_ = &a->X;
+ }
if (!a->Z_is_one) {
- if (!field_sqr(group, Za23, &a->Z, ctx))
- goto end;
- if (!field_mul(group, tmp2, &b->X, Za23, ctx))
+ if (!field_sqr(group, Za23, &a->Z, ctx) ||
+ !field_mul(group, tmp2, &b->X, Za23, ctx)) {
goto end;
+ }
tmp2_ = tmp2;
- } else
+ } else {
tmp2_ = &b->X;
+ }
/* compare X_a*Z_b^2 with X_b*Z_a^2 */
if (BN_cmp(tmp1_, tmp2_) != 0) {
@@ -1123,21 +1121,23 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
if (!b->Z_is_one) {
- if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
- goto end;
- if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
+ if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) ||
+ !field_mul(group, tmp1, &a->Y, Zb23, ctx)) {
goto end;
+ }
/* tmp1_ = tmp1 */
- } else
+ } else {
tmp1_ = &a->Y;
+ }
if (!a->Z_is_one) {
- if (!field_mul(group, Za23, Za23, &a->Z, ctx))
- goto end;
- if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
+ if (!field_mul(group, Za23, Za23, &a->Z, ctx) ||
+ !field_mul(group, tmp2, &b->Y, Za23, ctx)) {
goto end;
+ }
/* tmp2_ = tmp2 */
- } else
+ } else {
tmp2_ = &b->Y;
+ }
/* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
if (BN_cmp(tmp1_, tmp2_) != 0) {
@@ -1150,8 +1150,7 @@ int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
end:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -1161,25 +1160,28 @@ int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
BIGNUM *x, *y;
int ret = 0;
- if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
+ if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) {
return 1;
+ }
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
return 0;
+ }
}
BN_CTX_start(ctx);
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
- if (y == NULL)
+ if (y == NULL) {
goto err;
+ }
- if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
- goto err;
- if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
+ if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx) ||
+ !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
goto err;
+ }
if (!point->Z_is_one) {
OPENSSL_PUT_ERROR(EC, ec_GFp_simple_make_affine, ERR_R_INTERNAL_ERROR);
goto err;
@@ -1189,8 +1191,7 @@ int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
+ BN_CTX_free(new_ctx);
return ret;
}
@@ -1335,9 +1336,7 @@ int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
err:
BN_CTX_end(ctx);
- if (new_ctx != NULL) {
- BN_CTX_free(new_ctx);
- }
+ BN_CTX_free(new_ctx);
if (prod_Z != NULL) {
for (i = 0; i < num; i++) {
if (prod_Z[i] == NULL) {
diff --git a/src/crypto/ec/util-64.c b/src/crypto/ec/util-64.c
new file mode 100644
index 0000000..171b063
--- /dev/null
+++ b/src/crypto/ec/util-64.c
@@ -0,0 +1,183 @@
+/* Copyright (c) 2015, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <openssl/base.h>
+
+
+#if defined(OPENSSL_64_BIT) && !defined(OPENSSL_WINDOWS)
+
+#include <openssl/ec.h>
+
+#include "internal.h"
+
+/* Convert an array of points into affine coordinates. (If the point at
+ * infinity is found (Z = 0), it remains unchanged.) This function is
+ * essentially an equivalent to EC_POINTs_make_affine(), but works with the
+ * internal representation of points as used by ecp_nistp###.c rather than
+ * with (BIGNUM-based) EC_POINT data structures. point_array is the
+ * input/output buffer ('num' points in projective form, i.e. three
+ * coordinates each), based on an internal representation of field elements
+ * of size 'felem_size'. tmp_felems needs to point to a temporary array of
+ * 'num'+1 field elements for storage of intermediate values. */
+void ec_GFp_nistp_points_make_affine_internal(
+ size_t num, void *point_array, size_t felem_size, void *tmp_felems,
+ void (*felem_one)(void *out), int (*felem_is_zero)(const void *in),
+ void (*felem_assign)(void *out, const void *in),
+ void (*felem_square)(void *out, const void *in),
+ void (*felem_mul)(void *out, const void *in1, const void *in2),
+ void (*felem_inv)(void *out, const void *in),
+ void (*felem_contract)(void *out, const void *in)) {
+ int i = 0;
+
+#define tmp_felem(I) (&((char *)tmp_felems)[(I)*felem_size])
+#define X(I) (&((char *)point_array)[3 * (I)*felem_size])
+#define Y(I) (&((char *)point_array)[(3 * (I) + 1) * felem_size])
+#define Z(I) (&((char *)point_array)[(3 * (I) + 2) * felem_size])
+
+ if (!felem_is_zero(Z(0))) {
+ felem_assign(tmp_felem(0), Z(0));
+ } else {
+ felem_one(tmp_felem(0));
+ }
+
+ for (i = 1; i < (int)num; i++) {
+ if (!felem_is_zero(Z(i))) {
+ felem_mul(tmp_felem(i), tmp_felem(i - 1), Z(i));
+ } else {
+ felem_assign(tmp_felem(i), tmp_felem(i - 1));
+ }
+ }
+ /* Now each tmp_felem(i) is the product of Z(0) .. Z(i), skipping any
+ * zero-valued factors: if Z(i) = 0, we essentially pretend that Z(i) = 1. */
+
+ felem_inv(tmp_felem(num - 1), tmp_felem(num - 1));
+ for (i = num - 1; i >= 0; i--) {
+ if (i > 0) {
+ /* tmp_felem(i-1) is the product of Z(0) .. Z(i-1), tmp_felem(i)
+ * is the inverse of the product of Z(0) .. Z(i). */
+ /* 1/Z(i) */
+ felem_mul(tmp_felem(num), tmp_felem(i - 1), tmp_felem(i));
+ } else {
+ felem_assign(tmp_felem(num), tmp_felem(0)); /* 1/Z(0) */
+ }
+
+ if (!felem_is_zero(Z(i))) {
+ if (i > 0) {
+ /* For next iteration, replace tmp_felem(i-1) by its inverse. */
+ felem_mul(tmp_felem(i - 1), tmp_felem(i), Z(i));
+ }
+
+ /* Convert point (X, Y, Z) into affine form (X/(Z^2), Y/(Z^3), 1). */
+ felem_square(Z(i), tmp_felem(num)); /* 1/(Z^2) */
+ felem_mul(X(i), X(i), Z(i)); /* X/(Z^2) */
+ felem_mul(Z(i), Z(i), tmp_felem(num)); /* 1/(Z^3) */
+ felem_mul(Y(i), Y(i), Z(i)); /* Y/(Z^3) */
+ felem_contract(X(i), X(i));
+ felem_contract(Y(i), Y(i));
+ felem_one(Z(i));
+ } else {
+ if (i > 0) {
+ /* For next iteration, replace tmp_felem(i-1) by its inverse. */
+ felem_assign(tmp_felem(i - 1), tmp_felem(i));
+ }
+ }
+ }
+}
+
+/* This function looks at 5+1 scalar bits (5 current, 1 adjacent less
+ * significant bit), and recodes them into a signed digit for use in fast point
+ * multiplication: the use of signed rather than unsigned digits means that
+ * fewer points need to be precomputed, given that point inversion is easy (a
+ * precomputed point dP makes -dP available as well).
+ *
+ * BACKGROUND:
+ *
+ * Signed digits for multiplication were introduced by Booth ("A signed binary
+ * multiplication technique", Quart. Journ. Mech. and Applied Math., vol. IV,
+ * pt. 2 (1951), pp. 236-240), in that case for multiplication of integers.
+ * Booth's original encoding did not generally improve the density of nonzero
+ * digits over the binary representation, and was merely meant to simplify the
+ * handling of signed factors given in two's complement; but it has since been
+ * shown to be the basis of various signed-digit representations that do have
+ * further advantages, including the wNAF, using the following general
+ * approach:
+ *
+ * (1) Given a binary representation
+ *
+ * b_k ... b_2 b_1 b_0,
+ *
+ * of a nonnegative integer (b_k in {0, 1}), rewrite it in digits 0, 1, -1
+ * by using bit-wise subtraction as follows:
+ *
+ * b_k b_(k-1) ... b_2 b_1 b_0
+ * - b_k ... b_3 b_2 b_1 b_0
+ * -------------------------------------
+ * s_k b_(k-1) ... s_3 s_2 s_1 s_0
+ *
+ * A left-shift followed by subtraction of the original value yields a new
+ * representation of the same value, using signed bits s_i = b_(i+1) - b_i.
+ * This representation from Booth's paper has since appeared in the
+ * literature under a variety of different names including "reversed binary
+ * form", "alternating greedy expansion", "mutual opposite form", and
+ * "sign-alternating {+-1}-representation".
+ *
+ * An interesting property is that among the nonzero bits, values 1 and -1
+ * strictly alternate.
+ *
+ * (2) Various window schemes can be applied to the Booth representation of
+ * integers: for example, right-to-left sliding windows yield the wNAF
+ * (a signed-digit encoding independently discovered by various researchers
+ * in the 1990s), and left-to-right sliding windows yield a left-to-right
+ * equivalent of the wNAF (independently discovered by various researchers
+ * around 2004).
+ *
+ * To prevent leaking information through side channels in point multiplication,
+ * we need to recode the given integer into a regular pattern: sliding windows
+ * as in wNAFs won't do, we need their fixed-window equivalent -- which is a few
+ * decades older: we'll be using the so-called "modified Booth encoding" due to
+ * MacSorley ("High-speed arithmetic in binary computers", Proc. IRE, vol. 49
+ * (1961), pp. 67-91), in a radix-2^5 setting. That is, we always combine five
+ * signed bits into a signed digit:
+ *
+ * s_(4j + 4) s_(4j + 3) s_(4j + 2) s_(4j + 1) s_(4j)
+ *
+ * The sign-alternating property implies that the resulting digit values are
+ * integers from -16 to 16.
+ *
+ * Of course, we don't actually need to compute the signed digits s_i as an
+ * intermediate step (that's just a nice way to see how this scheme relates
+ * to the wNAF): a direct computation obtains the recoded digit from the
+ * six bits b_(4j + 4) ... b_(4j - 1).
+ *
+ * This function takes those five bits as an integer (0 .. 63), writing the
+ * recoded digit to *sign (0 for positive, 1 for negative) and *digit (absolute
+ * value, in the range 0 .. 8). Note that this integer essentially provides the
+ * input bits "shifted to the left" by one position: for example, the input to
+ * compute the least significant recoded digit, given that there's no bit b_-1,
+ * has to be b_4 b_3 b_2 b_1 b_0 0. */
+void ec_GFp_nistp_recode_scalar_bits(uint8_t *sign, uint8_t *digit,
+ uint8_t in) {
+ uint8_t s, d;
+
+ s = ~((in >> 5) - 1); /* sets all bits to MSB(in), 'in' seen as
+ * 6-bit value */
+ d = (1 << 6) - in - 1;
+ d = (d & s) | (in & ~s);
+ d = (d >> 1) + (d & 1);
+
+ *sign = s & 1;
+ *digit = d;
+}
+
+#endif /* 64_BIT && !WINDOWS */
diff --git a/src/crypto/ec/wnaf.c b/src/crypto/ec/wnaf.c
index 9016328..d87a7d9 100644
--- a/src/crypto/ec/wnaf.c
+++ b/src/crypto/ec/wnaf.c
@@ -72,6 +72,7 @@
#include <openssl/bn.h>
#include <openssl/err.h>
#include <openssl/mem.h>
+#include <openssl/thread.h>
#include "internal.h"
@@ -84,7 +85,6 @@
/* structure for precomputed multiples of the generator */
typedef struct ec_pre_comp_st {
- const EC_GROUP *group; /* parent EC_GROUP object */
size_t blocksize; /* block size for wNAF splitting */
size_t numblocks; /* max. number of blocks for which we have precomputation */
size_t w; /* window size */
@@ -94,18 +94,14 @@ typedef struct ec_pre_comp_st {
int references;
} EC_PRE_COMP;
-static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) {
+static EC_PRE_COMP *ec_pre_comp_new(void) {
EC_PRE_COMP *ret = NULL;
- if (!group)
- return NULL;
-
ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP));
if (!ret) {
OPENSSL_PUT_ERROR(EC, ec_pre_comp_new, ERR_R_MALLOC_FAILURE);
return ret;
}
- ret->group = group;
ret->blocksize = 8; /* default */
ret->numblocks = 0;
ret->w = 4; /* default */
@@ -125,14 +121,8 @@ void *ec_pre_comp_dup(EC_PRE_COMP *pre_comp) {
}
void ec_pre_comp_free(EC_PRE_COMP *pre_comp) {
- int i;
-
- if (!pre_comp) {
- return;
- }
-
- i = CRYPTO_add(&pre_comp->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
- if (i > 0) {
+ if (pre_comp == NULL ||
+ CRYPTO_add(&pre_comp->references, -1, CRYPTO_LOCK_EC_PRE_COMP) > 0) {
return;
}
@@ -272,8 +262,9 @@ err:
OPENSSL_free(r);
r = NULL;
}
- if (ok)
+ if (ok) {
*ret_len = len;
+ }
return r;
}
@@ -341,8 +332,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
goto err;
+ }
}
if (scalar != NULL) {
@@ -365,8 +357,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
numblocks = (BN_num_bits(scalar) / blocksize) + 1;
/* we cannot use more blocks than we have precomputation for */
- if (numblocks > pre_comp->numblocks)
+ if (numblocks > pre_comp->numblocks) {
numblocks = pre_comp->numblocks;
+ }
pre_points_per_block = (size_t)1 << (pre_comp->w - 1);
@@ -413,10 +406,12 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
wNAF[i + 1] = NULL; /* make sure we always have a pivot */
wNAF[i] =
compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
- if (wNAF[i] == NULL)
+ if (wNAF[i] == NULL) {
goto err;
- if (wNAF_len[i] > max_len)
+ }
+ if (wNAF_len[i] > max_len) {
max_len = wNAF_len[i];
+ }
}
if (numblocks) {
@@ -440,8 +435,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
/* use the window size for which we have precomputation */
wsize[num] = pre_comp->w;
tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
- if (!tmp_wNAF)
+ if (!tmp_wNAF) {
goto err;
+ }
if (tmp_len <= max_len) {
/* One of the other wNAFs is at least as long
@@ -484,10 +480,11 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
goto err;
}
tmp_len -= blocksize;
- } else
+ } else {
/* last block gets whatever is left
* (this could be more or less than 'blocksize'!) */
wNAF_len[i] = tmp_len;
+ }
wNAF[i + 1] = NULL;
wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
@@ -497,8 +494,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
goto err;
}
memcpy(wNAF[i], pp, wNAF_len[i]);
- if (wNAF_len[i] > max_len)
+ if (wNAF_len[i] > max_len) {
max_len = wNAF_len[i];
+ }
if (*tmp_points == NULL) {
OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR);
@@ -531,8 +529,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
val_sub[i] = v;
for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) {
*v = EC_POINT_new(group);
- if (*v == NULL)
+ if (*v == NULL) {
goto err;
+ }
v++;
}
}
@@ -541,8 +540,9 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
goto err;
}
- if (!(tmp = EC_POINT_new(group)))
+ if (!(tmp = EC_POINT_new(group))) {
goto err;
+ }
/* prepare precomputed values:
* val_sub[i][0] := points[i]
@@ -552,34 +552,36 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
*/
for (i = 0; i < num + num_scalar; i++) {
if (i < num) {
- if (!EC_POINT_copy(val_sub[i][0], points[i]))
- goto err;
- } else {
- if (!EC_POINT_copy(val_sub[i][0], generator))
+ if (!EC_POINT_copy(val_sub[i][0], points[i])) {
goto err;
+ }
+ } else if (!EC_POINT_copy(val_sub[i][0], generator)) {
+ goto err;
}
if (wsize[i] > 1) {
- if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
+ if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) {
goto err;
+ }
for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) {
- if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
+ if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) {
goto err;
+ }
}
}
}
#if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
- if (!EC_POINTs_make_affine(group, num_val, val, ctx))
+ if (!EC_POINTs_make_affine(group, num_val, val, ctx)) {
goto err;
+ }
#endif
r_is_at_infinity = 1;
for (k = max_len - 1; k >= 0; k--) {
- if (!r_is_at_infinity) {
- if (!EC_POINT_dbl(group, r, r, ctx))
- goto err;
+ if (!r_is_at_infinity && !EC_POINT_dbl(group, r, r, ctx)) {
+ goto err;
}
for (i = 0; i < totalnum; i++) {
@@ -590,13 +592,13 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
if (digit) {
is_neg = digit < 0;
- if (is_neg)
+ if (is_neg) {
digit = -digit;
+ }
if (is_neg != r_is_inverted) {
- if (!r_is_at_infinity) {
- if (!EC_POINT_invert(group, r, ctx))
- goto err;
+ if (!r_is_at_infinity && !EC_POINT_invert(group, r, ctx)) {
+ goto err;
}
r_is_inverted = !r_is_inverted;
}
@@ -604,12 +606,14 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
/* digit > 0 */
if (r_is_at_infinity) {
- if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
+ if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) {
goto err;
+ }
r_is_at_infinity = 0;
} else {
- if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx))
+ if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) {
goto err;
+ }
}
}
}
@@ -617,42 +621,37 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
}
if (r_is_at_infinity) {
- if (!EC_POINT_set_to_infinity(group, r))
+ if (!EC_POINT_set_to_infinity(group, r)) {
goto err;
- } else {
- if (r_is_inverted)
- if (!EC_POINT_invert(group, r, ctx))
- goto err;
+ }
+ } else if (r_is_inverted && !EC_POINT_invert(group, r, ctx)) {
+ goto err;
}
ret = 1;
err:
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- if (tmp != NULL)
- EC_POINT_free(tmp);
- if (wsize != NULL)
- OPENSSL_free(wsize);
- if (wNAF_len != NULL)
- OPENSSL_free(wNAF_len);
+ BN_CTX_free(new_ctx);
+ EC_POINT_free(tmp);
+ OPENSSL_free(wsize);
+ OPENSSL_free(wNAF_len);
if (wNAF != NULL) {
signed char **w;
- for (w = wNAF; *w != NULL; w++)
+ for (w = wNAF; *w != NULL; w++) {
OPENSSL_free(*w);
+ }
OPENSSL_free(wNAF);
}
if (val != NULL) {
- for (v = val; *v != NULL; v++)
+ for (v = val; *v != NULL; v++) {
EC_POINT_clear_free(*v);
+ }
OPENSSL_free(val);
}
- if (val_sub != NULL) {
- OPENSSL_free(val_sub);
- }
+ OPENSSL_free(val_sub);
return ret;
}
@@ -690,33 +689,36 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) {
int ret = 0;
/* if there is an old EC_PRE_COMP object, throw it away */
- if (group->pre_comp) {
- ec_pre_comp_free(group->pre_comp);
- group->pre_comp = NULL;
- }
-
- if ((pre_comp = ec_pre_comp_new(group)) == NULL)
- return 0;
+ ec_pre_comp_free(group->pre_comp);
+ group->pre_comp = NULL;
generator = EC_GROUP_get0_generator(group);
if (generator == NULL) {
OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, EC_R_UNDEFINED_GENERATOR);
- goto err;
+ return 0;
+ }
+
+ pre_comp = ec_pre_comp_new();
+ if (pre_comp == NULL) {
+ return 0;
}
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
- if (ctx == NULL)
+ if (ctx == NULL) {
goto err;
+ }
}
BN_CTX_start(ctx);
order = BN_CTX_get(ctx);
- if (order == NULL)
+ if (order == NULL) {
goto err;
+ }
- if (!EC_GROUP_get_order(group, order, ctx))
+ if (!EC_GROUP_get_order(group, order, ctx)) {
goto err;
+ }
if (BN_is_zero(order)) {
OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, EC_R_UNKNOWN_ORDER);
goto err;
@@ -764,23 +766,27 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) {
goto err;
}
- if (!EC_POINT_copy(base, generator))
+ if (!EC_POINT_copy(base, generator)) {
goto err;
+ }
/* do the precomputation */
for (i = 0; i < numblocks; i++) {
size_t j;
- if (!EC_POINT_dbl(group, tmp_point, base, ctx))
+ if (!EC_POINT_dbl(group, tmp_point, base, ctx)) {
goto err;
+ }
- if (!EC_POINT_copy(*var++, base))
+ if (!EC_POINT_copy(*var++, base)) {
goto err;
+ }
for (j = 1; j < pre_points_per_block; j++, var++) {
/* calculate odd multiples of the current base point */
- if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
+ if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) {
goto err;
+ }
}
if (i < numblocks - 1) {
@@ -792,19 +798,21 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) {
goto err;
}
- if (!EC_POINT_dbl(group, base, tmp_point, ctx))
+ if (!EC_POINT_dbl(group, base, tmp_point, ctx)) {
goto err;
+ }
for (k = 2; k < blocksize; k++) {
- if (!EC_POINT_dbl(group, base, base, ctx))
+ if (!EC_POINT_dbl(group, base, base, ctx)) {
goto err;
+ }
}
}
}
- if (!EC_POINTs_make_affine(group, num, points, ctx))
+ if (!EC_POINTs_make_affine(group, num, points, ctx)) {
goto err;
+ }
- pre_comp->group = group;
pre_comp->blocksize = blocksize;
pre_comp->numblocks = numblocks;
pre_comp->w = w;
@@ -818,23 +826,21 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) {
ret = 1;
err:
- if (ctx != NULL)
+ if (ctx != NULL) {
BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- if (pre_comp)
- ec_pre_comp_free(pre_comp);
+ }
+ BN_CTX_free(new_ctx);
+ ec_pre_comp_free(pre_comp);
if (points) {
EC_POINT **p;
- for (p = points; *p != NULL; p++)
+ for (p = points; *p != NULL; p++) {
EC_POINT_free(*p);
+ }
OPENSSL_free(points);
}
- if (tmp_point)
- EC_POINT_free(tmp_point);
- if (base)
- EC_POINT_free(base);
+ EC_POINT_free(tmp_point);
+ EC_POINT_free(base);
return ret;
}
generated by cgit v1.1 at 2024-06-19 22:01:17 +0000