Added wNAF method
@@ -14,7 +14,7 @@ import heapq
from typing import List, Sequence, Tuple
from .alias import INFJ, Integer, JacPoint, Point
-from .curve import Curve, CurveGroup, _jac_from_aff, _mult_jac
+from .curve import Curve, CurveGroup, _jac_from_aff, _mult_jac, negate
from .curves import secp256k1
from .utils import int_from_integer
@@ -145,7 +145,7 @@ def mult_base_3(m: Integer, Q: Point = None, ec: Curve = secp256k1) -> Point:
def _mult_jac_fixed_window(m: int, w: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
"""Scalar multiplication of a curve point in Jacobian coordinates.
- This implementation uses the same method called "fixed window"
+ This implementation uses the method called "fixed window"
It is not constant time.
For about 256-bit scalars choose w=4 or w=5
The input point is assumed to be on curve,
@@ -196,3 +196,59 @@ def mult_fixed_window(m: Integer, w: Integer, Q: Point = None, ec: Curve = secp2
# Sliding window ??
+
+
+def mods(m: int, w: int) -> int:
+ w2 = pow(2, w) # cannot name it 2w
+ M = m % w2
+ if M >= (w2 / 2):
+ return M - w2
+ else:
+ return M
+
+
+def _mult_jac_w_NAF(m: int, w: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
+ """Scalar multiplication of a curve point in Jacobian coordinates.
+ This implementation uses the same method called "w-ary non-adjacent form" (wNAF)
+ Not always resistent against cache-timing attacks
+ The input point is assumed to be on curve,
+ m is assumed to have been reduced mod n if appropriate
+ (e.g. cyclic groups of order n).
+ """
+ if m < 0:
+ raise ValueError(f"negative m: {hex(m)}")
+
+ if Q == INFJ:
+ return Q
+
+ i = 0
+
+ p = []
+
+ while (m > 0):
+ if (m % 2) == 1:
+ p[i] = mods(m, w)
+ d = d - p[i]
+ else:
+ p[i] = 0
+ d = d / 2
+ i = i + 1
+
+ b = pow(2, w)
+
+ # The values of even points must be cancelled
+ T = []
+ T[0] = INFJ
+ for i in range(1, b - 1):
+ T[i] = ec._add_jac(T[i - 1], Q)
+ for i in range(1 - b, -1):
+ T[i] = negate(ec, T[-i])
+
+ R = INFJ
+
+ for j in range(i - 1, 0):
+ R = ec._add_jac(R, R)
+ if p[j] != 0:
+ R = ec._add_jac(R, T[p[j]])
+
+ return R
