Further unify and specify scalarmults.

6 files changed, 231 insertions, 78 deletions

diff --git a/pyecsca/ec/configuration.py b/pyecsca/ec/configuration.py
index 79b7f4c..4d13c01 100644
--- a/pyecsca/ec/configuration.py
+++ b/pyecsca/ec/configuration.py
@@ -1,4 +1,5 @@
 """Provides a way to work with and enumerate implementation configurations."""
+import warnings
 from dataclasses import dataclass
 from enum import Enum
 from itertools import product
@@ -9,7 +10,6 @@ from typing import (
     get_args,
     Generator,
     FrozenSet,
-    Any,
 )
 
 from public import public
@@ -200,13 +200,26 @@ def all_configurations(**kwargs) -> Generator[Configuration, Configuration, None
                     required_type, bool
                 ):
                     options = [True, False]
+                elif get_origin(required_type) is None and issubclass(
+                        required_type, Enum
+                ):
+                    options = list(required_type)
                 elif (
                     get_origin(required_type) is None
                     and issubclass(required_type, int)
                     and name == "width"
                 ):
+                    # TODO: More options possible!
                     options = [3, 5]
+                elif (
+                    get_origin(required_type) is None
+                    and issubclass(required_type, int)
+                    and name == "m"
+                ):
+                    # TODO: More options possible!
+                    options = [5, 8]
                 else:
+                    warnings.warn(RuntimeWarning(f"Unknown scalarmult option range = {name}"))
                     options = []
                 arg_options[name] = options
             keys = arg_options.keys()
diff --git a/pyecsca/ec/mult.py b/pyecsca/ec/mult.py
index f68152e..45d2b38 100644
--- a/pyecsca/ec/mult.py
+++ b/pyecsca/ec/mult.py
@@ -1,7 +1,8 @@
 """Provides several classes implementing different scalar multiplication algorithms."""
 from abc import ABC, abstractmethod
 from copy import copy
-from typing import Mapping, Tuple, Optional, MutableMapping, ClassVar, Set, Type
+from enum import Enum, auto
+from typing import Mapping, Tuple, Optional, MutableMapping, ClassVar, Set, Type, List
 from math import log2
 
 from public import public
@@ -22,6 +23,20 @@ from .point import Point
 
 
 @public
+class ProcessingDirection(Enum):
+    """Scalar processing direction."""
+    LTR = "Left-to-right"
+    RTL = "Right-to-left"
+
+
+@public
+class AccumulationOrder(Enum):
+    """Accumulation order (makes a difference for the projective result)."""
+    PeqPR = "P = P + R"
+    PeqRP = "P = R + P"
+
+
+@public
 class ScalarMultiplicationAction(ResultAction):
     """A scalar multiplication of a point on a curve by a scalar."""
 
@@ -58,6 +73,10 @@ class ScalarMultiplier(ABC):
     """
     A scalar multiplication algorithm.
 
+    .. note::
+        The __init__ method of all concrete subclasses needs to have type annotations so that
+        configuration enumeration works.
+
     :param short_circuit: Whether the use of formulas will be guarded by short-circuit on inputs
                           of the point at infinity.
     :param formulas: Formulas this instance will use.
@@ -202,16 +221,20 @@ class ScalarMultiplier(ABC):
 
 
 @public
-class LTRMultiplier(ScalarMultiplier):
+class DoubleAndAddMultiplier(ScalarMultiplier, ABC):
     """
-    Classic double and add scalar multiplication algorithm, that scans the scalar left-to-right (msb to lsb).
+    Classic double and add scalar multiplication algorithm.
 
     :param always: Whether the double and add always method is used.
+    :param direction: Whether it is LTR or RTL.
+    :param accumulation_order: The order of accumulation of points.
+    :param complete: (Only for LTR, always false for RTL) Whether it starts processing at full order-bit-length.
     """
-
     requires = {AdditionFormula, DoublingFormula}
     optionals = {ScalingFormula}
     always: bool
+    direction: ProcessingDirection
+    accumulation_order: AccumulationOrder
     complete: bool
 
     def __init__(
@@ -220,20 +243,70 @@ class LTRMultiplier(ScalarMultiplier):
             dbl: DoublingFormula,
             scl: Optional[ScalingFormula] = None,
             always: bool = False,
+            direction: ProcessingDirection = ProcessingDirection.LTR,
+            accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
             complete: bool = True,
             short_circuit: bool = True,
     ):
         super().__init__(short_circuit=short_circuit, add=add, dbl=dbl, scl=scl)
         self.always = always
+        self.direction = direction
+        self.accumulation_order = accumulation_order
         self.complete = complete
 
     def __hash__(self):
         return id(self)
 
     def __eq__(self, other):
-        if not isinstance(other, LTRMultiplier):
+        if not isinstance(other, DoubleAndAddMultiplier):
             return False
-        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.always == other.always and self.complete == other.complete
+        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.direction == other.direction and self.accumulation_order == other.accumulation_order and self.always == other.always and self.complete == other.complete
+
+    def __repr__(self):
+        return f"{self.__class__.__name__}({tuple(self.formulas.values())}, short_circuit={self.short_circuit}, accumulation_order={self.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
+
+    def _ltr(self, scalar: int) -> Point:
+        if self.complete:
+            q = self._point
+            r = copy(self._params.curve.neutral)
+            top = self._params.order.bit_length() - 1
+        else:
+            q = copy(self._point)
+            r = copy(self._point)
+            top = scalar.bit_length() - 2
+        for i in range(top, -1, -1):
+            r = self._dbl(r)
+            if scalar & (1 << i) != 0:
+                r = self._accumulate(r, q)
+            elif self.always:
+                # dummy add
+                self._accumulate(r, q)
+        return r
+
+    def _rtl(self, scalar: int) -> Point:
+        q = self._point
+        r = copy(self._params.curve.neutral)
+        if self.complete:
+            top = self._params.order.bit_length()
+        else:
+            top = scalar.bit_length()
+        for _ in range(top):
+            if scalar & 1 != 0:
+                r = self._accumulate(r, q)
+            elif self.always:
+                # dummy add
+                self._accumulate(r, q)
+            # TODO: This double is unnecessary in the last iteration.
+            q = self._dbl(q)
+            scalar >>= 1
+        return r
 
     def multiply(self, scalar: int) -> Point:
         if not self._initialized:
@@ -241,76 +314,55 @@ class LTRMultiplier(ScalarMultiplier):
         with ScalarMultiplicationAction(self._point, scalar) as action:
             if scalar == 0:
                 return action.exit(copy(self._params.curve.neutral))
-            if self.complete:
-                q = self._point
-                r = copy(self._params.curve.neutral)
-                top = self._params.order.bit_length() - 1
-            else:
-                q = copy(self._point)
-                r = copy(self._point)
-                top = scalar.bit_length() - 2
-            for i in range(top, -1, -1):
-                r = self._dbl(r)
-                if scalar & (1 << i) != 0:
-                    # TODO: This order makes a difference in projective coordinates
-                    r = self._add(r, q)
-                elif self.always:
-                    self._add(r, q)
+            if self.direction is ProcessingDirection.LTR:
+                r = self._ltr(scalar)
+            elif self.direction is ProcessingDirection.RTL:
+                r = self._rtl(scalar)
             if "scl" in self.formulas:
                 r = self._scl(r)
             return action.exit(r)
 
 
 @public
-class RTLMultiplier(ScalarMultiplier):
+class LTRMultiplier(DoubleAndAddMultiplier):
     """
-    Classic double and add scalar multiplication algorithm, that scans the scalar right-to-left (lsb to msb).
-
-    :param always: Whether the double and add always method is used.
+    Classic double and add scalar multiplication algorithm, that scans the scalar left-to-right (msb to lsb).
     """
 
-    requires = {AdditionFormula, DoublingFormula}
-    optionals = {ScalingFormula}
-    always: bool
-
     def __init__(
             self,
             add: AdditionFormula,
             dbl: DoublingFormula,
             scl: Optional[ScalingFormula] = None,
             always: bool = False,
+            accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
+            complete: bool = True,
             short_circuit: bool = True,
     ):
-        super().__init__(short_circuit=short_circuit, add=add, dbl=dbl, scl=scl)
-        self.always = always
+        super().__init__(short_circuit=short_circuit, direction=ProcessingDirection.LTR,
+                         accumulation_order=accumulation_order, always=always, complete=complete,
+                         add=add, dbl=dbl, scl=scl)
 
-    def __hash__(self):
-        return id(self)
 
-    def __eq__(self, other):
-        if not isinstance(other, RTLMultiplier):
-            return False
-        return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.always == other.always
+@public
+class RTLMultiplier(DoubleAndAddMultiplier):
+    """
+    Classic double and add scalar multiplication algorithm, that scans the scalar right-to-left (lsb to msb).
+    """
 
-    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))
-            q = self._point
-            r = copy(self._params.curve.neutral)
-            while scalar > 0:
-                if scalar & 1 != 0:
-                    # TODO: This order makes a difference in projective coordinates
-                    r = self._add(r, q)
-                elif self.always:
-                    self._add(r, q)
-                q = self._dbl(q)
-                scalar >>= 1
-            if "scl" in self.formulas:
-                r = self._scl(r)
-            return action.exit(r)
+    def __init__(
+            self,
+            add: AdditionFormula,
+            dbl: DoublingFormula,
+            scl: Optional[ScalingFormula] = None,
+            always: bool = False,
+            accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
+            complete: bool = True,
+            short_circuit: bool = True,
+    ):
+        super().__init__(short_circuit=short_circuit, direction=ProcessingDirection.RTL,
+                         accumulation_order=accumulation_order, always=always,
+                         add=add, dbl=dbl, scl=scl, complete=complete)
 
 
 @public
@@ -521,10 +573,12 @@ class DifferentialLadderMultiplier(ScalarMultiplier):
 
 @public
 class BinaryNAFMultiplier(ScalarMultiplier):
-    """Binary NAF (Non Adjacent Form) multiplier, left-to-right."""
+    """Binary NAF (Non Adjacent Form) multiplier."""
 
     requires = {AdditionFormula, DoublingFormula, NegationFormula}
     optionals = {ScalingFormula}
+    direction: ProcessingDirection
+    accumulation_order: AccumulationOrder
     _point_neg: Point
 
     def __init__(
@@ -533,11 +587,15 @@ class BinaryNAFMultiplier(ScalarMultiplier):
             dbl: DoublingFormula,
             neg: NegationFormula,
             scl: Optional[ScalingFormula] = None,
+            direction: ProcessingDirection = ProcessingDirection.LTR,
+            accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
             short_circuit: bool = True,
     ):
         super().__init__(
             short_circuit=short_circuit, add=add, dbl=dbl, neg=neg, scl=scl
         )
+        self.direction = direction
+        self.accumulation_order = accumulation_order
 
     def __hash__(self):
         return id(self)
@@ -552,6 +610,36 @@ 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:
+            q = self._dbl(q)
+            if val == 1:
+                q = self._accumulate(q, self._point)
+            if val == -1:
+                # TODO: Whether this negation is precomputed can be a parameter
+                q = self._accumulate(q, self._point_neg)
+        return q
+
+    def _rtl(self, scalar_naf: List[int]) -> Point:
+        q = self._point
+        r = copy(self._params.curve.neutral)
+        for val in reversed(scalar_naf):
+            if val == 1:
+                r = self._accumulate(r, q)
+            if val == -1:
+                neg = self._neg(q)
+                r = self._accumulate(r, neg)
+            q = self._dbl(q)
+        return r
+
     def multiply(self, scalar: int) -> Point:
         if not self._initialized:
             raise ValueError("ScalarMultiplier not initialized.")
@@ -559,13 +647,10 @@ class BinaryNAFMultiplier(ScalarMultiplier):
             if scalar == 0:
                 return action.exit(copy(self._params.curve.neutral))
             scalar_naf = naf(scalar)
-            q = copy(self._params.curve.neutral)
-            for val in scalar_naf:
-                q = self._dbl(q)
-                if val == 1:
-                    q = self._add(q, self._point)
-                if val == -1:
-                    q = self._add(q, self._point_neg)
+            if self.direction is ProcessingDirection.LTR:
+                q = self._ltr(scalar_naf)
+            elif self.direction is ProcessingDirection.RTL:
+                q = self._rtl(scalar_naf)
             if "scl" in self.formulas:
                 q = self._scl(q)
             return action.exit(q)
@@ -628,14 +713,17 @@ class WindowNAFMultiplier(ScalarMultiplier):
             scalar_naf = wnaf(scalar, self.width)
             q = copy(self._params.curve.neutral)
             for val in scalar_naf:
+                # TODO: Add RTL version of this.
                 q = self._dbl(q)
                 if val > 0:
+                    # TODO: This order makes a difference in projective coordinates
                     q = self._add(q, self._points[val])
                 elif val < 0:
                     if self.precompute_negation:
                         neg = self._points_neg[-val]
                     else:
                         neg = self._neg(self._points[-val])
+                    # TODO: This order makes a difference in projective coordinates
                     q = self._add(q, neg)
             if "scl" in self.formulas:
                 q = self._scl(q)
@@ -693,6 +781,7 @@ class FixedWindowLTRMultiplier(ScalarMultiplier):
         else:
             r = copy(point)
             q = self._dbl(point)
+            # TODO: This could be made via a different chain.
             for _ in range(self.m - 2):
                 q = self._add(q, r)
         return q
@@ -707,8 +796,10 @@ class FixedWindowLTRMultiplier(ScalarMultiplier):
             converted = convert(scalar, self.m)
             q = copy(self._params.curve.neutral)
             for digit in reversed(converted):
+                # TODO: Add RTL version of this.
                 q = self._mult_m(q)
                 if digit != 0:
+                    # TODO: This order makes a difference in projective coordinates
                     q = self._add(q, self._points[digit])
             if "scl" in self.formulas:
                 q = self._scl(q)
diff --git a/pyecsca/ec/naf.py b/pyecsca/ec/naf.py
deleted file mode 100644
index e69de29..0000000
--- a/pyecsca/ec/naf.py
+++ /dev/null
diff --git a/test/ec/test_configuration.py b/test/ec/test_configuration.py
index 17fb6f7..6f1d6ef 100644
--- a/test/ec/test_configuration.py
+++ b/test/ec/test_configuration.py
@@ -10,7 +10,7 @@ from pyecsca.ec.configuration import (
     Inversion,
 )
 from pyecsca.ec.model import ShortWeierstrassModel
-from pyecsca.ec.mult import LTRMultiplier
+from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder
 
 
 @pytest.fixture(scope="module")
@@ -30,7 +30,7 @@ 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) == 1960
+    assert len(configs) == 4060
 
 
 def test_mult_class(base_independents):
@@ -38,18 +38,19 @@ 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(configs) == 560
+    assert len(configs) == 1120
 
 
 def test_one(base_independents):
     model = ShortWeierstrassModel()
     coords = model.coordinates["projective"]
     scalarmult = {"cls": LTRMultiplier, "add": coords.formulas["add-1998-cmo"], "dbl": coords.formulas["dbl-1998-cmo"],
-                  "scl": None, "always": True, "complete": False, "short_circuit": True, }
+                  "scl": None, "always": True, "complete": False, "short_circuit": True,
+                  "accumulation_order": AccumulationOrder.PeqRP}
     configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult, **base_independents))
     assert len(configs) == 1
-    scalarmult = LTRMultiplier(coords.formulas["add-1998-cmo"], coords.formulas["dbl-1998-cmo"], None, True, False,
-                               True, )
+    scalarmult = LTRMultiplier(coords.formulas["add-1998-cmo"], coords.formulas["dbl-1998-cmo"], None, True,
+                               accumulation_order=AccumulationOrder.PeqRP, complete=False, short_circuit=True)
     configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult, **base_independents))
     assert len(configs) == 1
     configs = list(all_configurations(model=model, scalarmult=scalarmult, **base_independents))
diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py
index 6b4a64a..50925a1 100644
--- a/test/ec/test_mult.py
+++ b/test/ec/test_mult.py
@@ -2,6 +2,7 @@
 import pytest
 
 from pyecsca.ec.mult import (
+    DoubleAndAddMultiplier,
     LTRMultiplier,
     RTLMultiplier,
     LadderMultiplier,
@@ -9,7 +10,10 @@ from pyecsca.ec.mult import (
     WindowNAFMultiplier,
     SimpleLadderMultiplier,
     DifferentialLadderMultiplier,
-    CoronMultiplier, FixedWindowLTRMultiplier,
+    CoronMultiplier,
+    FixedWindowLTRMultiplier,
+    ProcessingDirection,
+    AccumulationOrder
 )
 from pyecsca.ec.point import InfinityPoint, Point
 from .utils import cartesian
@@ -90,6 +94,37 @@ def test_ltr(secp128r1, name, add, dbl, scale):
                              ("scaled", "add-1998-cmo", "dbl-1998-cmo", "z"),
                              ("complete", "add-2016-rcb", "dbl-2016-rcb", None),
                              ("none", "add-1998-cmo", "dbl-1998-cmo", None),
+                         ])
+def test_doubleandadd(secp128r1, name, add, dbl, scale):
+    a = do_basic_test(
+        DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale
+    )
+    b = do_basic_test(
+        DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, direction=ProcessingDirection.RTL
+    )
+    c = do_basic_test(
+        DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, accumulation_order=AccumulationOrder.PeqPR
+    )
+    d = do_basic_test(
+        DoubleAndAddMultiplier,
+        secp128r1,
+        secp128r1.generator,
+        add,
+        dbl,
+        scale,
+        always=True,
+        complete=False,
+    )
+    assert_pt_equality(a, b, scale)
+    assert_pt_equality(b, c, scale)
+    assert_pt_equality(c, d, scale)
+
+
+@pytest.mark.parametrize("name,add,dbl,scale",
+                         [
+                             ("scaled", "add-1998-cmo", "dbl-1998-cmo", "z"),
+                             ("complete", "add-2016-rcb", "dbl-2016-rcb", None),
+                             ("none", "add-1998-cmo", "dbl-1998-cmo", None),
                          ]
                          )
 def test_coron(secp128r1, name, add, dbl, scale):
@@ -292,6 +327,19 @@ def test_basic_multipliers(secp128r1, name, num, add, dbl):
     res_bnaf = bnaf.multiply(num)
     assert res_bnaf == res_ltr
 
+    bnaf_rtl = BinaryNAFMultiplier(
+        secp128r1.curve.coordinate_model.formulas[add],
+        secp128r1.curve.coordinate_model.formulas[dbl],
+        secp128r1.curve.coordinate_model.formulas["neg"],
+        secp128r1.curve.coordinate_model.formulas["z"],
+        direction=ProcessingDirection.RTL
+    )
+    with pytest.raises(ValueError):
+        bnaf_rtl.multiply(1)
+    bnaf_rtl.init(secp128r1, secp128r1.generator)
+    res_bnaf_rtl = bnaf_rtl.multiply(num)
+    assert res_bnaf_rtl == res_ltr
+
     wnaf = WindowNAFMultiplier(
         secp128r1.curve.coordinate_model.formulas[add],
         secp128r1.curve.coordinate_model.formulas[dbl],
diff --git a/test/sca/test_rpa.py b/test/sca/test_rpa.py
index f5dc7cc..daaf028 100644
--- a/test/sca/test_rpa.py
+++ b/test/sca/test_rpa.py
@@ -12,7 +12,7 @@ from pyecsca.ec.mult import (
     RTLMultiplier,
     BinaryNAFMultiplier,
     WindowNAFMultiplier,
-    SimpleLadderMultiplier,
+    SimpleLadderMultiplier, AccumulationOrder, ProcessingDirection,
 )
 from pyecsca.ec.params import DomainParameters
 from pyecsca.ec.point import Point
@@ -73,12 +73,12 @@ def test_0y_point(rpa_params):
 
 
 def test_distinguish(secp128r1, add, dbl, neg):
-    multipliers = [LTRMultiplier(add, dbl, None, False, True, True),
-                   LTRMultiplier(add, dbl, None, True, True, True),
-                   RTLMultiplier(add, dbl, None, False, True),
-                   RTLMultiplier(add, dbl, None, True, True),
+    multipliers = [LTRMultiplier(add, dbl, None, False, AccumulationOrder.PeqRP, True, True),
+                   LTRMultiplier(add, dbl, None, True, AccumulationOrder.PeqRP, True, True),
+                   RTLMultiplier(add, dbl, None, False, AccumulationOrder.PeqRP, True),
+                   RTLMultiplier(add, dbl, None, True, AccumulationOrder.PeqRP, True),
                    SimpleLadderMultiplier(add, dbl, None, True, True),
-                   BinaryNAFMultiplier(add, dbl, neg, None, True),
+                   BinaryNAFMultiplier(add, dbl, neg, None, ProcessingDirection.LTR, AccumulationOrder.PeqRP, True),
                    WindowNAFMultiplier(add, dbl, neg, 3, None, True),
                    WindowNAFMultiplier(add, dbl, neg, 4, None, True)]
     for real_mult in multipliers: