summaryrefslogtreecommitdiff
path: root/crypto/ecc.c
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/ecc.c')
-rw-r--r--crypto/ecc.c100
1 files changed, 63 insertions, 37 deletions
diff --git a/crypto/ecc.c b/crypto/ecc.c
index f53fb4d6af99..c1d2e884be1e 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -60,6 +60,8 @@ const struct ecc_curve *ecc_get_curve(unsigned int curve_id)
return &nist_p256;
case ECC_CURVE_NIST_P384:
return &nist_p384;
+ case ECC_CURVE_NIST_P521:
+ return &nist_p521;
default:
return NULL;
}
@@ -689,7 +691,7 @@ static void vli_mmod_barrett(u64 *result, u64 *product, const u64 *mod,
static void vli_mmod_fast_192(u64 *result, const u64 *product,
const u64 *curve_prime, u64 *tmp)
{
- const unsigned int ndigits = 3;
+ const unsigned int ndigits = ECC_CURVE_NIST_P192_DIGITS;
int carry;
vli_set(result, product, ndigits);
@@ -717,7 +719,7 @@ static void vli_mmod_fast_256(u64 *result, const u64 *product,
const u64 *curve_prime, u64 *tmp)
{
int carry;
- const unsigned int ndigits = 4;
+ const unsigned int ndigits = ECC_CURVE_NIST_P256_DIGITS;
/* t */
vli_set(result, product, ndigits);
@@ -800,7 +802,7 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product,
const u64 *curve_prime, u64 *tmp)
{
int carry;
- const unsigned int ndigits = 6;
+ const unsigned int ndigits = ECC_CURVE_NIST_P384_DIGITS;
/* t */
vli_set(result, product, ndigits);
@@ -902,6 +904,28 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product,
#undef AND64H
#undef AND64L
+/*
+ * Computes result = product % curve_prime
+ * from "Recommendations for Discrete Logarithm-Based Cryptography:
+ * Elliptic Curve Domain Parameters" section G.1.4
+ */
+static void vli_mmod_fast_521(u64 *result, const u64 *product,
+ const u64 *curve_prime, u64 *tmp)
+{
+ const unsigned int ndigits = ECC_CURVE_NIST_P521_DIGITS;
+ size_t i;
+
+ /* Initialize result with lowest 521 bits from product */
+ vli_set(result, product, ndigits);
+ result[8] &= 0x1ff;
+
+ for (i = 0; i < ndigits; i++)
+ tmp[i] = (product[8 + i] >> 9) | (product[9 + i] << 55);
+ tmp[8] &= 0x1ff;
+
+ vli_mod_add(result, result, tmp, curve_prime, ndigits);
+}
+
/* Computes result = product % curve_prime for different curve_primes.
*
* Note that curve_primes are distinguished just by heuristic check and
@@ -932,15 +956,18 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
}
switch (ndigits) {
- case 3:
+ case ECC_CURVE_NIST_P192_DIGITS:
vli_mmod_fast_192(result, product, curve_prime, tmp);
break;
- case 4:
+ case ECC_CURVE_NIST_P256_DIGITS:
vli_mmod_fast_256(result, product, curve_prime, tmp);
break;
- case 6:
+ case ECC_CURVE_NIST_P384_DIGITS:
vli_mmod_fast_384(result, product, curve_prime, tmp);
break;
+ case ECC_CURVE_NIST_P521_DIGITS:
+ vli_mmod_fast_521(result, product, curve_prime, tmp);
+ break;
default:
pr_err_ratelimited("ecc: unsupported digits size!\n");
return false;
@@ -1295,7 +1322,10 @@ static void ecc_point_mult(struct ecc_point *result,
carry = vli_add(sk[0], scalar, curve->n, ndigits);
vli_add(sk[1], sk[0], curve->n, ndigits);
scalar = sk[!carry];
- num_bits = sizeof(u64) * ndigits * 8 + 1;
+ if (curve->nbits == 521) /* NIST P521 */
+ num_bits = curve->nbits + 2;
+ else
+ num_bits = sizeof(u64) * ndigits * 8 + 1;
vli_set(rx[1], point->x, ndigits);
vli_set(ry[1], point->y, ndigits);
@@ -1416,6 +1446,12 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
}
EXPORT_SYMBOL(ecc_point_mult_shamir);
+/*
+ * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5.
+ * Whereas A.4.2 results in an integer in the interval [1, n-1], this function
+ * ensures that the integer is in the range of [2, n-3]. We are slightly
+ * stricter because of the currently used scalar multiplication algorithm.
+ */
static int __ecc_is_key_valid(const struct ecc_curve *curve,
const u64 *private_key, unsigned int ndigits)
{
@@ -1455,31 +1491,29 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
EXPORT_SYMBOL(ecc_is_key_valid);
/*
- * ECC private keys are generated using the method of extra random bits,
- * equivalent to that described in FIPS 186-4, Appendix B.4.1.
- *
- * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
- * than requested
- * 0 <= c mod(n-1) <= n-2 and implies that
- * 1 <= d <= n-1
+ * ECC private keys are generated using the method of rejection sampling,
+ * equivalent to that described in FIPS 186-5, Appendix A.2.2.
*
* This method generates a private key uniformly distributed in the range
- * [1, n-1].
+ * [2, n-3].
*/
-int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
+int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits,
+ u64 *private_key)
{
const struct ecc_curve *curve = ecc_get_curve(curve_id);
- u64 priv[ECC_MAX_DIGITS];
unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
unsigned int nbits = vli_num_bits(curve->n, ndigits);
int err;
- /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
- if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
+ /*
+ * Step 1 & 2: check that N is included in Table 1 of FIPS 186-5,
+ * section 6.1.1.
+ */
+ if (nbits < 224)
return -EINVAL;
/*
- * FIPS 186-4 recommends that the private key should be obtained from a
+ * FIPS 186-5 recommends that the private key should be obtained from a
* RBG with a security strength equal to or greater than the security
* strength associated with N.
*
@@ -1492,17 +1526,17 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
if (crypto_get_default_rng())
return -EFAULT;
- err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
+ /* Step 3: obtain N returned_bits from the DRBG. */
+ err = crypto_rng_get_bytes(crypto_default_rng,
+ (u8 *)private_key, nbytes);
crypto_put_default_rng();
if (err)
return err;
- /* Make sure the private key is in the valid range. */
- if (__ecc_is_key_valid(curve, priv, ndigits))
+ /* Step 4: make sure the private key is in the valid range. */
+ if (__ecc_is_key_valid(curve, private_key, ndigits))
return -EINVAL;
- ecc_swap_digits(priv, privkey, ndigits);
-
return 0;
}
EXPORT_SYMBOL(ecc_gen_privkey);
@@ -1512,23 +1546,20 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
{
int ret = 0;
struct ecc_point *pk;
- u64 priv[ECC_MAX_DIGITS];
const struct ecc_curve *curve = ecc_get_curve(curve_id);
- if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) {
+ if (!private_key) {
ret = -EINVAL;
goto out;
}
- ecc_swap_digits(private_key, priv, ndigits);
-
pk = ecc_alloc_point(ndigits);
if (!pk) {
ret = -ENOMEM;
goto out;
}
- ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits);
+ ecc_point_mult(pk, &curve->g, private_key, NULL, curve, ndigits);
/* SP800-56A rev 3 5.6.2.1.3 key check */
if (ecc_is_pubkey_valid_full(curve, pk)) {
@@ -1612,13 +1643,11 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
{
int ret = 0;
struct ecc_point *product, *pk;
- u64 priv[ECC_MAX_DIGITS];
u64 rand_z[ECC_MAX_DIGITS];
unsigned int nbytes;
const struct ecc_curve *curve = ecc_get_curve(curve_id);
- if (!private_key || !public_key || !curve ||
- ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) {
+ if (!private_key || !public_key || ndigits > ARRAY_SIZE(rand_z)) {
ret = -EINVAL;
goto out;
}
@@ -1639,15 +1668,13 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
if (ret)
goto err_alloc_product;
- ecc_swap_digits(private_key, priv, ndigits);
-
product = ecc_alloc_point(ndigits);
if (!product) {
ret = -ENOMEM;
goto err_alloc_product;
}
- ecc_point_mult(product, pk, priv, rand_z, curve, ndigits);
+ ecc_point_mult(product, pk, private_key, rand_z, curve, ndigits);
if (ecc_point_is_zero(product)) {
ret = -EFAULT;
@@ -1657,7 +1684,6 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
ecc_swap_digits(product->x, secret, ndigits);
err_validity:
- memzero_explicit(priv, sizeof(priv));
memzero_explicit(rand_z, sizeof(rand_z));
ecc_free_point(product);
err_alloc_product:
generated by cgit v1.2.3 (git 2.39.0) at 2025-02-17 03:37:17 +0300