Skip to contentSkip to conversation

ecc: add API's to support EAP-PWD

PATCH In review James Prestwood 2 participants 7 messages Jan 10, 2019

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/4 ecc: add API's to support EAP-PWD

EAP-PWD requires the following ECC functionality
- Point multiplication
- Point addition
- Point inverse
- Scalar addition

---
 ell/ecc.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 ell/ecc.h | 14 ++++++++++++++
 2 files changed, 67 insertions(+)
ell/ecc.c +53 -0
index c7043ef..8e8d2ac 100644
@@ -435,3 +435,56 @@ LIB_EXPORT void l_ecc_scalar_free(struct l_ecc_scalar *c)
 	memset(c->c, 0, c->curve->ndigits * 8);
 	l_free(c);
 }
+
+LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_order(
+						const struct l_ecc_curve *curve)
+{
+	return _ecc_constant_new(curve, (void *) curve->n, curve->ndigits * 8);
+}
+
+LIB_EXPORT bool l_ecc_scalar_add(struct l_ecc_scalar *ret,
+					const struct l_ecc_scalar *a,
+					const struct l_ecc_scalar *b,
+					const struct l_ecc_scalar *mod)
+{
+	if (unlikely(!ret || !a || !b || !mod))
+		return false;
+
+	_vli_mod_add(ret->c, a->c, b->c, mod->c, a->curve->ndigits);
+
+	return true;
+}
+
+LIB_EXPORT bool l_ecc_point_multiply(struct l_ecc_point *ret,
+					const struct l_ecc_scalar *scalar,
+					const struct l_ecc_point *point)
+{
+	if (unlikely(!ret || !scalar || !point))
+		return false;
+
+	_ecc_point_mult(ret, point, scalar->c, NULL, scalar->curve->p);
+
+	return true;
+}
+
+LIB_EXPORT bool l_ecc_point_add(struct l_ecc_point *ret,
+					const struct l_ecc_point *a,
+					const struct l_ecc_point *b)
+{
+	if (unlikely(!ret || !a || !b))
+		return false;
+
+	_ecc_point_add(ret, a, b, a->curve->p);
+
+	return true;
+}
+
+LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p)
+{
+	if (unlikely(!p))
+		return false;
+
+	_vli_mod_sub(p->y, p->curve->p, p->y, p->curve->p, p->curve->ndigits);
+
+	return true;
+}
ell/ecc.h +14 -0
index 569757f..1020724 100644
@@ -61,6 +61,20 @@ ssize_t l_ecc_scalar_get_data(const struct l_ecc_scalar *c, void *buf,
 					size_t len);
 void l_ecc_scalar_free(struct l_ecc_scalar *c);
 
+/* Constant operations */
+struct l_ecc_scalar *l_ecc_curve_get_order(const struct l_ecc_curve *curve);
+bool l_ecc_scalar_add(struct l_ecc_scalar *ret, const struct l_ecc_scalar *a,
+				const struct l_ecc_scalar *b,
+				const struct l_ecc_scalar *mod);
+
+/* Point operations */
+bool l_ecc_point_multiply(struct l_ecc_point *ret,
+				const struct l_ecc_scalar *scalar,
+				const struct l_ecc_point *point);
+bool l_ecc_point_add(struct l_ecc_point *ret, const struct l_ecc_point *a,
+				const struct l_ecc_point *b);
+bool l_ecc_point_inverse(struct l_ecc_point *p);
+
 #ifdef __cplusplus
 }
 #endif
Signature · 1 line
2.17.1
#1 lore raw

Hi James,

Quoted 10 lines · James Prestwood

EAP-PWD requires the following ECC functionality
- Point multiplication
- Point addition
- Point inverse
- Scalar addition

---
  ell/ecc.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
  ell/ecc.h | 14 ++++++++++++++
  2 files changed, 67 insertions(+)

<snip>

ell/ecc.c LIB_EXPORT void l_ecc_scalar_free(struct l_ecc_scalar *c) · line 442

Quoted 5 lines
ell/ecc.c +5 -0
+
+LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_order(
+						const struct l_ecc_curve *curve)
+{
+	return _ecc_constant_new(curve, (void *) curve->n, curve->ndigits * 8);

I took out this cast.

Review

Quoted 2 lines
(quoted diff) +2 -0
+}
+

Regards,
-Denis

#2 lore raw

PATCH v3 2/4 ecc: added API's to support SAE

In reply to James Prestwood

The functionality require was:
- Scalar multiplication
- Find a scalars legendre symbol
- Sum the curve equations X side
- Get prime from curve (needed for input to SAE KDF)
- Check if scalars/points are equal

---
 ell/ecc.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ell/ecc.h | 15 ++++++++++++++
 2 files changed, 75 insertions(+), 1 deletion(-)
ell/ecc.c +60 -1
index 8e8d2ac..61e839e 100644
@@ -160,7 +160,7 @@ void _ecc_native2be(uint64_t *dest, const uint64_t *native,
 }
 
 static void ecc_compute_y_sqr(const struct l_ecc_curve *curve,
-					uint64_t *y_sqr, uint64_t *x)
+					uint64_t *y_sqr, const uint64_t *x)
 {
 	uint64_t sum[L_ECC_MAX_DIGITS] = { 0 };
 	uint64_t tmp[L_ECC_MAX_DIGITS] = { 0 };
@@ -488,3 +488,62 @@ LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p)
 
 	return true;
 }
+
+LIB_EXPORT bool l_ecc_scalar_multiply(struct l_ecc_scalar *ret,
+					const struct l_ecc_scalar *a,
+					const struct l_ecc_scalar *b)
+{
+	if (unlikely(!ret || !a || !b))
+		return false;
+
+	_vli_mod_mult_fast(ret->c, a->c, b->c, a->curve->p, a->curve->ndigits);
+
+	return true;
+}
+
+LIB_EXPORT int l_ecc_scalar_legendre(struct l_ecc_scalar *value)
+{
+	if (unlikely(!value))
+		return -1;
+
+	return _vli_legendre(value->c, value->curve->p, value->curve->ndigits);
+}
+
+LIB_EXPORT bool l_ecc_scalar_sum_x(struct l_ecc_scalar *ret,
+					const struct l_ecc_scalar *x)
+{
+	if (unlikely(!ret || !x))
+		return false;
+
+	ecc_compute_y_sqr(x->curve, ret->c, x->c);
+
+	return true;
+}
+
+LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_prime(
+						const struct l_ecc_curve *curve)
+{
+	if (unlikely(!curve))
+		return NULL;
+
+	return _ecc_constant_new(curve, (void *) curve->p, curve->ndigits * 8);
+}
+
+LIB_EXPORT bool l_ecc_scalars_are_equal(const struct l_ecc_scalar *a,
+						const struct l_ecc_scalar *b)
+{
+	if (unlikely(!a || !b))
+		return false;
+
+	return (memcmp(a->c, b->c, a->curve->ndigits * 8) == 0);
+}
+
+LIB_EXPORT bool l_ecc_points_are_equal(const struct l_ecc_point *a,
+						const struct l_ecc_point *b)
+{
+	if (unlikely(!a || !b))
+		return false;
+
+	return ((memcmp(a->x, b->x, a->curve->ndigits * 8) == 0) &&
+			(memcmp(a->y, b->y, a->curve->ndigits * 8) == 0));
+}
ell/ecc.h +15 -0
index 1020724..9a852ff 100644
@@ -75,6 +75,21 @@ bool l_ecc_point_add(struct l_ecc_point *ret, const struct l_ecc_point *a,
 				const struct l_ecc_point *b);
 bool l_ecc_point_inverse(struct l_ecc_point *p);
 
+/* extra operations needed for SAE */
+bool l_ecc_scalar_multiply(struct l_ecc_scalar *ret,
+				const struct l_ecc_scalar *a,
+				const struct l_ecc_scalar *b);
+int l_ecc_scalar_legendre(struct l_ecc_scalar *value);
+bool l_ecc_scalar_sum_x(struct l_ecc_scalar *ret, const struct l_ecc_scalar *x);
+
+struct l_ecc_scalar *l_ecc_curve_get_prime(const struct l_ecc_curve *curve);
+
+bool l_ecc_scalars_are_equal(const struct l_ecc_scalar *a,
+				const struct l_ecc_scalar *b);
+
+bool l_ecc_points_are_equal(const struct l_ecc_point *a,
+				const struct l_ecc_point *b);
+
 #ifdef __cplusplus
 }
 #endif
Signature · 1 line
2.17.1
#3 lore raw

Re: [PATCH v3 2/4] ecc: added API's to support SAE

Hi James,

Quoted 11 lines · James Prestwood

The functionality require was:
- Scalar multiplication
- Find a scalars legendre symbol
- Sum the curve equations X side
- Get prime from curve (needed for input to SAE KDF)
- Check if scalars/points are equal

---
  ell/ecc.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
  ell/ecc.h | 15 ++++++++++++++
  2 files changed, 75 insertions(+), 1 deletion(-)

<snip>

ell/ecc.c LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p) · line 529

Quoted 7 lines
ell/ecc.c +7 -0
+LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_prime(
+						const struct l_ecc_curve *curve)
+{
+	if (unlikely(!curve))
+		return NULL;
+
+	return _ecc_constant_new(curve, (void *) curve->p, curve->ndigits * 8);

I took out this cast and applied this patch.

Review

Quoted 2 lines
(quoted diff) +2 -0
+}
+

Regards,
-Denis

#4 lore raw

PATCH v3 3/4 ecc: moved point add, exp, and legendre into ecc.c

In reply to James Prestwood

_ecc_point_add, _vli_mod_exp, and _vli_legendre were all written in house, in addition to the ecc code taken from the kernel. Inside IWD it was much more convenient to just bundle these into the same file. Now (in ELL), since we have ecc-private.h, its much easier to keep these separate and out of ecc-external.c.

---
 ell/ecc-external.c | 123 +++++++--------------------------------------
 ell/ecc-private.h  |   4 ++
 ell/ecc.c          |  90 +++++++++++++++++++++++++++++++++
 3 files changed, 111 insertions(+), 106 deletions(-)
ell/ecc-external.c +17 -106
index 0cdb198..71b3e68 100644
@@ -180,7 +180,7 @@ static uint64_t vli_add(uint64_t *result, const uint64_t *left,
 }
 
 /* Computes result = left - right, returning borrow. Can modify in place. */
-static uint64_t vli_sub(uint64_t *result, const uint64_t *left,
+uint64_t _vli_sub(uint64_t *result, const uint64_t *left,
 							const uint64_t *right,
 							unsigned int ndigits)
 {
@@ -327,7 +327,7 @@ void _vli_mod_add(uint64_t *result, const uint64_t *left,
 	 * get remainder.
 	 */
 	if (carry || _vli_cmp(result, mod, ndigits) >= 0)
-		vli_sub(result, result, mod, ndigits);
+		_vli_sub(result, result, mod, ndigits);
 }
 
 /* Computes result = (left - right) % mod.
@@ -337,7 +337,7 @@ void _vli_mod_sub(uint64_t *result, const uint64_t *left,
 				const uint64_t *right, const uint64_t *mod,
 				unsigned int ndigits)
 {
-	uint64_t borrow = vli_sub(result, left, right, ndigits);
+	uint64_t borrow = _vli_sub(result, left, right, ndigits);
 
 	/* In this case, p_result == -diff == (max int) - diff.
 	 * Since -x % d == d - x, we can get the correct result from
@@ -372,7 +372,7 @@ static void vli_mmod_fast_192(uint64_t *result, const uint64_t *product,
 	carry += vli_add(result, result, tmp, ndigits);
 
 	while (carry || _vli_cmp(curve_prime, result, ndigits) != 1)
-		carry -= vli_sub(result, result, curve_prime, ndigits);
+		carry -= _vli_sub(result, result, curve_prime, ndigits);
 }
 
 /* Computes result = product % curve_prime
@@ -421,28 +421,28 @@ static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product,
 	tmp[1] = (product[6] >> 32);
 	tmp[2] = 0;
 	tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32);
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	/* d2 */
 	tmp[0] = product[6];
 	tmp[1] = product[7];
 	tmp[2] = 0;
 	tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull);
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	/* d3 */
 	tmp[0] = (product[6] >> 32) | (product[7] << 32);
 	tmp[1] = (product[7] >> 32) | (product[4] << 32);
 	tmp[2] = (product[4] >> 32) | (product[5] << 32);
 	tmp[3] = (product[6] << 32);
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	/* d4 */
 	tmp[0] = product[7];
 	tmp[1] = product[4] & 0xffffffff00000000ull;
 	tmp[2] = product[5];
 	tmp[3] = product[6] & 0xffffffff00000000ull;
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	if (carry < 0) {
 		do {
@@ -450,7 +450,7 @@ static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product,
 		} while (carry < 0);
 	} else {
 		while (carry || _vli_cmp(curve_prime, result, ndigits) != 1)
-			carry -= vli_sub(result, result, curve_prime, ndigits);
+			carry -= _vli_sub(result, result, curve_prime, ndigits);
 	}
 }
 
@@ -550,7 +550,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product,
 	tmp[3] = ECC_SET_S(product, 18, 17);
 	tmp[4] = ECC_SET_S(product, 20, 19);
 	tmp[5] = ECC_SET_S(product, 22, 21);
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	/* s8 */
 	tmp[0] = ECC_SET_S(product, 20, -1);
@@ -559,7 +559,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product,
 	tmp[3] = 0;
 	tmp[4] = 0;
 	tmp[5] = 0;
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	/* s9 */
 	tmp[0] = 0;
@@ -568,7 +568,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product,
 	tmp[3] = 0;
 	tmp[4] = 0;
 	tmp[5] = 0;
-	carry -= vli_sub(result, result, tmp, ndigits);
+	carry -= _vli_sub(result, result, tmp, ndigits);
 
 	if (carry < 0) {
 		do {
@@ -576,7 +576,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product,
 		} while (carry < 0);
 	} else {
 		while (carry || _vli_cmp(curve_prime, result, ndigits) != 1)
-			carry -= vli_sub(result, result, curve_prime, ndigits);
+			carry -= _vli_sub(result, result, curve_prime, ndigits);
 	}
 }
 
@@ -675,13 +675,13 @@ void _vli_mod_inv(uint64_t *result, const uint64_t *input,
 			if (carry)
 				v[ndigits - 1] |= 0x8000000000000000ull;
 		} else if (cmp_result > 0) {
-			vli_sub(a, a, b, ndigits);
+			_vli_sub(a, a, b, ndigits);
 			_vli_rshift1(a, ndigits);
 
 			if (_vli_cmp(u, v, ndigits) < 0)
 				vli_add(u, u, mod, ndigits);
 
-			vli_sub(u, u, v, ndigits);
+			_vli_sub(u, u, v, ndigits);
 			if (!EVEN(u))
 				carry = vli_add(u, u, mod, ndigits);
 
@@ -689,13 +689,13 @@ void _vli_mod_inv(uint64_t *result, const uint64_t *input,
 			if (carry)
 				u[ndigits - 1] |= 0x8000000000000000ull;
 		} else {
-			vli_sub(b, b, a, ndigits);
+			_vli_sub(b, b, a, ndigits);
 			_vli_rshift1(b, ndigits);
 
 			if (_vli_cmp(v, u, ndigits) < 0)
 				vli_add(v, v, mod, ndigits);
 
-			vli_sub(v, v, u, ndigits);
+			_vli_sub(v, v, u, ndigits);
 			if (!EVEN(v))
 				carry = vli_add(v, v, mod, ndigits);
 
@@ -972,92 +972,3 @@ bool _ecc_point_is_zero(const struct l_ecc_point *point)
 	return (vli_is_zero(point->x, point->curve->ndigits) &&
 		vli_is_zero(point->y, point->curve->ndigits));
 }
-
-/* (rx, ry) = (px, py) + (qx, qy) */
-void _ecc_point_add(struct l_ecc_point *ret, const struct l_ecc_point *p,
-			const struct l_ecc_point *q,
-			const uint64_t *curve_prime)
-{
-	/*
-	* s = (py - qy)/(px - qx)
-	*
-	* rx = s^2 - px - qx
-	* ry = s(px - rx) - py
-	*/
-	uint64_t s[L_ECC_MAX_DIGITS];
-	uint64_t kp1[L_ECC_MAX_DIGITS];
-	uint64_t kp2[L_ECC_MAX_DIGITS];
-	uint64_t resx[L_ECC_MAX_DIGITS];
-	uint64_t resy[L_ECC_MAX_DIGITS];
-	unsigned int ndigits = p->curve->ndigits;
-
-	vli_clear(s, ndigits);
-
-	/* kp1 = py - qy */
-	_vli_mod_sub(kp1, q->y, p->y, curve_prime, ndigits);
-	/* kp2 = px - qx */
-	_vli_mod_sub(kp2, q->x, p->x, curve_prime, ndigits);
-	/* s = kp1/kp2 */
-	_vli_mod_inv(kp2, kp2, curve_prime, ndigits);
-	_vli_mod_mult_fast(s, kp1, kp2, curve_prime, ndigits);
-	/* rx = s^2 - px - qx */
-	_vli_mod_mult_fast(kp1, s, s, curve_prime, ndigits);
-	_vli_mod_sub(kp1, kp1, p->x, curve_prime, ndigits);
-	_vli_mod_sub(resx, kp1, q->x, curve_prime, ndigits);
-	/* ry = s(px - rx) - py */
-	_vli_mod_sub(kp1, p->x, resx, curve_prime, ndigits);
-	_vli_mod_mult_fast(kp1, s, kp1, curve_prime, ndigits);
-	_vli_mod_sub(resy, kp1, p->y, curve_prime, ndigits);
-
-	vli_set(ret->x, resx, ndigits);
-	vli_set(ret->y, resy, ndigits);
-}
-
-/* result = (base ^ exp) % p */
-void _vli_mod_exp(uint64_t *result, uint64_t *base, uint64_t *exp,
-			const uint64_t *mod, unsigned int ndigits)
-{
-	unsigned int i;
-	int bit;
-	uint64_t n[L_ECC_MAX_DIGITS];
-	uint64_t r[L_ECC_MAX_DIGITS] = { 1 };
-
-	vli_set(n, base, ndigits);
-
-	for (i = 0; i < ndigits; i++) {
-		for (bit = 0; bit < 64; bit++) {
-			uint64_t tmp[L_ECC_MAX_DIGITS];
-
-			if (exp[i] & (1ull << bit)) {
-				_vli_mod_mult_fast(tmp, r, n, mod, ndigits);
-				vli_set(r, tmp, ndigits);
-			}
-
-			_vli_mod_mult_fast(tmp, n, n, mod, ndigits);
-			vli_set(n, tmp, ndigits);
-		}
-	}
-
-	vli_set(result, r, ndigits);
-}
-
-int _vli_legendre(uint64_t *val, const uint64_t *p, unsigned int ndigits)
-{
-	uint64_t tmp[L_ECC_MAX_DIGITS];
-	uint64_t exp[L_ECC_MAX_DIGITS];
-	uint64_t _1[L_ECC_MAX_DIGITS] = { 1ull };
-	uint64_t _0[L_ECC_MAX_DIGITS] = { 0 };
-
-	/* check that val ^ ((p - 1) / 2) == [1, 0 or -1] */
-
-	vli_sub(exp, p, _1, ndigits);
-	_vli_rshift1(exp, ndigits);
-	_vli_mod_exp(tmp, val, exp, p, ndigits);
-
-	if (_vli_cmp(tmp, _1, ndigits) == 0)
-		return 1;
-	else if (_vli_cmp(tmp, _0, ndigits) == 0)
-		return 0;
-	else
-		return -1;
-}
ell/ecc-private.h +4 -0
index 0d8a444..3863620 100644
@@ -75,6 +75,10 @@ void _vli_mod_exp(uint64_t *result, uint64_t *base, uint64_t *exp,
 
 int _vli_cmp(const uint64_t *left, const uint64_t *right, unsigned int ndigits);
 
+uint64_t _vli_sub(uint64_t *result, const uint64_t *left,
+							const uint64_t *right,
+							unsigned int ndigits);
+
 int _vli_legendre(uint64_t *val, const uint64_t *p, unsigned int ndigits);
 
 bool _ecc_point_is_zero(const struct l_ecc_point *point);
ell/ecc.c +90 -0

96 lines not on this page · raw message

Signature · 1 line
2.17.1
#5 lore raw

Re: [PATCH v3 3/4] ecc: moved point add, exp, and legendre into ecc.c

Hi James,

Quoted 11 lines · James Prestwood

_ecc_point_add, _vli_mod_exp, and _vli_legendre were all written in house, in addition to the ecc code taken from the kernel. Inside IWD it was much more convenient to just bundle these into the same file. Now (in ELL), since we have ecc-private.h, its much easier to keep these separate and out of ecc-external.c.

---
  ell/ecc-external.c | 123 +++++++--------------------------------------
  ell/ecc-private.h  |   4 ++
  ell/ecc.c          |  90 +++++++++++++++++++++++++++++++++
  3 files changed, 111 insertions(+), 106 deletions(-)

Patch 3 & 4 applied, thanks.

Regards,
-Denis

#6 lore raw

PATCH v3 4/4 ecc: Updated _ecc_point_mult to match kernel

In reply to James Prestwood

Commit 3da2c1dfdb802b184eea0653d1e589515b52d74b was added to the kernel which addressed potential timing attacks. This updates our ecc code with the same fix. It was slightly modified to not change the internal API parameters (we can get the curve from the point, rather than passing in the curve structure).

---
 ell/ecc-external.c | 43 ++++++++++---------------------------------
 1 file changed, 10 insertions(+), 33 deletions(-)
ell/ecc-external.c +10 -33
index 71b3e68..1c118c2 100644
@@ -68,37 +68,6 @@ static uint64_t vli_test_bit(const uint64_t *vli, unsigned int bit)
 	return (vli[bit / 64] & ((uint64_t) 1 << (bit % 64)));
 }
 
-/* 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);
-}
-
 /* Sets dest = src. */
 static void vli_set(uint64_t *dest, const uint64_t *src, unsigned int ndigits)
 {
@@ -916,12 +885,20 @@ void _ecc_point_mult(struct l_ecc_point *result,
 			uint64_t *initial_z, const uint64_t *curve_prime)
 {
 	/* R0 and R1 */
+	const struct l_ecc_curve *curve = point->curve;
 	uint64_t rx[2][L_ECC_MAX_DIGITS];
 	uint64_t ry[2][L_ECC_MAX_DIGITS];
 	uint64_t z[L_ECC_MAX_DIGITS];
+	uint64_t sk[2][L_ECC_MAX_DIGITS];
 	int i, nb;
-	unsigned int ndigits = point->curve->ndigits;
-	int num_bits = vli_num_bits(scalar, ndigits);
+	unsigned int ndigits = curve->ndigits;
+	int num_bits;
+	int carry;
+
+	carry = vli_add(sk[0], scalar, curve->n, ndigits);
+	vli_add(sk[1], sk[0], curve->n, ndigits);
+	scalar = sk[!carry];
+	num_bits = sizeof(uint64_t) * ndigits * 8 + 1;
 
 	vli_set(rx[1], point->x, ndigits);
 	vli_set(ry[1], point->y, ndigits);
Signature · 1 line
2.17.1