diff mbox series

[v4,04/12] crypto: ecc - Implement vli_mmod_fast_521 for NIST p521

Message ID 20240301022007.344948-5-stefanb@linux.ibm.com
State New
Headers
Series Add support for NIST P521 to ecdsa |

Commit Message

Stefan Berger March 1, 2024, 2:19 a.m. UTC 
  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@linux.ibm.com>
---
 crypto/ecc.c                  | 31 +++++++++++++++++++++++++++++++
 include/crypto/internal/ecc.h |  2 +-
 2 files changed, 32 insertions(+), 1 deletion(-)

Comments

Lukas Wunner March 3, 2024, 11:05 a.m. UTC | #1 
On Thu, Feb 29, 2024 at 09:19:59PM -0500, Stefan Berger wrote:
> +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;

Hm, the other vli_mmod_fast_*() functions manually unroll those loops.
Wondering if that would make sense here as well?  It's also possible
to tell gcc to unroll a loop with a per-function...

    __attribute__((optimize("unroll-loops")))

..but I'm not sure about clang portability.


> @@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
> +	case 9:
> +		if (!strcmp(curve->name, "nist_521")) {
> +			vli_mmod_fast_521(result, product, curve_prime, tmp);
> +			break;
> +		}
> +		fallthrough;

If you reorder patch 4 and 5, you could check for curve->nbits == 521 here,
which might be cheaper than the string comparison.


> -#define ECC_MAX_DIGITS              (512 / 64) /* due to ecrdsa */
> +#define ECC_MAX_DIGITS              (576 / 64) /* due to NIST P521 */

Maybe DIV_ROUND_UP(521, 64) for clarity?

Thanks,

Lukas
Stefan Berger March 3, 2024, 4:29 p.m. UTC | #2 
On 3/3/24 06:05, Lukas Wunner wrote:
> On Thu, Feb 29, 2024 at 09:19:59PM -0500, Stefan Berger wrote:
>> +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;
> 
> Hm, the other vli_mmod_fast_*() functions manually unroll those loops.
> Wondering if that would make sense here as well?  It's also possible

Why would we do this? One could also argue why not use vli_set() instead 
of the loop...

> to tell gcc to unroll a loop with a per-function...
> 
>      __attribute__((optimize("unroll-loops")))
> 
> ...but I'm not sure about clang portability. >
> 
>> @@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
>> +	case 9:
>> +		if (!strcmp(curve->name, "nist_521")) {
>> +			vli_mmod_fast_521(result, product, curve_prime, tmp);
>> +			break;
>> +		}
>> +		fallthrough;
> 
> If you reorder patch 4 and 5, you could check for curve->nbits == 521 here,
> which might be cheaper than the string comparison.

Sure. I thought it's a nist spec for this particular curve, so compare 
against 'nist' in the string. Though comparing against nbits also works, 
of course.

> 
> 
>> -#define ECC_MAX_DIGITS              (512 / 64) /* due to ecrdsa */
>> +#define ECC_MAX_DIGITS              (576 / 64) /* due to NIST P521 */
> 
> Maybe DIV_ROUND_UP(521, 64) for clarity?

Ok, will adjust.

Regards,
    Stefan

> 
> Thanks,
> 
> Lukas
>
diff mbox series

Patch

diff --git a/crypto/ecc.c b/crypto/ecc.c
index f53fb4d6af99..ea7b28b5e00e 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
+ * 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 (!strcmp(curve->name, "nist_521")) {
+			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 48a04605da7f..b63238b12204 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              (576 / 64) /* due to NIST P521 */
 
 #define ECC_DIGITS_TO_BYTES_SHIFT 3