This series adds support for the NIST P521 curve to the ecdsa module.
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
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 (10):
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 - Implement vli_mmod_fast_521 for NIST p521
crypto: ecc - Add nbits field to ecc_curve structure
crypte: ecc - Implement ecc_curve_get_nbits to get number of bits
crypto: ecc - Use ecc_get_curve_nbits to get number of bits for NIST
P521
crypto: ecc - Add NIST P521 curve parameters
crypto: ecdsa - Register NIST P521 and extend test suite
x509: Add OID for NIST P521 and extend parser for it
crypto/asymmetric_keys/x509_cert_parser.c | 3 +
crypto/ecc.c | 38 +++++-
crypto/ecc_curve_defs.h | 45 +++++++
crypto/ecdsa.c | 48 +++++--
crypto/testmgr.c | 7 ++
crypto/testmgr.h | 146 ++++++++++++++++++++++
include/crypto/ecc_curve.h | 3 +
include/crypto/ecdh.h | 1 +
include/crypto/internal/ecc.h | 32 ++++-
include/linux/oid_registry.h | 1 +
10 files changed, 315 insertions(+), 9 deletions(-)
--
2.43.0
For NIST P192/256/384 the public key's x and y parameters could be copied
directly from a given array since both parameters filled 'ndigits' of
digits (a 'digit' is a u64). For support of NIST P521 the key parameters
first have to be copied into a temporary byte array with leading zeros
and can then be copied into the final digit array using ecc_swap_digits.
Implement ecc_digits_from_bytes to convert a byte array into an array of
digits and use this function in ecdsa_set_pub_key where an input byte array
needs to be converted into digits.
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/ecdsa.c | 14 +++++++++-----
include/crypto/internal/ecc.h | 19 +++++++++++++++++++
2 files changed, 28 insertions(+), 5 deletions(-)
diff --git a/crypto/ecdsa.c b/crypto/ecdsa.c
index fbd76498aba8..ba8fb76fd165 100644
--- a/crypto/ecdsa.c
+++ b/crypto/ecdsa.c
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
{
struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+ unsigned int digitlen, ndigits;
const unsigned char *d = key;
- const u64 *digits = (const u64 *)&d[1];
- unsigned int ndigits;
int ret;
ret = ecdsa_ecc_ctx_reset(ctx);
@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
return -EINVAL;
keylen--;
- ndigits = (keylen >> 1) / sizeof(u64);
+ digitlen = keylen >> 1;
+
+ ndigits = digitlen / sizeof(u64);
if (ndigits != ctx->curve->g.ndigits)
return -EINVAL;
- ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
- ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
+ d++;
+
+ ecc_digits_from_bytes(d, digitlen, ctx->pub_key.x, ndigits);
+ ecc_digits_from_bytes(&d[digitlen], digitlen, ctx->pub_key.y, ndigits);
+
ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
ctx->pub_key_set = ret == 0;
diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h
index 4f6c1a68882f..bee3329af7de 100644
--- a/include/crypto/internal/ecc.h
+++ b/include/crypto/internal/ecc.h
@@ -56,6 +56,25 @@ static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigit
out[i] = get_unaligned_be64(&src[ndigits - 1 - i]);
}
+/**
+ * ecc_digits_from_bytes() - Create ndigits-sized digits array from byte array
+ * @in: Input byte array
+ * @nbytes Size of input byte array
+ * @out Output digits array
+ * @ndigits: Number of digits to create from byte array
+ */
+static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
+ u64 *out, unsigned int ndigits)
+{
+ unsigned int sz = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+ u8 tmp[ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT];
+ unsigned int o = sz - nbytes;
+
+ memset(tmp, 0, o);
+ memcpy(&tmp[o], in, nbytes);
+ ecc_swap_digits(tmp, out, ndigits);
+}
+
/**
* ecc_is_key_valid() - Validate a given ECDH private key
*
--
2.43.0
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 | 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..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 bee3329af7de..b8ca5023b3b5 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
--
2.43.0
res.x has been calculated by ecc_point_mult_shamir, which uses
'mod curve_prime'. The curve_prime 'p' is typically larger than the
curve_order 'n' and therefore it is possible that p > res.x >= n.
If res.x >= n then res.x mod n can be calculated by iteratively sub-
tracting n from res.x until n > res.x. For NIST P192/256/384 this can be
done in a single subtraction. This can also be done in a single
subtraction for NIST P521.
The mathematical reason why a single subtraction is sufficient is
due to the values of 'p' and 'n' of the NIST curves where the following
holds true:
note: max(res.x) = p - 1
max(res.x) - n < n
p - 1 - n < n
p - 1 < 2n => true for the NIST curves
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/ecdsa.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/crypto/ecdsa.c b/crypto/ecdsa.c
index 64e1e69d53ba..1814f009f971 100644
--- a/crypto/ecdsa.c
+++ b/crypto/ecdsa.c
@@ -122,7 +122,7 @@ static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, con
/* res.x = res.x mod n (if res.x > order) */
if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
- /* faster alternative for NIST p384, p256 & p192 */
+ /* faster alternative for NIST p521, p384, p256 & p192 */
vli_sub(res.x, res.x, curve->n, ndigits);
if (!vli_cmp(res.x, r, ndigits))
--
2.43.0
If curve->nbits is set then return this number, otherwise use
the curve->ndigits to calculate the number of bits.
Signed-off-by: Stefan Berger <[email protected]>
---
include/crypto/internal/ecc.h | 11 +++++++++++
1 file changed, 11 insertions(+)
diff --git a/include/crypto/internal/ecc.h b/include/crypto/internal/ecc.h
index b8ca5023b3b5..2d321b47d0f7 100644
--- a/include/crypto/internal/ecc.h
+++ b/include/crypto/internal/ecc.h
@@ -75,6 +75,17 @@ static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
ecc_swap_digits(tmp, out, ndigits);
}
+/**
+ * ecc_curve_get_nbits() - Get the number of bits of the curve
+ * @curve: The curve
+ */
+static inline unsigned int ecc_curve_get_nbits(const struct ecc_curve *curve)
+{
+ if (curve->nbits)
+ return curve->nbits;
+ return curve->g.ndigits << ECC_DIGITS_TO_BYTES_SHIFT * 8;
+}
+
/**
* ecc_is_key_valid() - Validate a given ECDH private key
*
--
2.43.0
Add the number of bits a curve has to the ecc_curve definition. This field
only needs to be set for curves that don't fill up all bytes in their
digits, such as NIST P521 which has only 9 bits in the most significant
digit. This field will be used to determine the number of bytes a curve
requires for its key coordinates for example.
Signed-off-by: Stefan Berger <[email protected]>
---
include/crypto/ecc_curve.h | 3 +++
1 file changed, 3 insertions(+)
diff --git a/include/crypto/ecc_curve.h b/include/crypto/ecc_curve.h
index 70964781eb68..337a44956926 100644
--- a/include/crypto/ecc_curve.h
+++ b/include/crypto/ecc_curve.h
@@ -23,6 +23,8 @@ struct ecc_point {
* struct ecc_curve - definition of elliptic curve
*
* @name: Short name of the curve.
+ * @nbits: Curves that do not use all bits in their ndigits must specify
+ * their number of bits here, otherwise can leave at 0.
* @g: Generator point of the curve.
* @p: Prime number, if Barrett's reduction is used for this curve
* pre-calculated value 'mu' is appended to the @p after ndigits.
@@ -34,6 +36,7 @@ struct ecc_point {
*/
struct ecc_curve {
char *name;
+ unsigned int nbits;
struct ecc_point g;
u64 *p;
u64 *n;
--
2.43.0
In ecc_point_mult query for the number of bits when using NIST P521 and
add '2'. The change is required specifically for NIST P521 to pass
mathematical tests on the public key.
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/ecc.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index ea7b28b5e00e..89ad45cf2404 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1326,7 +1326,10 @@ static void ecc_point_mult(struct ecc_point *result,
carry = vli_add(sk[0], scalar, curve->n, ndigits);
vli_add(sk[1], sk[0], curve->n, ndigits);
scalar = sk[!carry];
- num_bits = sizeof(u64) * ndigits * 8 + 1;
+ if (ndigits == 9 && !strcmp(curve->name, "nist_521"))
+ num_bits = ecc_curve_get_nbits(curve) + 2;
+ else
+ num_bits = sizeof(u64) * ndigits * 8 + 1;
vli_set(rx[1], point->x, ndigits);
vli_set(ry[1], point->y, ndigits);
--
2.43.0
Register NIST P521 as an akcipher and extend the testmgr with
NIST P521-specific test vectors.
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/ecdsa.c | 30 ++++++++++
crypto/testmgr.c | 7 +++
crypto/testmgr.h | 146 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 183 insertions(+)
diff --git a/crypto/ecdsa.c b/crypto/ecdsa.c
index 1814f009f971..faa55c692d2a 100644
--- a/crypto/ecdsa.c
+++ b/crypto/ecdsa.c
@@ -269,6 +269,28 @@ static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
}
+static int ecdsa_nist_p521_init_tfm(struct crypto_akcipher *tfm)
+{
+ struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+
+ return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P521);
+}
+
+static struct akcipher_alg ecdsa_nist_p521 = {
+ .verify = ecdsa_verify,
+ .set_pub_key = ecdsa_set_pub_key,
+ .max_size = ecdsa_max_size,
+ .init = ecdsa_nist_p521_init_tfm,
+ .exit = ecdsa_exit_tfm,
+ .base = {
+ .cra_name = "ecdsa-nist-p521",
+ .cra_driver_name = "ecdsa-nist-p521-generic",
+ .cra_priority = 100,
+ .cra_module = THIS_MODULE,
+ .cra_ctxsize = sizeof(struct ecc_ctx),
+ },
+};
+
static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
{
struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
@@ -352,8 +374,15 @@ static int __init ecdsa_init(void)
if (ret)
goto nist_p384_error;
+ ret = crypto_register_akcipher(&ecdsa_nist_p521);
+ if (ret)
+ goto nist_p521_error;
+
return 0;
+nist_p521_error:
+ crypto_unregister_akcipher(&ecdsa_nist_p384);
+
nist_p384_error:
crypto_unregister_akcipher(&ecdsa_nist_p256);
@@ -369,6 +398,7 @@ static void __exit ecdsa_exit(void)
crypto_unregister_akcipher(&ecdsa_nist_p192);
crypto_unregister_akcipher(&ecdsa_nist_p256);
crypto_unregister_akcipher(&ecdsa_nist_p384);
+ crypto_unregister_akcipher(&ecdsa_nist_p521);
}
subsys_initcall(ecdsa_init);
diff --git a/crypto/testmgr.c b/crypto/testmgr.c
index c26aeda85787..a017b4ad119b 100644
--- a/crypto/testmgr.c
+++ b/crypto/testmgr.c
@@ -5097,6 +5097,13 @@ static const struct alg_test_desc alg_test_descs[] = {
.suite = {
.akcipher = __VECS(ecdsa_nist_p384_tv_template)
}
+ }, {
+ .alg = "ecdsa-nist-p521",
+ .test = alg_test_akcipher,
+ .fips_allowed = 1,
+ .suite = {
+ .akcipher = __VECS(ecdsa_nist_p521_tv_template)
+ }
}, {
.alg = "ecrdsa",
.test = alg_test_akcipher,
diff --git a/crypto/testmgr.h b/crypto/testmgr.h
index 986f331a5fc2..9bde04be8df9 100644
--- a/crypto/testmgr.h
+++ b/crypto/testmgr.h
@@ -991,6 +991,152 @@ static const struct akcipher_testvec ecdsa_nist_p384_tv_template[] = {
},
};
+static const struct akcipher_testvec ecdsa_nist_p521_tv_template[] = {
+ {
+ .key = /* secp521r1(sha224) */
+ "\x04\x01\x4f\x43\x18\xb6\xa9\xc9\x5d\x68\xd3\xa9\x42\xf8\x98\xc0"
+ "\xd2\xd1\xa9\x50\x3b\xe8\xc4\x40\xe6\x11\x78\x88\x4b\xbd\x76\xa7"
+ "\x9a\xe0\xdd\x31\xa4\x67\x78\x45\x33\x9e\x8c\xd1\xc7\x44\xac\x61"
+ "\x68\xc8\x04\xe7\x5c\x79\xb1\xf1\x41\x0c\x71\xc0\x53\xa8\xbc\xfb"
+ "\xf5\xca\xd4\x01\x40\xfd\xa3\x45\xda\x08\xe0\xb4\xcb\x28\x3b\x0a"
+ "\x02\x35\x5f\x02\x9f\x3f\xcd\xef\x08\x22\x40\x97\x74\x65\xb7\x76"
+ "\x85\xc7\xc0\x5c\xfb\x81\xe1\xa5\xde\x0c\x4e\x8b\x12\x31\xb6\x47"
+ "\xed\x37\x0f\x99\x3f\x26\xba\xa3\x8e\xff\x79\x34\x7c\x3a\xfe\x1f"
+ "\x3b\x83\x82\x2f\x14",
+ .key_len = 133,
+ .params =
+ "\x30\x10\x06\x07\x2a\x86\x48\xce\x3d\x02\x01\x06\x05\x2b\x81\x04"
+ "\x00\x23",
+ .param_len = 18,
+ .m =
+ "\xa2\x3a\x6a\x8c\x7b\x3c\xf2\x51\xf8\xbe\x5f\x4f\x3b\x15\x05\xc4"
+ "\xb5\xbc\x19\xe7\x21\x85\xe9\x23\x06\x33\x62\xfb",
+ .m_size = 28,
+ .algo = OID_id_ecdsa_with_sha224,
+ .c =
+ "\x30\x81\x86\x02\x41\x01\xd6\x43\xe7\xff\x42\xb2\xba\x74\x35\xf6"
+ "\xdc\x6d\x02\x7b\x22\xac\xe2\xef\x07\x92\xee\x60\x94\x06\xf8\x3f"
+ "\x59\x0f\x74\xf0\x3f\xd8\x18\xc6\x37\x8a\xcb\xa7\xd8\x7d\x98\x85"
+ "\x29\x88\xff\x0b\x94\x94\x6c\xa6\x9b\x89\x8b\x1e\xfd\x09\x46\x6b"
+ "\xc7\xaf\x7a\xb9\x19\x0a\x02\x41\x3a\x26\x0d\x55\xcd\x23\x1e\x7d"
+ "\xa0\x5e\xf9\x88\xf3\xd2\x32\x90\x57\x0f\xf8\x65\x97\x6b\x09\x4d"
+ "\x22\x26\x0b\x5f\x49\x32\x6b\x91\x99\x30\x90\x0f\x1c\x8f\x78\xd3"
+ "\x9f\x0e\x64\xcc\xc4\xe8\x43\xd9\x0e\x1c\xad\x22\xda\x82\x00\x35"
+ "\xa3\x50\xb1\xa5\x98\x92\x2a\xa5\x52",
+ .c_size = 137,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ {
+ .key = /* secp521r1(sha256) */
+ "\x04\x01\x05\x3a\x6b\x3b\x5a\x0f\xa7\xb9\xb7\x32\x53\x4e\xe2\xae"
+ "\x0a\x52\xc5\xda\xdd\x5a\x79\x1c\x30\x2d\x33\x07\x79\xd5\x70\x14"
+ "\x61\x0c\xec\x26\x4d\xd8\x35\x57\x04\x1d\x88\x33\x4d\xce\x05\x36"
+ "\xa5\xaf\x56\x84\xfa\x0b\x9e\xff\x7b\x30\x4b\x92\x1d\x06\xf8\x81"
+ "\x24\x1e\x51\x00\x09\x21\x51\xf7\x46\x0a\x77\xdb\xb5\x0c\xe7\x9c"
+ "\xff\x27\x3c\x02\x71\xd7\x85\x36\xf1\xaa\x11\x59\xd8\xb8\xdc\x09"
+ "\xdc\x6d\x5a\x6f\x63\x07\x6c\xe1\xe5\x4d\x6e\x0f\x6e\xfb\x7c\x05"
+ "\x8a\xe9\x53\xa8\xcf\xce\x43\x0e\x82\x20\x86\xbc\x88\x9c\xb7\xe3"
+ "\xe6\x77\x1e\x1f\x8a",
+ .key_len = 133,
+ .params =
+ "\x30\x10\x06\x07\x2a\x86\x48\xce\x3d\x02\x01\x06\x05\x2b\x81\x04"
+ "\x00\x23",
+ .param_len = 18,
+ .m =
+ "\xcc\x97\x73\x0c\x73\xa2\x53\x2b\xfa\xd7\x83\x1d\x0c\x72\x1b\x39"
+ "\x80\x71\x8d\xdd\xc5\x9b\xff\x55\x32\x98\x25\xa2\x58\x2e\xb7\x73",
+ .m_size = 32,
+ .algo = OID_id_ecdsa_with_sha256,
+ .c =
+ "\x30\x81\x88\x02\x42\x00\xcd\xa5\x5f\x57\x52\x27\x78\x3a\xb5\x06"
+ "\x0f\xfd\x83\xfc\x0e\xd9\xce\x50\x9f\x7d\x1f\xca\x8b\xa8\x2d\x56"
+ "\x3c\xf6\xf0\xd8\xe1\xb7\x5d\x95\x35\x6f\x02\x0e\xaf\xe1\x4c\xae"
+ "\xce\x54\x76\x9a\xc2\x8f\xb8\x38\x1f\x46\x0b\x04\x64\x34\x79\xde"
+ "\x7e\xd7\x59\x10\xe9\xd9\xd5\x02\x42\x01\xcf\x50\x85\x38\xf9\x15"
+ "\x83\x18\x04\x6b\x35\xae\x65\xb5\x99\x12\x0a\xa9\x79\x24\xb9\x37"
+ "\x35\xdd\xa0\xe0\x87\x2c\x44\x4b\x5a\xee\xaf\xfa\x10\xdd\x9b\xfb"
+ "\x36\x1a\x31\x03\x42\x02\x5f\x50\xf0\xa2\x0d\x1c\x57\x56\x8f\x12"
+ "\xb7\x1d\x91\x55\x38\xb6\xf6\x34\x65\xc7\xbd",
+ .c_size = 139,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ {
+ .key = /* secp521r1(sha384) */
+ "\x04\x00\x2e\xd6\x21\x04\x75\xc3\xdc\x7d\xff\x0e\xf3\x70\x25\x2b"
+ "\xad\x72\xfc\x5a\x91\xf1\xd5\x9c\x64\xf3\x1f\x47\x11\x10\x62\x33"
+ "\xfd\x2e\xe8\x32\xca\x9e\x6f\x0a\x4c\x5b\x35\x9a\x46\xc5\xe7\xd4"
+ "\x38\xda\xb2\xf0\xf4\x87\xf3\x86\xf4\xea\x70\xad\x1e\xd4\x78\x8c"
+ "\x36\x18\x17\x00\xa2\xa0\x34\x1b\x2e\x6a\xdf\x06\xd6\x99\x2d\x47"
+ "\x50\x92\x1a\x8a\x72\x9c\x23\x44\xfa\xa7\xa9\xed\xa6\xef\x26\x14"
+ "\xb3\x9d\xfe\x5e\xa3\x8c\xd8\x29\xf8\xdf\xad\xa6\xab\xfc\xdd\x46"
+ "\x22\x6e\xd7\x35\xc7\x23\xb7\x13\xae\xb6\x34\xff\xd7\x80\xe5\x39"
+ "\xb3\x3b\x5b\x1b\x94",
+ .key_len = 133,
+ .params =
+ "\x30\x10\x06\x07\x2a\x86\x48\xce\x3d\x02\x01\x06\x05\x2b\x81\x04"
+ "\x00\x23",
+ .param_len = 18,
+ .m =
+ "\x36\x98\xd6\x82\xfa\xad\xed\x3c\xb9\x40\xb6\x4d\x9e\xb7\x04\x26"
+ "\xad\x72\x34\x44\xd2\x81\xb4\x9b\xbe\x01\x04\x7a\xd8\x50\xf8\x59"
+ "\xba\xad\x23\x85\x6b\x59\xbe\xfb\xf6\x86\xd4\x67\xa8\x43\x28\x76",
+ .m_size = 48,
+ .algo = OID_id_ecdsa_with_sha384,
+ .c =
+ "\x30\x81\x88\x02\x42\x00\x93\x96\x76\x3c\x27\xea\xaa\x9c\x26\xec"
+ "\x51\xdc\xe8\x35\x5e\xae\x16\xf2\x4b\x64\x98\xf7\xec\xda\xc7\x7e"
+ "\x42\x71\x86\x57\x2d\xf1\x7d\xe4\xdf\x9b\x7d\x9e\x47\xca\x33\x32"
+ "\x76\x06\xd0\xf9\xc0\xe4\xe6\x84\x59\xfd\x1a\xc4\x40\xdd\x43\xb8"
+ "\x6a\xdd\xfb\xe6\x63\x4e\x28\x02\x42\x00\xff\xc3\x6a\x87\x6e\xb5"
+ "\x13\x1f\x20\x55\xce\x37\x97\xc9\x05\x51\xe5\xe4\x3c\xbc\x93\x65"
+ "\x57\x1c\x30\xda\xa7\xcd\x26\x28\x76\x3b\x52\xdf\xc4\xc0\xdb\x54"
+ "\xdb\x8a\x0d\x6a\xc3\xf3\x7a\xd1\xfa\xe7\xa7\xe5\x5a\x94\x56\xcf"
+ "\x8f\xb4\x22\xc6\x4f\xab\x2b\x62\xc1\x42\xb1",
+ .c_size = 139,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ {
+ .key = /* secp521r1(sha512) */
+ "\x04\x00\xc7\x65\xee\x0b\x86\x7d\x8f\x02\xf1\x74\x5b\xb0\x4c\x3f"
+ "\xa6\x35\x60\x9f\x55\x23\x11\xcc\xdf\xb8\x42\x99\xee\x6c\x96\x6a"
+ "\x27\xa2\x56\xb2\x2b\x03\xad\x0f\xe7\x97\xde\x09\x5d\xb4\xc5\x5f"
+ "\xbd\x87\x37\xbf\x5a\x16\x35\x56\x08\xfd\x6f\x06\x1a\x1c\x84\xee"
+ "\xc3\x64\xb3\x00\x9e\xbd\x6e\x60\x76\xee\x69\xfd\x3a\xb8\xcd\x7e"
+ "\x91\x68\x53\x57\x44\x13\x2e\x77\x09\x2a\xbe\x48\xbd\x91\xd8\xf6"
+ "\x21\x16\x53\x99\xd5\xf0\x40\xad\xa6\xf8\x58\x26\xb6\x9a\xf8\x77"
+ "\xfe\x3a\x05\x1a\xdb\xa9\x0f\xc0\x6c\x76\x30\x8c\xd8\xde\x44\xae"
+ "\xd0\x17\xdf\x49\x6a",
+ .key_len = 133,
+ .params =
+ "\x30\x10\x06\x07\x2a\x86\x48\xce\x3d\x02\x01\x06\x05\x2b\x81\x04"
+ "\x00\x23",
+ .param_len = 18,
+ .m =
+ "\x5c\xa6\xbc\x79\xb8\xa0\x1e\x11\x83\xf7\xe9\x05\xdf\xba\xf7\x69"
+ "\x97\x22\x32\xe4\x94\x7c\x65\xbd\x74\xc6\x9a\x8b\xbd\x0d\xdc\xed"
+ "\xf5\x9c\xeb\xe1\xc5\x68\x40\xf2\xc7\x04\xde\x9e\x0d\x76\xc5\xa3"
+ "\xf9\x3c\x6c\x98\x08\x31\xbd\x39\xe8\x42\x7f\x80\x39\x6f\xfe\x68",
+ .m_size = 64,
+ .algo = OID_id_ecdsa_with_sha512,
+ .c =
+ "\x30\x81\x88\x02\x42\x01\x5c\x71\x86\x96\xac\x21\x33\x7e\x4e\xaa"
+ "\x86\xec\xa8\x05\x03\x52\x56\x63\x0e\x02\xcc\x94\xa9\x05\xb9\xfb"
+ "\x62\x1e\x42\x03\x6c\x74\x8a\x1f\x12\x3e\xb7\x7e\x51\xff\x7f\x27"
+ "\x93\xe8\x6c\x49\x7d\x28\xfc\x80\xa6\x13\xfc\xb6\x90\xf7\xbb\x28"
+ "\xb5\x04\xb0\xb6\x33\x1c\x7e\x02\x42\x01\x70\x43\x52\x1d\xe3\xc6"
+ "\xbd\x5a\x40\x95\x35\x89\x4f\x41\x5f\x9e\x19\x88\x05\x3e\x43\x39"
+ "\x01\xbd\xb7\x7a\x76\x37\x51\x47\x49\x98\x12\x71\xd0\xe9\xca\xa7"
+ "\xc0\xcb\xaa\x00\x55\xbb\x6a\xb4\x73\x00\xd2\x72\x74\x13\x63\x39"
+ "\xa6\xe5\x25\x46\x1e\x77\x44\x78\xe0\xd1\x04",
+ .c_size = 139,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+};
+
/*
* EC-RDSA test vectors are generated by gost-engine.
*/
--
2.43.0
Add the parameters for the NIST P521 curve and define a new curve ID
for it. Make the curve available in ecc_get_curve.
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/ecc.c | 2 ++
crypto/ecc_curve_defs.h | 45 +++++++++++++++++++++++++++++++++++++++++
include/crypto/ecdh.h | 1 +
3 files changed, 48 insertions(+)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index 89ad45cf2404..164898ad1961 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -60,6 +60,8 @@ const struct ecc_curve *ecc_get_curve(unsigned int curve_id)
return &nist_p256;
case ECC_CURVE_NIST_P384:
return &nist_p384;
+ case ECC_CURVE_NIST_P521:
+ return &nist_p521;
default:
return NULL;
}
diff --git a/crypto/ecc_curve_defs.h b/crypto/ecc_curve_defs.h
index 9719934c9428..09a221657c31 100644
--- a/crypto/ecc_curve_defs.h
+++ b/crypto/ecc_curve_defs.h
@@ -86,6 +86,51 @@ static struct ecc_curve nist_p384 = {
.b = nist_p384_b
};
+/* NIST P-521 */
+static u64 nist_p521_g_x[] = { 0xf97e7e31c2e5bd66ull, 0x3348b3c1856a429bull,
+ 0xfe1dc127a2ffa8deull, 0xa14b5e77efe75928ull,
+ 0xf828af606b4d3dbaull, 0x9c648139053fb521ull,
+ 0x9e3ecb662395b442ull, 0x858e06b70404e9cdull,
+ 0xc6ull };
+static u64 nist_p521_g_y[] = { 0x88be94769fd16650ull, 0x353c7086a272c240ull,
+ 0xc550b9013fad0761ull, 0x97ee72995ef42640ull,
+ 0x17afbd17273e662cull, 0x98f54449579b4468ull,
+ 0x5c8a5fb42c7d1bd9ull, 0x39296a789a3bc004ull,
+ 0x118ull };
+static u64 nist_p521_p[] = { 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0x1ffull };
+static u64 nist_p521_n[] = { 0xbb6fb71e91386409ull, 0x3bb5c9b8899c47aeull,
+ 0x7fcc0148f709a5d0ull, 0x51868783bf2f966bull,
+ 0xfffffffffffffffaull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0x1ffull };
+static u64 nist_p521_a[] = { 0xfffffffffffffffcull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0xffffffffffffffffull, 0xffffffffffffffffull,
+ 0x1ffull };
+static u64 nist_p521_b[] = { 0xef451fd46b503f00ull, 0x3573df883d2c34f1ull,
+ 0x1652c0bd3bb1bf07ull, 0x56193951ec7e937bull,
+ 0xb8b489918ef109e1ull, 0xa2da725b99b315f3ull,
+ 0x929a21a0b68540eeull, 0x953eb9618e1c9a1full,
+ 0x051ull };
+static struct ecc_curve nist_p521 = {
+ .name = "nist_521",
+ .nbits = 521,
+ .g = {
+ .x = nist_p521_g_x,
+ .y = nist_p521_g_y,
+ .ndigits = 9,
+ },
+ .p = nist_p521_p,
+ .n = nist_p521_n,
+ .a = nist_p521_a,
+ .b = nist_p521_b
+};
+
/* curve25519 */
static u64 curve25519_g_x[] = { 0x0000000000000009, 0x0000000000000000,
0x0000000000000000, 0x0000000000000000 };
diff --git a/include/crypto/ecdh.h b/include/crypto/ecdh.h
index a9f98078d29c..9784ecdd2fb4 100644
--- a/include/crypto/ecdh.h
+++ b/include/crypto/ecdh.h
@@ -26,6 +26,7 @@
#define ECC_CURVE_NIST_P192 0x0001
#define ECC_CURVE_NIST_P256 0x0002
#define ECC_CURVE_NIST_P384 0x0003
+#define ECC_CURVE_NIST_P521 0x0004
/**
* struct ecdh - define an ECDH private key
--
2.43.0
Prepare the x509 parser to accept NIST P521 certificates and add the
OID for ansip521r1, which is the identifier for NIST P521.
Cc: David Howells <[email protected]>
Signed-off-by: Stefan Berger <[email protected]>
---
crypto/asymmetric_keys/x509_cert_parser.c | 3 +++
include/linux/oid_registry.h | 1 +
2 files changed, 4 insertions(+)
diff --git a/crypto/asymmetric_keys/x509_cert_parser.c b/crypto/asymmetric_keys/x509_cert_parser.c
index 487204d39426..99f809b7910b 100644
--- a/crypto/asymmetric_keys/x509_cert_parser.c
+++ b/crypto/asymmetric_keys/x509_cert_parser.c
@@ -538,6 +538,9 @@ int x509_extract_key_data(void *context, size_t hdrlen,
case OID_id_ansip384r1:
ctx->cert->pub->pkey_algo = "ecdsa-nist-p384";
break;
+ case OID_id_ansip521r1:
+ ctx->cert->pub->pkey_algo = "ecdsa-nist-p521";
+ break;
default:
return -ENOPKG;
}
diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
index 3921fbed0b28..af16d96fbbf2 100644
--- a/include/linux/oid_registry.h
+++ b/include/linux/oid_registry.h
@@ -65,6 +65,7 @@ enum OID {
OID_Scram, /* 1.3.6.1.5.5.14 */
OID_certAuthInfoAccess, /* 1.3.6.1.5.5.7.1.1 */
OID_id_ansip384r1, /* 1.3.132.0.34 */
+ OID_id_ansip521r1, /* 1.3.132.0.35 */
OID_sha256, /* 2.16.840.1.101.3.4.2.1 */
OID_sha384, /* 2.16.840.1.101.3.4.2.2 */
OID_sha512, /* 2.16.840.1.101.3.4.2.3 */
--
2.43.0
On Fri, Feb 23, 2024 at 03:41:45PM -0500, Stefan Berger wrote:
> --- a/include/crypto/internal/ecc.h
> +++ b/include/crypto/internal/ecc.h
> @@ -75,6 +75,17 @@ static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> ecc_swap_digits(tmp, out, ndigits);
> }
>
> +/**
> + * ecc_curve_get_nbits() - Get the number of bits of the curve
> + * @curve: The curve
> + */
> +static inline unsigned int ecc_curve_get_nbits(const struct ecc_curve *curve)
> +{
> + if (curve->nbits)
> + return curve->nbits;
> + return curve->g.ndigits << ECC_DIGITS_TO_BYTES_SHIFT * 8;
> +}
Since you're amending struct ecc_curve with an extra nbits value anyway,
why not statically fill it in for all curves, instead of adding this
extra complexity in the code?
Thanks,
Lukas
On 2/29/24 11:48, Lukas Wunner wrote:
> On Thu, Feb 29, 2024 at 09:57:30AM -0500, Stefan Berger wrote:
>> static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>> u64 *out, unsigned int ndigits)
>> {
>> unsigned int o = nbytes & 7;
>> u64 msd = 0;
>> size_t i;
>>
>> if (o == 0) {
>> ecc_swap_digits(in, out, ndigits);
>> } else {
>> for (i = 0; i < o; i++)
>> msd = (msd << 8) | in[i];
>> out[ndigits - 1] = msd;
>> ecc_swap_digits(&in[o], out, ndigits - 1);
>> }
>> }
>
> Might be beneficial to add a code comment explaining the else-branch
> is for curves with key length not a multiple of 64 bits (such as NIST P521).
Will do. I am also using this here now since it's safer:
ecc_swap_digits(&in[o], out, (nbytes - o) >> 3);
Stefan
>
> Otherwise LGTM, thanks!
>
> Lukas
On 2/29/24 04:34, Lukas Wunner wrote:
> On Fri, Feb 23, 2024 at 03:41:39PM -0500, Stefan Berger wrote:
>> This series adds support for the NIST P521 curve to the ecdsa module.
>>
>> 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.
>
> Don't you also need to amend software_key_query()? In the "issig" case,
> it calculates len = crypto_sig_maxsize(sig), which is 72 bytes for P521,
> then further below calculates "info->max_sig_size = 2 * (len + 3) + 2;"
>
> I believe the ASN.1 encoded integers are just 66 bytes instead of 72,
> so info->max_sig_size is 6 bytes too large. Am I missing something?
Right! Good catch. While the 'keyctl pkey_verify' interface was already
working the space was too generous with 72 bytes. So I adjusted
ecdsa_max_size now to base the size calculations on nbits rather than
ndigits and we now get 66 bytes.
For so-far supported curves the max_sig_size is:
2 bytes for sequence (0x30) + following length as single byte
Each coordinate may have a 0 prepended to make a possibly negative
number positive:
=> 2 + 2 * (2 + 1 + len)
In case of NIST P521 the max signature length is calculated as follows:
3 bytes for sequence (0x30) + following length as 2 bytes
The coordinates won't have a preprended 0 byte since only 1 bit is used
in the highest bit, so only 2 bytes for
=> 3 + 2 * (2 + len)
We would have to adjust the math there as well. The max. signature size
for NIST P521 is 139 rather than 140 with the first formula.
Stefan
>
> Thanks,
>
> Lukas
On 2/27/24 15:15, Lukas Wunner wrote:
> On Fri, Feb 23, 2024 at 03:41:45PM -0500, Stefan Berger wrote:
>> --- a/include/crypto/internal/ecc.h
>> +++ b/include/crypto/internal/ecc.h
>> @@ -75,6 +75,17 @@ static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>> ecc_swap_digits(tmp, out, ndigits);
>> }
>>
>> +/**
>> + * ecc_curve_get_nbits() - Get the number of bits of the curve
>> + * @curve: The curve
>> + */
>> +static inline unsigned int ecc_curve_get_nbits(const struct ecc_curve *curve)
>> +{
>> + if (curve->nbits)
>> + return curve->nbits;
>> + return curve->g.ndigits << ECC_DIGITS_TO_BYTES_SHIFT * 8;
>> +}
>
> Since you're amending struct ecc_curve with an extra nbits value anyway,
> why not statically fill it in for all curves, instead of adding this
> extra complexity in the code?
I filled in all curves now, including ecrdsa cruves and curve25519.
Stefan
>
> Thanks,
>
> Lukas
On Thu, Feb 29, 2024 at 09:57:30AM -0500, Stefan Berger wrote:
> static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> u64 *out, unsigned int ndigits)
> {
> unsigned int o = nbytes & 7;
> u64 msd = 0;
> size_t i;
>
> if (o == 0) {
> ecc_swap_digits(in, out, ndigits);
> } else {
> for (i = 0; i < o; i++)
> msd = (msd << 8) | in[i];
> out[ndigits - 1] = msd;
> ecc_swap_digits(&in[o], out, ndigits - 1);
> }
> }
Might be beneficial to add a code comment explaining the else-branch
is for curves with key length not a multiple of 64 bits (such as NIST P521).
Otherwise LGTM, thanks!
Lukas
On Fri, Feb 23, 2024 at 03:41:39PM -0500, Stefan Berger wrote:
> This series adds support for the NIST P521 curve to the ecdsa module.
>
> 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.
Don't you also need to amend software_key_query()? In the "issig" case,
it calculates len = crypto_sig_maxsize(sig), which is 72 bytes for P521,
then further below calculates "info->max_sig_size = 2 * (len + 3) + 2;"
I believe the ASN.1 encoded integers are just 66 bytes instead of 72,
so info->max_sig_size is 6 bytes too large. Am I missing something?
Thanks,
Lukas
On 3/1/24 15:26, Jarkko Sakkinen wrote:
> On Thu Feb 29, 2024 at 4:57 PM EET, Stefan Berger wrote:
>>
>>
>> On 2/29/24 04:11, Lukas Wunner wrote:
>>> On Fri, Feb 23, 2024 at 03:41:40PM -0500, Stefan Berger wrote:
>>>> +static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>>>> + u64 *out, unsigned int ndigits)
>>>> +{
>>>> + unsigned int sz = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
>>>> + u8 tmp[ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT];
>>>> + unsigned int o = sz - nbytes;
>>>> +
>>>> + memset(tmp, 0, o);
>>>> + memcpy(&tmp[o], in, nbytes);
>>>> + ecc_swap_digits(tmp, out, ndigits);
>>>> +}
>>>
>>> Copying the whole key into tmp seems inefficient. You only need
>>> special handling for the first few bytes of "in" (6 bytes in the
>>> P521 case) and could use ecc_swap_digits() to convert the rest
>>> of "in" directly to "out" without using tmp.
>>>
>>> So it would be sufficient to allocate the first digit on the stack,
>>> memset + memcpy, then convert that to native byte order into "in[0]"
>>> and use ecc_swap_digits() for the rest.
>>>
>>> And the special handling would be conditional on "!o", so is skipped
>>> for existing curves.
>>
>> Thanks. It looks like this now:
>>
>> static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>> u64 *out, unsigned int ndigits)
>> {
>> unsigned int o = nbytes & 7;
>> u64 msd = 0;
>> size_t i;
>>
>> if (o == 0) {
>> ecc_swap_digits(in, out, ndigits);
>> } else {
>> for (i = 0; i < o; i++)
>> msd = (msd << 8) | in[i];
>> out[ndigits - 1] = msd;
>> ecc_swap_digits(&in[o], out, ndigits - 1);
>
> This would be more stream-lined IMHO:
>
> unsigned int o = nbytes & 7;
> unsigned int n = ndigits;
> u64 msd = 0;
> size_t i;
>
> if (o != 0) {
> for (i = 0; i < o; i++)
> msd = (msd << 8) | in[i];
>
> out[--n] = msd;
> }
>
> ecc_swap_digits(in, out, n);
You forgot to advance 'in'.
>
> BR, Jarkko
>
On 3/2/24 09:00, Lukas Wunner wrote:
> On Fri, Mar 01, 2024 at 10:26:29PM +0200, Jarkko Sakkinen wrote:
>> On Thu Feb 29, 2024 at 4:57 PM EET, Stefan Berger wrote:
>>>
>>>
>>> On 2/29/24 04:11, Lukas Wunner wrote:
>>>> On Fri, Feb 23, 2024 at 03:41:40PM -0500, Stefan Berger wrote:
>>>>> +static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>>>>> + u64 *out, unsigned int ndigits)
>>>>> +{
>>>>> + unsigned int sz = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
>>>>> + u8 tmp[ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT];
>>>>> + unsigned int o = sz - nbytes;
>>>>> +
>>>>> + memset(tmp, 0, o);
>>>>> + memcpy(&tmp[o], in, nbytes);
>>>>> + ecc_swap_digits(tmp, out, ndigits);
>>>>> +}
>>>>
>>>> Copying the whole key into tmp seems inefficient. You only need
>>>> special handling for the first few bytes of "in" (6 bytes in the
>>>> P521 case) and could use ecc_swap_digits() to convert the rest
>>>> of "in" directly to "out" without using tmp.
>>>>
>>>> So it would be sufficient to allocate the first digit on the stack,
>>>> memset + memcpy, then convert that to native byte order into "in[0]"
>>>> and use ecc_swap_digits() for the rest.
>>>>
>>>> And the special handling would be conditional on "!o", so is skipped
>>>> for existing curves.
>>>
>>> Thanks. It looks like this now:
>>>
>>> static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
>>> u64 *out, unsigned int ndigits)
>>> {
>>> unsigned int o = nbytes & 7;
>>> u64 msd = 0;
>>> size_t i;
>>>
>>> if (o == 0) {
>>> ecc_swap_digits(in, out, ndigits);
>>> } else {
>>> for (i = 0; i < o; i++)
>>> msd = (msd << 8) | in[i];
>>> out[ndigits - 1] = msd;
>>> ecc_swap_digits(&in[o], out, ndigits - 1);
>>
>> This would be more stream-lined IMHO:
>>
>> unsigned int o = nbytes & 7;
>> unsigned int n = ndigits;
>> u64 msd = 0;
>> size_t i;
>>
>> if (o != 0) {
>> for (i = 0; i < o; i++)
>> msd = (msd << 8) | in[i];
>>
>> out[--n] = msd;
>> }
>>
>> ecc_swap_digits(in, out, n);
>
> Maybe eliminate the for-loop as well?
>
> unsigned int o = nbytes & 7;
> u64 msd = 0;
>
> if (o != 0) {
> /* if key length is not a multiple of 64 bits (NIST P521) */
> memcpy((u8 *)&msd + sizeof(msd) - o, in, o);
> out[--ndigits] = be64_to_cpu(msd);
> in += o;
> }
>
> ecc_swap_digits(in, out, ndigits);
>
Will take this for v5 with your Suggested-by:, ok?
Stefan
On Sat Mar 2, 2024 at 4:00 PM EET, Lukas Wunner wrote:
> On Fri, Mar 01, 2024 at 10:26:29PM +0200, Jarkko Sakkinen wrote:
> > On Thu Feb 29, 2024 at 4:57 PM EET, Stefan Berger wrote:
> > >
> > >
> > > On 2/29/24 04:11, Lukas Wunner wrote:
> > > > On Fri, Feb 23, 2024 at 03:41:40PM -0500, Stefan Berger wrote:
> > > >> +static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> > > >> + u64 *out, unsigned int ndigits)
> > > >> +{
> > > >> + unsigned int sz = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
> > > >> + u8 tmp[ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT];
> > > >> + unsigned int o = sz - nbytes;
> > > >> +
> > > >> + memset(tmp, 0, o);
> > > >> + memcpy(&tmp[o], in, nbytes);
> > > >> + ecc_swap_digits(tmp, out, ndigits);
> > > >> +}
> > > >
> > > > Copying the whole key into tmp seems inefficient. You only need
> > > > special handling for the first few bytes of "in" (6 bytes in the
> > > > P521 case) and could use ecc_swap_digits() to convert the rest
> > > > of "in" directly to "out" without using tmp.
> > > >
> > > > So it would be sufficient to allocate the first digit on the stack,
> > > > memset + memcpy, then convert that to native byte order into "in[0]"
> > > > and use ecc_swap_digits() for the rest.
> > > >
> > > > And the special handling would be conditional on "!o", so is skipped
> > > > for existing curves.
> > >
> > > Thanks. It looks like this now:
> > >
> > > static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> > > u64 *out, unsigned int ndigits)
> > > {
> > > unsigned int o = nbytes & 7;
> > > u64 msd = 0;
> > > size_t i;
> > >
> > > if (o == 0) {
> > > ecc_swap_digits(in, out, ndigits);
> > > } else {
> > > for (i = 0; i < o; i++)
> > > msd = (msd << 8) | in[i];
> > > out[ndigits - 1] = msd;
> > > ecc_swap_digits(&in[o], out, ndigits - 1);
> >
> > This would be more stream-lined IMHO:
> >
> > unsigned int o = nbytes & 7;
> > unsigned int n = ndigits;
> > u64 msd = 0;
> > size_t i;
> >
> > if (o != 0) {
> > for (i = 0; i < o; i++)
> > msd = (msd << 8) | in[i];
> >
> > out[--n] = msd;
> > }
> >
> > ecc_swap_digits(in, out, n);
>
> Maybe eliminate the for-loop as well?
>
> unsigned int o = nbytes & 7;
> u64 msd = 0;
>
> if (o != 0) {
> /* if key length is not a multiple of 64 bits (NIST P521) */
> memcpy((u8 *)&msd + sizeof(msd) - o, in, o);
> out[--ndigits] = be64_to_cpu(msd);
> in += o;
> }
>
> ecc_swap_digits(in, out, ndigits);
+1
BR, Jarkko
On Sat, Mar 02, 2024 at 04:19:49PM -0500, Stefan Berger wrote:
> On 3/2/24 09:00, Lukas Wunner wrote:
> > Maybe eliminate the for-loop as well?
> >
> > unsigned int o = nbytes & 7;
> > u64 msd = 0;
> >
> > if (o != 0) {
> > /* if key length is not a multiple of 64 bits (NIST P521) */
> > memcpy((u8 *)&msd + sizeof(msd) - o, in, o);
> > out[--ndigits] = be64_to_cpu(msd);
> > in += o;
> > }
> >
> > ecc_swap_digits(in, out, ndigits);
>
> Will take this for v5 with your Suggested-by:, ok?
Sure, feel free to, but better test it because I haven't. :-)
I'll look through the rest of the series tomorrow. %-)
Thanks,
Lukas
On Fri, Mar 01, 2024 at 10:26:29PM +0200, Jarkko Sakkinen wrote:
> On Thu Feb 29, 2024 at 4:57 PM EET, Stefan Berger wrote:
> >
> >
> > On 2/29/24 04:11, Lukas Wunner wrote:
> > > On Fri, Feb 23, 2024 at 03:41:40PM -0500, Stefan Berger wrote:
> > >> +static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> > >> + u64 *out, unsigned int ndigits)
> > >> +{
> > >> + unsigned int sz = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
> > >> + u8 tmp[ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT];
> > >> + unsigned int o = sz - nbytes;
> > >> +
> > >> + memset(tmp, 0, o);
> > >> + memcpy(&tmp[o], in, nbytes);
> > >> + ecc_swap_digits(tmp, out, ndigits);
> > >> +}
> > >
> > > Copying the whole key into tmp seems inefficient. You only need
> > > special handling for the first few bytes of "in" (6 bytes in the
> > > P521 case) and could use ecc_swap_digits() to convert the rest
> > > of "in" directly to "out" without using tmp.
> > >
> > > So it would be sufficient to allocate the first digit on the stack,
> > > memset + memcpy, then convert that to native byte order into "in[0]"
> > > and use ecc_swap_digits() for the rest.
> > >
> > > And the special handling would be conditional on "!o", so is skipped
> > > for existing curves.
> >
> > Thanks. It looks like this now:
> >
> > static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
> > u64 *out, unsigned int ndigits)
> > {
> > unsigned int o = nbytes & 7;
> > u64 msd = 0;
> > size_t i;
> >
> > if (o == 0) {
> > ecc_swap_digits(in, out, ndigits);
> > } else {
> > for (i = 0; i < o; i++)
> > msd = (msd << 8) | in[i];
> > out[ndigits - 1] = msd;
> > ecc_swap_digits(&in[o], out, ndigits - 1);
>
> This would be more stream-lined IMHO:
>
> unsigned int o = nbytes & 7;
> unsigned int n = ndigits;
> u64 msd = 0;
> size_t i;
>
> if (o != 0) {
> for (i = 0; i < o; i++)
> msd = (msd << 8) | in[i];
>
> out[--n] = msd;
> }
>
> ecc_swap_digits(in, out, n);
Maybe eliminate the for-loop as well?
unsigned int o = nbytes & 7;
u64 msd = 0;
if (o != 0) {
/* if key length is not a multiple of 64 bits (NIST P521) */
memcpy((u8 *)&msd + sizeof(msd) - o, in, o);
out[--ndigits] = be64_to_cpu(msd);
in += o;
}
ecc_swap_digits(in, out, ndigits);