[2/3] ecc: Introduce _vli_mmod_slow that works with curve_p and curve_n

Commit Message

Marcel Holtmann Nov. 9, 2023, 2:20 p.m. UTC

---
 ell/ecc-external.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++
 ell/ecc-private.h  |  3 ++
 2 files changed, 78 insertions(+)

Patch

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);