From patchwork Thu Nov 9 14:20:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marcel Holtmann X-Patchwork-Id: 13451186 Received: from mail.holtmann.org (coyote.holtmann.net [212.227.132.17]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 6DD571E522 for ; Thu, 9 Nov 2023 14:21:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=holtmann.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=holtmann.org Authentication-Results: smtp.subspace.kernel.org; dkim=none Received: from fedora.. (p4fefc822.dip0.t-ipconnect.de [79.239.200.34]) by mail.holtmann.org (Postfix) with ESMTPSA id 67842CECE3 for ; Thu, 9 Nov 2023 15:20:58 +0100 (CET) From: Marcel Holtmann To: ell@lists.linux.dev Subject: [PATCH 1/3] ecc: Make product variable of _vli_mmod_fast const Date: Thu, 9 Nov 2023 15:20:54 +0100 Message-ID: <20231109142056.12385-1-marcel@holtmann.org> X-Mailer: git-send-email 2.41.0 Precedence: bulk X-Mailing-List: ell@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 --- ell/ecc-external.c | 2 +- ell/ecc-private.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/ell/ecc-external.c b/ell/ecc-external.c index a851271df26e..46f710bff11b 100644 --- a/ell/ecc-external.c +++ b/ell/ecc-external.c @@ -550,7 +550,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product, /* Computes result = product % curve_prime * from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -bool _vli_mmod_fast(uint64_t *result, uint64_t *product, +bool _vli_mmod_fast(uint64_t *result, const uint64_t *product, const uint64_t *curve_prime, unsigned int ndigits) { uint64_t tmp[2 * L_ECC_MAX_DIGITS]; diff --git a/ell/ecc-private.h b/ell/ecc-private.h index 880ae800e8d8..dcf676d9614a 100644 --- a/ell/ecc-private.h +++ b/ell/ecc-private.h @@ -86,7 +86,7 @@ void _vli_mod_add(uint64_t *result, const uint64_t *left, const uint64_t *right, void _vli_rshift1(uint64_t *vli, unsigned int ndigits); -bool _vli_mmod_fast(uint64_t *result, uint64_t *product, +bool _vli_mmod_fast(uint64_t *result, const uint64_t *product, const uint64_t *curve_prime, unsigned int ndigits); void _vli_mod_mult_fast(uint64_t *result, const uint64_t *left, From patchwork Thu Nov 9 14:20:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marcel Holtmann X-Patchwork-Id: 13451187 Received: from mail.holtmann.org (coyote.holtmann.net [212.227.132.17]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 6DDB71E535 for ; Thu, 9 Nov 2023 14:21:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=holtmann.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=holtmann.org Authentication-Results: smtp.subspace.kernel.org; dkim=none Received: from fedora.. (p4fefc822.dip0.t-ipconnect.de [79.239.200.34]) by mail.holtmann.org (Postfix) with ESMTPSA id 89AB8CECE8 for ; Thu, 9 Nov 2023 15:20:58 +0100 (CET) From: Marcel Holtmann To: ell@lists.linux.dev Subject: [PATCH 2/3] ecc: Introduce _vli_mmod_slow that works with curve_p and curve_n Date: Thu, 9 Nov 2023 15:20:55 +0100 Message-ID: <20231109142056.12385-2-marcel@holtmann.org> X-Mailer: git-send-email 2.41.0 Precedence: bulk X-Mailing-List: ell@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 --- ell/ecc-external.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++ ell/ecc-private.h | 3 ++ 2 files changed, 78 insertions(+) diff --git a/ell/ecc-external.c b/ell/ecc-external.c index 46f710bff11b..7a0882326811 100644 --- a/ell/ecc-external.c +++ b/ell/ecc-external.c @@ -314,6 +314,81 @@ void _vli_mod_sub(uint64_t *result, const uint64_t *left, _vli_add(result, result, mod, ndigits); } +/* Counts the number of 64-bit "digits" in vli. */ +static unsigned int _vli_num_digits(const uint64_t *vli, unsigned int ndigits) +{ + int i; + + /* Search from the end until we find a non-zero digit. + * We do it in reverse because we expect that most digits will + * be nonzero. + */ + for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); + + return (i + 1); +} + +/* Counts the number of bits required for vli. */ +static unsigned int _vli_num_bits(const uint64_t *vli, unsigned int ndigits) +{ + unsigned int i, num_digits; + uint64_t digit; + + num_digits = _vli_num_digits(vli, ndigits); + if (num_digits == 0) + return 0; + + digit = vli[num_digits - 1]; + for (i = 0; digit; i++) + digit >>= 1; + + return ((num_digits - 1) * 64 + i); +} + +/* Computes result = product % mod, where product is 2N words long. + * Currently only designed to work for curve_p or curve_n. + */ +void _vli_mmod_slow(uint64_t *result, const uint64_t *product, + const uint64_t *mod, unsigned int ndigits) +{ + uint64_t mod_m[2 * L_ECC_MAX_DIGITS]; + uint64_t tmp[2 * L_ECC_MAX_DIGITS]; + uint64_t *v[2] = { tmp, (uint64_t *) product }; + uint64_t carry = 0; + unsigned int i; + /* Shift mod so its highest set bit is at the maximum position. */ + int shift = (ndigits * 2 * 64) - _vli_num_bits(mod, ndigits); + int word_shift = shift / 64; + int bit_shift = shift % 64; + + vli_clear(mod_m, word_shift); + if (bit_shift > 0) { + for (i = 0; i < ndigits; ++i) { + mod_m[word_shift + i] = (mod[i] << bit_shift) | carry; + carry = mod[i] >> (64 - bit_shift); + } + } else + vli_set(mod_m + word_shift, mod, ndigits); + + for (i = 1; shift >= 0; --shift) { + uint64_t borrow = 0; + unsigned int j; + + for (j = 0; j < ndigits * 2; ++j) { + uint64_t diff = v[i][j] - mod_m[j] - borrow; + + if (diff != v[i][j]) + borrow = (diff > v[i][j]); + v[1 - i][j] = diff; + } + i = !(i ^ borrow); /* Swap the index if there was no borrow */ + _vli_rshift1(mod_m, ndigits); + mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1); + _vli_rshift1(mod_m + ndigits, ndigits); + } + vli_set(result, v[i], ndigits); +} + /* Computes p_result = p_product % curve_p. * See algorithm 5 and 6 from * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf diff --git a/ell/ecc-private.h b/ell/ecc-private.h index dcf676d9614a..de84bc64dc1b 100644 --- a/ell/ecc-private.h +++ b/ell/ecc-private.h @@ -86,6 +86,9 @@ void _vli_mod_add(uint64_t *result, const uint64_t *left, const uint64_t *right, void _vli_rshift1(uint64_t *vli, unsigned int ndigits); +void _vli_mmod_slow(uint64_t *result, const uint64_t *product, + const uint64_t *mod, unsigned int ndigits); + bool _vli_mmod_fast(uint64_t *result, const uint64_t *product, const uint64_t *curve_prime, unsigned int ndigits); From patchwork Thu Nov 9 14:20:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marcel Holtmann X-Patchwork-Id: 13451188 Received: from mail.holtmann.org (coyote.holtmann.net [212.227.132.17]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 8C6621E534 for ; Thu, 9 Nov 2023 14:21:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=holtmann.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=holtmann.org Authentication-Results: smtp.subspace.kernel.org; dkim=none Received: from fedora.. (p4fefc822.dip0.t-ipconnect.de [79.239.200.34]) by mail.holtmann.org (Postfix) with ESMTPSA id A7E8CCECE9 for ; Thu, 9 Nov 2023 15:20:58 +0100 (CET) From: Marcel Holtmann To: ell@lists.linux.dev Subject: [PATCH 3/3] ecc: Add helper for creating a scalar modulo curve order Date: Thu, 9 Nov 2023 15:20:56 +0100 Message-ID: <20231109142056.12385-3-marcel@holtmann.org> X-Mailer: git-send-email 2.41.0 Precedence: bulk X-Mailing-List: ell@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 The SPAKE2+ key exchange protocol requires the ability have a scalar modulo curve order. This adds a helper that allows to create a new scalar and run modulo curver order on it. This is similar to the helper that does the same with the curve prime value. --- ell/ecc.c | 35 +++++++++++++++++++++++++++++++++++ ell/ecc.h | 2 ++ ell/ell.sym | 1 + 3 files changed, 38 insertions(+) diff --git a/ell/ecc.c b/ell/ecc.c index ff147b84ed74..2124856dfe99 100644 --- a/ell/ecc.c +++ b/ell/ecc.c @@ -846,6 +846,41 @@ LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new_modp( return NULL; } +LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new_modn( + const struct l_ecc_curve *curve, + const void *bytes, size_t len) +{ + struct l_ecc_scalar *c; + uint64_t tmp[2 * L_ECC_MAX_DIGITS]; + unsigned int ndigits = len / 8; + + if (!bytes) + return NULL; + + if (len % 8) + return NULL; + + if (ndigits > curve->ndigits * 2) + return NULL; + + c = _ecc_constant_new(curve, NULL, 0); + if (!c) + return NULL; + + memset(tmp, 0, sizeof(tmp)); + _ecc_be2native(tmp, bytes, ndigits); + + _vli_mmod_slow(c->c, tmp, curve->n, curve->ndigits); + + if (!_vli_is_zero_or_one(c->c, curve->ndigits) && + secure_memcmp_64(curve->n, c->c, curve->ndigits) > 0) + return c; + + l_ecc_scalar_free(c); + + return NULL; +} + /* * Takes a buffer of the same size as the curve and scales it to a range * 1..n using value = (value mod (n - 1)) + 1. For the curves we support diff --git a/ell/ecc.h b/ell/ecc.h index de116f018b44..5a8cf0341acc 100644 --- a/ell/ecc.h +++ b/ell/ecc.h @@ -66,6 +66,8 @@ struct l_ecc_scalar *l_ecc_scalar_new_random( const struct l_ecc_curve *curve); struct l_ecc_scalar *l_ecc_scalar_new_modp(const struct l_ecc_curve *curve, const void *buf, size_t len); +struct l_ecc_scalar *l_ecc_scalar_new_modn(const struct l_ecc_curve *curve, + const void *buf, size_t len); struct l_ecc_scalar *l_ecc_scalar_new_reduced_1_to_n( const struct l_ecc_curve *curve, const void *buf, size_t len); diff --git a/ell/ell.sym b/ell/ell.sym index 0f593e1fc402..a887b2b09520 100644 --- a/ell/ell.sym +++ b/ell/ell.sym @@ -608,6 +608,7 @@ global: l_ecc_scalar_new; l_ecc_scalar_new_random; l_ecc_scalar_new_modp; + l_ecc_scalar_new_modn; l_ecc_scalar_new_reduced_1_to_n; l_ecc_scalar_sum_x; l_ecc_scalars_are_equal;