* [PATCH 1/2] crypto: ecc - Keep the random initial Z below 2^521 on P-521
2026-11-14 8:44 [PATCH 0/2] crypto: ecc - Fix P-521 public key generation Arun Iyengar via B4 Relay
@ 2026-11-14 8:44 ` Arun Iyengar via B4 Relay
2026-11-14 8:44 ` [PATCH 2/2] crypto: ecc - Fix P-521 scalar multiplication for small scalars Arun Iyengar via B4 Relay
1 sibling, 0 replies; 3+ messages in thread
From: Arun Iyengar via B4 Relay @ 2026-11-14 8:44 UTC (permalink / raw)
To: Lukas Wunner, Ignat Korchagin, Stefan Berger, Herbert Xu,
David S. Miller, Jarkko Sakkinen
Cc: linux-crypto, linux-kernel, Erwin Pawliczek, Arun Iyengar
From: Arun Iyengar <aiyengar1990@gmail.com>
Erwin Pawliczek's commit cd65eaf17841 ("crypto: ecc - Randomize the
initial Z in ecc_make_pub_key()") takes the initial Z from ndigits * 8
random bytes, as crypto_ecdh_shared_secret() already did. On P-521 that
is a 576-bit number, but vli_mmod_fast_521() only reduces products of
numbers below 2^521. With a 576-bit Z, every P-521 ecc_make_pub_key()
call returns -EAGAIN. There is no in-tree P-521 caller yet.
Get Z from one helper at both sites that keeps the random bits to the
curve's bit length. The other curves are unchanged.
Tested in UML: P-521 ecc_make_pub_key() now matches a Python reference
for the tested keys from 2^522 - 2n up to n - 3. Smaller keys are fixed
by the next patch. The ecdsa-nist-p521 self-tests still pass.
Fixes: cd65eaf17841 ("crypto: ecc - Randomize the initial Z in ecc_make_pub_key()")
Cc: Erwin Pawliczek <pawliczekerwin@gmail.com>
Signed-off-by: Arun Iyengar <aiyengar1990@gmail.com>
---
crypto/ecc.c | 20 ++++++++++++--------
1 file changed, 12 insertions(+), 8 deletions(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index 6696bf0d90a6..a56a33e4eccb 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1609,13 +1609,22 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits,
}
EXPORT_SYMBOL(ecc_gen_privkey);
+/* Random initial Z for ecc_point_mult(), below 2^nbits */
+static void ecc_rand_z(const struct ecc_curve *curve, u64 *z,
+ unsigned int ndigits)
+{
+ get_random_bytes(z, ndigits << ECC_DIGITS_TO_BYTES_SHIFT);
+ /* P-521: the fast reduction only takes products of 521-bit numbers */
+ if (curve->nbits % 64)
+ z[ndigits - 1] &= GENMASK_ULL(curve->nbits % 64 - 1, 0);
+}
+
int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
const u64 *private_key, u64 *public_key)
{
int ret = 0;
struct ecc_point *pk;
u64 rand_z[ECC_MAX_DIGITS];
- unsigned int nbytes;
const struct ecc_curve *curve = ecc_get_curve(curve_id);
if (!private_key || ndigits > ARRAY_SIZE(rand_z)) {
@@ -1623,9 +1632,7 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
goto out;
}
- nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
-
- get_random_bytes(rand_z, nbytes);
+ ecc_rand_z(curve, rand_z, ndigits);
pk = ecc_alloc_point(ndigits);
if (!pk) {
@@ -1719,7 +1726,6 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
int ret = 0;
struct ecc_point *product, *pk;
u64 rand_z[ECC_MAX_DIGITS];
- unsigned int nbytes;
const struct ecc_curve *curve = ecc_get_curve(curve_id);
if (!private_key || !public_key || ndigits > ARRAY_SIZE(rand_z)) {
@@ -1727,9 +1733,7 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
goto out;
}
- nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
-
- get_random_bytes(rand_z, nbytes);
+ ecc_rand_z(curve, rand_z, ndigits);
pk = ecc_alloc_point(ndigits);
if (!pk) {
--
2.55.0
^ permalink raw reply [flat|nested] 3+ messages in thread* [PATCH 2/2] crypto: ecc - Fix P-521 scalar multiplication for small scalars
2026-11-14 8:44 [PATCH 0/2] crypto: ecc - Fix P-521 public key generation Arun Iyengar via B4 Relay
2026-11-14 8:44 ` [PATCH 1/2] crypto: ecc - Keep the random initial Z below 2^521 on P-521 Arun Iyengar via B4 Relay
@ 2026-11-14 8:44 ` Arun Iyengar via B4 Relay
1 sibling, 0 replies; 3+ messages in thread
From: Arun Iyengar via B4 Relay @ 2026-11-14 8:44 UTC (permalink / raw)
To: Lukas Wunner, Ignat Korchagin, Stefan Berger, Herbert Xu,
David S. Miller, Jarkko Sakkinen
Cc: linux-crypto, linux-kernel, Erwin Pawliczek, Arun Iyengar
From: Arun Iyengar <aiyengar1990@gmail.com>
Stefan Berger's commit 114e80437e0e ("crypto: ecc - Add special case
for NIST P521 in ecc_point_mult") made the ladder run on k + n or
k + 2n with bit 522 as the top bit.
For k < n, k + n never carries out of the nine digits, so k + 2n is
always used. Its bit 522 is set only for k >= 2^522 - 2n (about
2^259.5); for smaller k the result is (k + 2^522) * P instead of k * P.
Use k + n if its bit 521 is set, else k + 2n, and start the ladder at
bit 521.
No caller is affected today: the only P-521 caller,
ecc_is_pubkey_valid_full(), passes k = n.
Tested in UML on top of the previous patch: ecc_make_pub_key() on
P-521 now matches a Python reference for k = 2, 3, 4, 2^200 + 5, k
around 2^521 - n and 2^522 - 2n, and 40 random k. Before, every k
below 2^522 - 2n was wrong. The ecdsa-nist-p521 self-tests (k = n)
still pass.
Fixes: 114e80437e0e ("crypto: ecc - Add special case for NIST P521 in ecc_point_mult")
Signed-off-by: Arun Iyengar <aiyengar1990@gmail.com>
---
crypto/ecc.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index a56a33e4eccb..370c60595fa9 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1365,11 +1365,14 @@ 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];
- if (curve->nbits == 521) /* NIST P521 */
- num_bits = curve->nbits + 2;
- else
+ if (curve->nbits == 521) { /* NIST P521 */
+ /* k + n or k + 2n, whichever has bit 521 as its top bit */
+ carry = !!vli_test_bit(sk[0], curve->nbits);
+ num_bits = curve->nbits + 1;
+ } else {
num_bits = sizeof(u64) * ndigits * 8 + 1;
+ }
+ scalar = sk[!carry];
vli_set(rx[1], point->x, ndigits);
vli_set(ry[1], point->y, ndigits);
--
2.55.0
^ permalink raw reply [flat|nested] 3+ messages in thread