| Message ID | 20240301022007.344948-5-stefanb@linux.ibm.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Add support for NIST P521 to ecdsa | expand |
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
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 --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
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(-)