Add sliding window multiplier.

7 files changed, 117 insertions, 57 deletions

diff --git a/pyecsca/ec/configuration.py b/pyecsca/ec/configuration.py
index 4d13c01..0e3b338 100644
--- a/pyecsca/ec/configuration.py
+++ b/pyecsca/ec/configuration.py
@@ -142,12 +142,12 @@ def all_configurations(**kwargs) -> Generator[Configuration, Configuration, None
 
     def leaf_subclasses(cls):
         subs = cls.__subclasses__()
-        result = []
+        result = set()
         for subclass in subs:
             if subclass.__subclasses__():
-                result.extend(leaf_subclasses(subclass))
+                result.update(leaf_subclasses(subclass))
             else:
-                result.append(subclass)
+                result.add(subclass)
         return result
 
     def independents(kwargs):
diff --git a/pyecsca/ec/mult/base.py b/pyecsca/ec/mult/base.py
index 027320c..a0584d1 100644
--- a/pyecsca/ec/mult/base.py
+++ b/pyecsca/ec/mult/base.py
@@ -206,3 +206,24 @@ class ScalarMultiplier(ABC):
         :return: The resulting multiple.
         """
         raise NotImplementedError
+
+
+@public
+class AccumulatorMultiplier(ScalarMultiplier, ABC):
+    """
+    A scalar multiplication algorithm mix-in class for a multiplier that accumulates.
+
+    :param accumulation_order: The order of accumulation of points.
+    """
+    accumulation_order: AccumulationOrder
+
+    def __init__(self, *args, accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, **kwargs):
+        super().__init__(*args, **kwargs)
+        self.accumulation_order = accumulation_order
+
+    def _accumulate(self, p: Point, r: Point) -> Point:
+        if self.accumulation_order is AccumulationOrder.PeqPR:
+            p = self._add(p, r)
+        elif self.accumulation_order is AccumulationOrder.PeqRP:
+            p = self._add(r, p)
+        return p
diff --git a/pyecsca/ec/mult/binary.py b/pyecsca/ec/mult/binary.py
index dda3388..6145828 100644
--- a/pyecsca/ec/mult/binary.py
+++ b/pyecsca/ec/mult/binary.py
@@ -4,7 +4,8 @@ from typing import Optional
 
 from public import public
 
-from .base import ScalarMultiplier, ProcessingDirection, AccumulationOrder, ScalarMultiplicationAction
+from .base import ScalarMultiplier, ProcessingDirection, AccumulationOrder, ScalarMultiplicationAction, \
+    AccumulatorMultiplier
 from ..formula import (
     AdditionFormula,
     DoublingFormula,
@@ -14,7 +15,7 @@ from ..point import Point
 
 
 @public
-class DoubleAndAddMultiplier(ScalarMultiplier, ABC):
+class DoubleAndAddMultiplier(AccumulatorMultiplier, ScalarMultiplier, ABC):
     """
     Classic double and add scalar multiplication algorithm.
 
@@ -27,7 +28,6 @@ class DoubleAndAddMultiplier(ScalarMultiplier, ABC):
     optionals = {ScalingFormula}
     always: bool
     direction: ProcessingDirection
-    accumulation_order: AccumulationOrder
     complete: bool
 
     def __init__(
@@ -41,10 +41,9 @@ class DoubleAndAddMultiplier(ScalarMultiplier, ABC):
             complete: bool = True,
             short_circuit: bool = True,
     ):
-        super().__init__(short_circuit=short_circuit, add=add, dbl=dbl, scl=scl)
+        super().__init__(short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, scl=scl)
         self.always = always
         self.direction = direction
-        self.accumulation_order = accumulation_order
         self.complete = complete
 
     def __hash__(self):
@@ -58,13 +57,6 @@ class DoubleAndAddMultiplier(ScalarMultiplier, ABC):
     def __repr__(self):
         return f"{self.__class__.__name__}({tuple(self.formulas.values())}, short_circuit={self.short_circuit}, accumulation_order={self.accumulation_order}, always={self.always}, complete={self.complete})"
 
-    def _accumulate(self, p: Point, r: Point) -> Point:
-        if self.accumulation_order is AccumulationOrder.PeqPR:
-            p = self._add(p, r)
-        elif self.accumulation_order is AccumulationOrder.PeqRP:
-            p = self._add(r, p)
-        return p
-
     def _ltr(self, scalar: int) -> Point:
         if self.complete:
             q = self._point
diff --git a/pyecsca/ec/mult/naf.py b/pyecsca/ec/mult/naf.py
index b3409db..1cec8b0 100644
--- a/pyecsca/ec/mult/naf.py
+++ b/pyecsca/ec/mult/naf.py
@@ -2,7 +2,8 @@ from copy import copy
 from typing import Optional, List, MutableMapping
 from public import public
 
-from .base import ScalarMultiplier, ScalarMultiplicationAction, ProcessingDirection, AccumulationOrder, PrecomputationAction
+from .base import ScalarMultiplier, ScalarMultiplicationAction, ProcessingDirection, AccumulationOrder, \
+    PrecomputationAction, AccumulatorMultiplier
 from ..formula import (
     AdditionFormula,
     DoublingFormula,
@@ -15,13 +16,12 @@ from ..scalar import naf, wnaf
 
 
 @public
-class BinaryNAFMultiplier(ScalarMultiplier):
+class BinaryNAFMultiplier(AccumulatorMultiplier, ScalarMultiplier):
     """Binary NAF (Non Adjacent Form) multiplier."""
 
     requires = {AdditionFormula, DoublingFormula, NegationFormula}
     optionals = {ScalingFormula}
     direction: ProcessingDirection
-    accumulation_order: AccumulationOrder
     _point_neg: Point
 
     def __init__(
@@ -35,10 +35,9 @@ class BinaryNAFMultiplier(ScalarMultiplier):
             short_circuit: bool = True,
     ):
         super().__init__(
-            short_circuit=short_circuit, add=add, dbl=dbl, neg=neg, scl=scl
+            short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, neg=neg, scl=scl
         )
         self.direction = direction
-        self.accumulation_order = accumulation_order
 
     def __hash__(self):
         return id(self)
@@ -53,13 +52,6 @@ class BinaryNAFMultiplier(ScalarMultiplier):
             super().init(params, point)
             self._point_neg = self._neg(point)
 
-    def _accumulate(self, p: Point, r: Point) -> Point:
-        if self.accumulation_order is AccumulationOrder.PeqPR:
-            p = self._add(p, r)
-        elif self.accumulation_order is AccumulationOrder.PeqRP:
-            p = self._add(r, p)
-        return p
-
     def _ltr(self, scalar_naf: List[int]) -> Point:
         q = copy(self._params.curve.neutral)
         for val in scalar_naf:
@@ -100,14 +92,13 @@ class BinaryNAFMultiplier(ScalarMultiplier):
 
 
 @public
-class WindowNAFMultiplier(ScalarMultiplier):
+class WindowNAFMultiplier(AccumulatorMultiplier, ScalarMultiplier):
     """Window NAF (Non Adjacent Form) multiplier, left-to-right."""
 
     requires = {AdditionFormula, DoublingFormula, NegationFormula}
     optionals = {ScalingFormula}
     _points: MutableMapping[int, Point]
     _points_neg: MutableMapping[int, Point]
-    accumulation_order: AccumulationOrder
     precompute_negation: bool = False
     width: int
 
@@ -123,10 +114,9 @@ class WindowNAFMultiplier(ScalarMultiplier):
             short_circuit: bool = True,
     ):
         super().__init__(
-            short_circuit=short_circuit, add=add, dbl=dbl, neg=neg, scl=scl
+            short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, neg=neg, scl=scl
         )
         self.width = width
-        self.accumulation_order = accumulation_order
         self.precompute_negation = precompute_negation
 
     def __hash__(self):
@@ -135,7 +125,7 @@ class WindowNAFMultiplier(ScalarMultiplier):
     def __eq__(self, other):
         if not isinstance(other, WindowNAFMultiplier):
             return False
-        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.width == other.width and self.precompute_negation == other.precompute_negation
+        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.width == other.width and self.precompute_negation == other.precompute_negation and self.accumulation_order == other.accumulation_order
 
     def init(self, params: DomainParameters, point: Point):
         with PrecomputationAction(params, point):
@@ -150,13 +140,6 @@ class WindowNAFMultiplier(ScalarMultiplier):
                     self._points_neg[2 * i + 1] = self._neg(current_point)
                 current_point = self._add(current_point, double_point)
 
-    def _accumulate(self, p: Point, r: Point) -> Point:
-        if self.accumulation_order is AccumulationOrder.PeqPR:
-            p = self._add(p, r)
-        elif self.accumulation_order is AccumulationOrder.PeqRP:
-            p = self._add(r, p)
-        return p
-
     def multiply(self, scalar: int) -> Point:
         if not self._initialized:
             raise ValueError("ScalarMultiplier not initialized.")
diff --git a/pyecsca/ec/mult/window.py b/pyecsca/ec/mult/window.py
index f2c2c70..15126a7 100644
--- a/pyecsca/ec/mult/window.py
+++ b/pyecsca/ec/mult/window.py
@@ -3,25 +3,90 @@ from typing import Optional, MutableMapping
 from public import public
 
 from ..params import DomainParameters
-from .base import ScalarMultiplier, AccumulationOrder, ScalarMultiplicationAction, PrecomputationAction
+from .base import ScalarMultiplier, AccumulationOrder, ScalarMultiplicationAction, PrecomputationAction, \
+    ProcessingDirection, AccumulatorMultiplier
 from ..formula import (
     AdditionFormula,
     DoublingFormula,
     ScalingFormula,
 )
 from ..point import Point
-from ..scalar import convert_base
+from ..scalar import convert_base, sliding_window_rtl, sliding_window_ltr
 
 
 @public
-class FixedWindowLTRMultiplier(ScalarMultiplier):
+class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier):
+    """"""
+
+    requires = {AdditionFormula, DoublingFormula}
+    optionals = {ScalingFormula}
+    complete: bool
+    width: int
+    recoding_direction: ProcessingDirection
+    _points: MutableMapping[int, Point]
+
+    def __init__(
+            self,
+            add: AdditionFormula,
+            dbl: DoublingFormula,
+            width: int,
+            scl: Optional[ScalingFormula] = None,
+            recoding_direction: ProcessingDirection = ProcessingDirection.LTR,
+            accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
+            short_circuit: bool = True,
+    ):
+        super().__init__(
+            short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, scl=scl
+        )
+        self.width = width
+        self.recoding_direction = recoding_direction
+
+    def __hash__(self):
+        return id(self)
+
+    def __eq__(self, other):
+        if not isinstance(other, SlidingWindowMultiplier):
+            return False
+        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.width == other.width and self.recoding_direction == other.recoding_direction and self.accumulation_order == other.accumulation_order
+
+    def init(self, params: DomainParameters, point: Point):
+        with PrecomputationAction(params, point):
+            super().init(params, point)
+            self._points = {}
+            current_point = point
+            double_point = self._dbl(point)
+            for i in range(0, 2 ** (self.width - 1)):
+                self._points[2 * i + 1] = current_point
+                current_point = self._add(current_point, double_point)
+
+    def multiply(self, scalar: int) -> Point:
+        if not self._initialized:
+            raise ValueError("ScalarMultiplier not initialized.")
+        with ScalarMultiplicationAction(self._point, scalar) as action:
+            if scalar == 0:
+                return action.exit(copy(self._params.curve.neutral))
+            if self.recoding_direction is ProcessingDirection.LTR:
+                scalar_sliding = sliding_window_ltr(scalar, self.width)
+            elif self.recoding_direction is ProcessingDirection.RTL:
+                scalar_sliding = sliding_window_rtl(scalar, self.width)
+            q = copy(self._params.curve.neutral)
+            for val in scalar_sliding:
+                q = self._dbl(q)
+                if val != 0:
+                    q = self._accumulate(q, self._points[val])
+            if "scl" in self.formulas:
+                q = self._scl(q)
+            return action.exit(q)
+
+
+@public
+class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier):
     """Like LTRMultiplier, but not binary, but m-ary."""
 
     requires = {AdditionFormula, DoublingFormula}
     optionals = {ScalingFormula}
     complete: bool
     m: int
-    accumulation_order: AccumulationOrder
     _points: MutableMapping[int, Point]
 
     def __init__(
@@ -34,7 +99,7 @@ class FixedWindowLTRMultiplier(ScalarMultiplier):
             short_circuit: bool = True,
     ):
         super().__init__(
-            short_circuit=short_circuit, add=add, dbl=dbl, scl=scl
+            short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, scl=scl
         )
         if m < 2:
             raise ValueError("Invalid base.")
@@ -47,7 +112,7 @@ class FixedWindowLTRMultiplier(ScalarMultiplier):
     def __eq__(self, other):
         if not isinstance(other, FixedWindowLTRMultiplier):
             return False
-        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.m == other.m
+        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.m == other.m and self.accumulation_order == other.accumulation_order
 
     def init(self, params: DomainParameters, point: Point):
         with PrecomputationAction(params, point):
@@ -74,13 +139,6 @@ class FixedWindowLTRMultiplier(ScalarMultiplier):
                 q = self._accumulate(q, r)
         return q
 
-    def _accumulate(self, p: Point, r: Point) -> Point:
-        if self.accumulation_order is AccumulationOrder.PeqPR:
-            p = self._add(p, r)
-        elif self.accumulation_order is AccumulationOrder.PeqRP:
-            p = self._add(r, p)
-        return p
-
     def multiply(self, scalar: int) -> Point:
         if not self._initialized:
             raise ValueError("ScalarMultiplier not initialized.")
diff --git a/test/ec/test_configuration.py b/test/ec/test_configuration.py
index bfb6463..4e2e4ca 100644
--- a/test/ec/test_configuration.py
+++ b/test/ec/test_configuration.py
@@ -30,7 +30,8 @@ def test_weierstrass_projective(base_independents):
     model = ShortWeierstrassModel()
     coords = model.coordinates["projective"]
     configs = list(all_configurations(model=model, coords=coords, **base_independents))
-    assert len(configs) == 4900
+    assert len(set(map(lambda cfg: cfg.scalarmult, configs))) == len(configs)
+    assert len(configs) == 6020
 
 
 def test_mult_class(base_independents):
@@ -38,6 +39,7 @@ def test_mult_class(base_independents):
     coords = model.coordinates["projective"]
     scalarmult = LTRMultiplier
     configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult, **base_independents))
+    assert len(set(map(lambda cfg: cfg.scalarmult, configs))) == len(configs)
     assert len(configs) == 1120
 
 
diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py
index 519e34c..2a17867 100644
--- a/test/ec/test_mult.py
+++ b/test/ec/test_mult.py
@@ -15,7 +15,7 @@ from pyecsca.ec.mult import (
     CoronMultiplier,
     FixedWindowLTRMultiplier,
     ProcessingDirection,
-    AccumulationOrder, ScalarMultiplier
+    AccumulationOrder, ScalarMultiplier, SlidingWindowMultiplier
 )
 from pyecsca.ec.point import InfinityPoint, Point
 from .utils import cartesian
@@ -292,10 +292,15 @@ def test_basic_multipliers(secp128r1, num, add, dbl):
     wnafs = [WindowNAFMultiplier(add, dbl, neg, scl=scale, **dict(zip(wnaf_options.keys(), combination))) for combination in product(*wnaf_options.values())]
     ladder_options = {"complete": (True, False)}
     ladders = [SimpleLadderMultiplier(add, dbl, scale, **dict(zip(ladder_options.keys(), combination))) for combination in product(*ladder_options.values())]
-    fixed_options = {"m": (5, 8), "accumulation_order": tuple(AccumulationOrder)}
+    fixed_options = {"m": (5, 8),
+                     "accumulation_order": tuple(AccumulationOrder)}
     fixeds = [FixedWindowLTRMultiplier(add, dbl, scl=scale, **dict(zip(fixed_options.keys(), combination))) for combination in product(*fixed_options.values())]
+    sliding_options = {"width": (3, 5),
+                       "recoding_direction": tuple(ProcessingDirection),
+                       "accumulation_order": tuple(AccumulationOrder)}
+    slides = [SlidingWindowMultiplier(add, dbl, scl=scale, **dict(zip(sliding_options.keys(), combination))) for combination in product(*sliding_options.values())]
 
-    mults: Sequence[ScalarMultiplier] = ltrs + rtls + bnafs + wnafs + [CoronMultiplier(add, dbl, scale)] + ladders + fixeds
+    mults: Sequence[ScalarMultiplier] = ltrs + rtls + bnafs + wnafs + [CoronMultiplier(add, dbl, scale)] + ladders + fixeds + slides
     results = []
     for mult in mults:
         mult.init(secp128r1, secp128r1.generator)
@@ -303,7 +308,6 @@ def test_basic_multipliers(secp128r1, num, add, dbl):
         if results:
             assert res == results[-1], f"Points not equal {res} != {results[-1]} for mult = {mult}"
         results.append(res)
-    print(len(results))
 
 
 def test_init_fail(curve25519, secp128r1):