From: Stefan Berger <[email protected]>
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 <[email protected]>
---
crypto/ecc.c | 25 +++++++++++++++++++++++++
include/crypto/internal/ecc.h | 3 ++-
2 files changed, 27 insertions(+), 1 deletion(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index 415a2f4e7291..99d41887c005 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -902,6 +902,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
@@ -941,6 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
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;
diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h
index ab722a8986b7..4e2f5f938e91 100644
--- a/include/crypto/internal/ecc.h
+++ b/include/crypto/internal/ecc.h
@@ -33,7 +33,8 @@
#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_CURVE_NIST_P521_DIGITS 9
+#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
#define ECC_DIGITS_TO_BYTES_SHIFT 3
--
2.43.0
> -----Original Message-----
> From: Stefan Berger <[email protected]>
> Sent: Wednesday, March 13, 2024 12:06 AM
> To: [email protected]; [email protected];
> [email protected]; [email protected]
> Cc: [email protected]; [email protected];
> [email protected]; Bharat Bhushan <[email protected]>;
> [email protected]; Stefan Berger <[email protected]>
> Subject: [EXTERNAL] [PATCH v6 06/13] crypto: ecc - Implement
> vli_mmod_fast_521 for NIST p521
>
> Prioritize security for external emails: Confirm sender and content safety
> before clicking links or opening attachments
>
> ----------------------------------------------------------------------
> From: Stefan Berger <[email protected]>
>
> 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 <[email protected]>
> ---
> crypto/ecc.c | 25 +++++++++++++++++++++++++
> include/crypto/internal/ecc.h | 3 ++-
> 2 files changed, 27 insertions(+), 1 deletion(-)
>
> diff --git a/crypto/ecc.c b/crypto/ecc.c index 415a2f4e7291..99d41887c005
> 100644
> --- a/crypto/ecc.c
> +++ b/crypto/ecc.c
> @@ -902,6 +902,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;
Can we get away from this hardcoding, like 9, 55, 0x1ff etc.
Or at least add comment about these.
> +
> + 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 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
> 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;
> diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h index
> ab722a8986b7..4e2f5f938e91 100644
> --- a/include/crypto/internal/ecc.h
> +++ b/include/crypto/internal/ecc.h
> @@ -33,7 +33,8 @@
> #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_CURVE_NIST_P521_DIGITS 9
Maybe these can be defined as:
#define ECC_CURVE_NIST_P521_DIGITS (DIV_ROUND_UP(521, 64) /* NIST P521 */)
> +#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
/* NIST_P521 is max digits */
#define ECC_MAX_DIGITS ECC_CURVE_ _DIGITS
Thanks
-Bharat
>
> #define ECC_DIGITS_TO_BYTES_SHIFT 3
>
> --
> 2.43.0
On 3/18/24 01:47, Bharat Bhushan wrote:
>
>
>> -----Original Message-----
>> From: Stefan Berger <[email protected]>
>> Sent: Wednesday, March 13, 2024 12:06 AM
>> To: [email protected]; [email protected];
>> [email protected]; [email protected]
>> Cc: [email protected]; [email protected];
>> [email protected]; Bharat Bhushan <[email protected]>;
>> [email protected]; Stefan Berger <[email protected]>
>> Subject: [EXTERNAL] [PATCH v6 06/13] crypto: ecc - Implement
>> vli_mmod_fast_521 for NIST p521
>>
>> Prioritize security for external emails: Confirm sender and content safety
>> before clicking links or opening attachments
>>
>> ----------------------------------------------------------------------
>> From: Stefan Berger <[email protected]>
>>
>> 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 <[email protected]>
>> ---
>> crypto/ecc.c | 25 +++++++++++++++++++++++++
>> include/crypto/internal/ecc.h | 3 ++-
>> 2 files changed, 27 insertions(+), 1 deletion(-)
>>
>> diff --git a/crypto/ecc.c b/crypto/ecc.c index 415a2f4e7291..99d41887c005
>> 100644
>> --- a/crypto/ecc.c
>> +++ b/crypto/ecc.c
>> @@ -902,6 +902,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;
>
> Can we get away from this hardcoding, like 9, 55, 0x1ff etc.
> Or at least add comment about these.
>
>> +
>> + 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 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
>> 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;
>> diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h index
>> ab722a8986b7..4e2f5f938e91 100644
>> --- a/include/crypto/internal/ecc.h
>> +++ b/include/crypto/internal/ecc.h
>> @@ -33,7 +33,8 @@
>> #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_CURVE_NIST_P521_DIGITS 9
>
> Maybe these can be defined as:
> #define ECC_CURVE_NIST_P521_DIGITS (DIV_ROUND_UP(521, 64) /* NIST P521 */)
I think for NIST P521 9 can be pre-calculated. It will not change
anymore in the future.
>
>> +#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
>
> /* NIST_P521 is max digits */
> #define ECC_MAX_DIGITS ECC_CURVE_ _DIGITS
In this case I think the DIV_ROUND_UP() along with the comment shows
that it needs to be updated if ever a larger curve comes along.
>
> Thanks
> -Bharat
>
>>
>> #define ECC_DIGITS_TO_BYTES_SHIFT 3
>>
>> --
>> 2.43.0
>
On Tue Mar 12, 2024 at 8:36 PM EET, Stefan Berger wrote:
> From: Stefan Berger <[email protected]>
>
> 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 <[email protected]>
Should provide context on what it will be used (for completeness).
> ---
> crypto/ecc.c | 25 +++++++++++++++++++++++++
> include/crypto/internal/ecc.h | 3 ++-
> 2 files changed, 27 insertions(+), 1 deletion(-)
>
> diff --git a/crypto/ecc.c b/crypto/ecc.c
> index 415a2f4e7291..99d41887c005 100644
> --- a/crypto/ecc.c
> +++ b/crypto/ecc.c
> @@ -902,6 +902,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
> @@ -941,6 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
> 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;
> diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h
> index ab722a8986b7..4e2f5f938e91 100644
> --- a/include/crypto/internal/ecc.h
> +++ b/include/crypto/internal/ecc.h
> @@ -33,7 +33,8 @@
> #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_CURVE_NIST_P521_DIGITS 9
> +#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
>
> #define ECC_DIGITS_TO_BYTES_SHIFT 3
>
Otherwise, lgtm
BR, Jarkko
> -----Original Message-----
> From: Stefan Berger <[email protected]>
> Sent: Tuesday, March 19, 2024 12:09 AM
> To: Bharat Bhushan <[email protected]>; Stefan Berger
> <[email protected]>; [email protected]; linux-
> [email protected]; [email protected];
> [email protected]
> Cc: [email protected]; [email protected];
> [email protected]; [email protected]
> Subject: [EXTERNAL] Re: [PATCH v6 06/13] crypto: ecc - Implement
> vli_mmod_fast_521 for NIST p521
>
> ----------------------------------------------------------------------
>
>
> On 3/18/24 01:47, Bharat Bhushan wrote:
> >
> >
> >> -----Original Message-----
> >> From: Stefan Berger <[email protected]>
> >> Sent: Wednesday, March 13, 2024 12:06 AM
> >> To: [email protected]; [email protected];
> >> [email protected]; [email protected]
> >> Cc: [email protected]; [email protected];
> >> [email protected]; Bharat Bhushan <[email protected]>;
> >> [email protected]; Stefan Berger <[email protected]>
> >> Subject: [EXTERNAL] [PATCH v6 06/13] crypto: ecc - Implement
> >> vli_mmod_fast_521 for NIST p521
> >>
> >> ---------------------------------------------------------------------
> >> -
> >> From: Stefan Berger <[email protected]>
> >>
> >> 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 <[email protected]>
> >> ---
> >> crypto/ecc.c | 25 +++++++++++++++++++++++++
> >> include/crypto/internal/ecc.h | 3 ++-
> >> 2 files changed, 27 insertions(+), 1 deletion(-)
> >>
> >> diff --git a/crypto/ecc.c b/crypto/ecc.c index
> >> 415a2f4e7291..99d41887c005
> >> 100644
> >> --- a/crypto/ecc.c
> >> +++ b/crypto/ecc.c
> >> @@ -902,6 +902,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;
> >
> > Can we get away from this hardcoding, like 9, 55, 0x1ff etc.
> > Or at least add comment about these.
> >
> >> +
> >> + 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 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
> >> 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;
> >> diff --git a/include/crypto/internal/ecc.h
> >> b/include/crypto/internal/ecc.h index
> >> ab722a8986b7..4e2f5f938e91 100644
> >> --- a/include/crypto/internal/ecc.h
> >> +++ b/include/crypto/internal/ecc.h
> >> @@ -33,7 +33,8 @@
> >> #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_CURVE_NIST_P521_DIGITS 9
> >
> > Maybe these can be defined as:
> > #define ECC_CURVE_NIST_P521_DIGITS (DIV_ROUND_UP(521, 64) /* NIST
> > P521 */)
>
> I think for NIST P521 9 can be pre-calculated. It will not change anymore in the
> future.
pre-calculation for others is perfect division by 64 but not for P521. So that creates a little confusion why it is 9 and not 8.
So in my view we can either use same logic used for ECC_MAX_DIGITS or a comment that it is rounded up. Anyways not a major concern.
Thanks
-Bharat
>
> >
> >> +#define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521
> */
> >
> > /* NIST_P521 is max digits */
> > #define ECC_MAX_DIGITS ECC_CURVE_ _DIGITS
>
> In this case I think the DIV_ROUND_UP() along with the comment shows that
> it needs to be updated if ever a larger curve comes along.
>
> >
> > Thanks
> > -Bharat
> >
> >>
> >> #define ECC_DIGITS_TO_BYTES_SHIFT 3
> >>
> >> --
> >> 2.43.0
> >