| Message ID | 20240306222257.979304-1-stefanb@linux.ibm.com |
|---|---|
| Headers | show |
| Series | Add support for NIST P521 to ecdsa | expand |
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@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 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. > + 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
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@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 > > 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
This series adds support for the NIST P521 curve to the ecdsa module to enable signature verification with it. An issue with the current code in ecdsa is that it assumes that input arrays providing key coordinates for example, are arrays of digits (a 'digit' is a 'u64'). This works well for all currently supported curves, such as NIST P192/256/384, but does not work for NIST P521 where coordinates are 8 digits + 2 bytes long. So some of the changes deal with converting byte arrays to digits and adjusting tests on input byte array lengths to tolerate arrays not providing multiples of 8 bytes. Regards, Stefan v5: - Simplified ecc_digits_from_bytes as suggested by Lukas (1/12) - Using nbits == 521 to detect NIST P521 curve rather than strcmp() (5,6/12) - Nits in patch description and comments (11/12) v4: - Followed suggestions by Lukas Wummer (1,5,8/12) - Use nbits rather than ndigits where needed (8/12) - Renaming 'keylen' variablest to bufsize where necessary (9/12) - Adjust signature size calculation for NIST P521 (11/12) v3: - Dropped ecdh support - Use ecc_get_curve_nbits for getting number of bits in NIST P521 curve in ecc_point_mult (7/10) v2: - Reformulated some patch descriptions - Fixed issue detected by krobot - Some other small changes to the code Stefan Berger (12): crypto: ecdsa - Convert byte arrays with key coordinates to digits crypto: ecdsa - Adjust tests on length of key parameters crypto: ecdsa - Extend res.x mod n calculation for NIST P521 crypto: ecc - Add nbits field to ecc_curve structure crypto: ecc - Implement vli_mmod_fast_521 for NIST p521 crypto: ecc - Add special case for NIST P521 in ecc_point_mult crypto: ecc - Add NIST P521 curve parameters crypto: ecdsa - Replace ndigits with nbits where precision is needed crypto: ecdsa - Rename keylen to bufsize where necessary crypto: ecdsa - Register NIST P521 and extend test suite crypto: asymmetric_keys - Adjust signature size calculation for NIST P521 crypto: x509 - Add OID for NIST P521 and extend parser for it crypto/asymmetric_keys/public_key.c | 14 ++- crypto/asymmetric_keys/x509_cert_parser.c | 3 + crypto/ecc.c | 38 +++++- crypto/ecc_curve_defs.h | 49 ++++++++ crypto/ecdsa.c | 62 ++++++--- crypto/ecrdsa_defs.h | 5 + crypto/testmgr.c | 7 ++ crypto/testmgr.h | 146 ++++++++++++++++++++++ include/crypto/ecc_curve.h | 2 + include/crypto/ecdh.h | 1 + include/crypto/internal/ecc.h | 23 +++- include/linux/oid_registry.h | 1 + 12 files changed, 334 insertions(+), 17 deletions(-)