diff mbox series

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

Message ID 20240306222257.979304-6-stefanb@linux.ibm.com
State New
Headers show
Series Add support for NIST P521 to ecdsa | expand

Commit Message

Stefan Berger March 6, 2024, 10:22 p.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>
Tested-by: Lukas Wunner <lukas@wunner.de>
---
 crypto/ecc.c                  | 31 +++++++++++++++++++++++++++++++
 include/crypto/internal/ecc.h |  2 +-
 2 files changed, 32 insertions(+), 1 deletion(-)

Comments

Bharat Bhushan March 11, 2024, 5:07 a.m. UTC | #1 
Minor nits

> -----Original Message-----
> From: Stefan Berger <stefanb@linux.ibm.com>
> Sent: Thursday, March 7, 2024 3:53 AM
> To: keyrings@vger.kernel.org; linux-crypto@vger.kernel.org;
> herbert@gondor.apana.org.au; davem@davemloft.net
> Cc: linux-kernel@vger.kernel.org; saulo.alessandre@tse.jus.br;
> lukas@wunner.de; Stefan Berger <stefanb@linux.ibm.com>
> Subject: [EXTERNAL] [PATCH v5 05/12] crypto: ecc - Implement
> vli_mmod_fast_521 for NIST p521
>  
> ----------------------------------------------------------------------
> 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>
> Tested-by: Lukas Wunner <lukas@wunner.de>
> ---
>  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
> + * 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:

Can we use ECC_CURVE_NIST_P384_DIGITS, ECC_CURVE_NIST_P256_DIGITS  in this function?
 
And define ECC_CURVE_NIST_P521_DIGITS, which is same as ECC_MAX_DIGITS defined below in this patch?

> +		if (curve->nbits == 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
> 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
> 
> --
> 2.43.0
>
Stefan Berger March 11, 2024, 2:03 p.m. UTC | #2 
On 3/11/24 01:07, Bharat Bhushan wrote:
> Minor nits
> 
>> -----Original Message-----
>> From: Stefan Berger <stefanb@linux.ibm.com>
>> Sent: Thursday, March 7, 2024 3:53 AM
>> To: keyrings@vger.kernel.org; linux-crypto@vger.kernel.org;
>> herbert@gondor.apana.org.au; davem@davemloft.net
>> Cc: linux-kernel@vger.kernel.org; saulo.alessandre@tse.jus.br;
>> lukas@wunner.de; Stefan Berger <stefanb@linux.ibm.com>
>> Subject: [EXTERNAL] [PATCH v5 05/12] crypto: ecc - Implement
>> vli_mmod_fast_521 for NIST p521
>>   
>> ----------------------------------------------------------------------
>> 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>
>> Tested-by: Lukas Wunner <lukas@wunner.de>
>> ---
>>   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
>> + * 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);

I have also modified this here now to initialize 'result' from lowest 
521 bis of product without the detour through tmp.

>> +
>> +
>> +	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:
> 
> Can we use ECC_CURVE_NIST_P384_DIGITS, ECC_CURVE_NIST_P256_DIGITS  in this function?
>   
> And define ECC_CURVE_NIST_P521_DIGITS, which is same as ECC_MAX_DIGITS defined below in this patch?
> 
>> +		if (curve->nbits == 521) {

If I replace the numbers with these hash-defines's in here (in an 
additional patch on existing code) then I can just about remove the 
check on nbits here as well... ?


>> +			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
>>
>> --
>> 2.43.0
>>
>
Bharat Bhushan March 11, 2024, 4:11 p.m. UTC | #3 
> -----Original Message-----
> From: Stefan Berger <stefanb@linux.ibm.com>
> Sent: Monday, March 11, 2024 7:33 PM
> To: Bharat Bhushan <bbhushan2@marvell.com>; keyrings@vger.kernel.org; linux-
> crypto@vger.kernel.org; herbert@gondor.apana.org.au; davem@davemloft.net
> Cc: linux-kernel@vger.kernel.org; saulo.alessandre@tse.jus.br; lukas@wunner.de
> Subject: [EXTERNAL] Re: [PATCH v5 05/12] crypto: ecc - Implement
> vli_mmod_fast_521 for NIST p521
> > 
> ----------------------------------------------------------------------
> 
> 
> On 3/11/24 01:07, Bharat Bhushan wrote:
> > Minor nits
> >
> >> -----Original Message-----
> >> From: Stefan Berger <stefanb@linux.ibm.com>
> >> Sent: Thursday, March 7, 2024 3:53 AM
> >> To: keyrings@vger.kernel.org; linux-crypto@vger.kernel.org;
> >> herbert@gondor.apana.org.au; davem@davemloft.net
> >> Cc: linux-kernel@vger.kernel.org; saulo.alessandre@tse.jus.br;
> >> lukas@wunner.de; Stefan Berger <stefanb@linux.ibm.com>
> >> Subject: [EXTERNAL] [PATCH v5 05/12] crypto: ecc - Implement
> >> vli_mmod_fast_521 for NIST p521
> >>
> >> ---------------------------------------------------------------------
> >> - 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>
> >> Tested-by: Lukas Wunner <lukas@wunner.de>
> >> ---
> >>   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
> >> + * 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);
> 
> I have also modified this here now to initialize 'result' from lowest
> 521 bis of product without the detour through tmp.
> 
> >> +
> >> +
> >> +	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:
> >
> > Can we use ECC_CURVE_NIST_P384_DIGITS, ECC_CURVE_NIST_P256_DIGITS
> in this function?
> >
> > And define ECC_CURVE_NIST_P521_DIGITS, which is same as
> ECC_MAX_DIGITS defined below in this patch?
> >
> >> +		if (curve->nbits == 521) {
> 
> If I replace the numbers with these hash-defines's in here (in an additional patch
> on existing code) then I can just about remove the check on nbits here as well... ?

Yes, can use same define here.

Thanks
-Bharat

> 
> 
> >> +			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
> >>
> >> --
> >> 2.43.0
> >>
> >
diff mbox series

Patch

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
+ * 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) {
+			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