Re: [PATCH v5 05/12] crypto: ecc - Implement vli_mmod_fast_521 for NIST p521

From: Stefan Berger
Date: Thu Mar 07 2024 - 15:38:11 EST




On 3/7/24 14:11, Jarkko Sakkinen wrote:
On Thu Mar 7, 2024 at 12:22 AM EET, Stefan Berger wrote:
Implement vli_mmod_fast_521 following the description for how to calculate
the modulus for NIST P521 in the NIST publication "Recommendations for
Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters"
section G.1.4.

NIST p521 requires 9 64bit digits, so increase the ECC_MAX_DIGITS so that
arrays fit the larger numbers.

Signed-off-by: Stefan Berger <stefanb@xxxxxxxxxxxxx>
Tested-by: Lukas Wunner <lukas@xxxxxxxxx>
---
crypto/ecc.c | 31 +++++++++++++++++++++++++++++++
include/crypto/internal/ecc.h | 2 +-
2 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index f53fb4d6af99..373660e7b19d 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -902,6 +902,31 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product,
#undef AND64H
#undef AND64L
+/* Computes result = product % curve_prime

Missing empty comment line:

/*
*

+ * from "Recommendations for Discrete Logarithm-Based Cryptography:
+ * Elliptic Curve Domain Parameters" G.1.4
+ */
+static void vli_mmod_fast_521(u64 *result, const u64 *product,
+ const u64 *curve_prime, u64 *tmp)
+{
+ const unsigned int ndigits = 9;
+ size_t i;
+
+ for (i = 0; i < ndigits; i++)
+ tmp[i] = product[i];
+ tmp[8] &= 0x1ff;
+
+ vli_set(result, tmp, ndigits);
+
+
+ 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
@@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
case 6:
vli_mmod_fast_384(result, product, curve_prime, tmp);
break;
+ case 9:
+ if (curve->nbits == 521) {

Missing inline comment about the branching decision, and has a magic
number.


Ok, will add comment to this and 6/12.

+ vli_mmod_fast_521(result, product, curve_prime, tmp);
+ break;
+ }
+ fallthrough;
default:
pr_err_ratelimited("ecc: unsupported digits size!\n");
return false;
diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h
index 4a556b41873e..de17bcdeb53a 100644
--- a/include/crypto/internal/ecc.h
+++ b/include/crypto/internal/ecc.h
@@ -33,7 +33,7 @@
#define ECC_CURVE_NIST_P192_DIGITS 3
#define ECC_CURVE_NIST_P256_DIGITS 4
#define ECC_CURVE_NIST_P384_DIGITS 6
-#define ECC_MAX_DIGITS (512 / 64) /* due to ecrdsa */
+#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
#define ECC_DIGITS_TO_BYTES_SHIFT 3

BR, Jarkko