Add Context for tracing multiples, usable for RPA.

6 files changed, 94 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 2eaf069..0498208 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,7 @@ ec.test_params ec.test_key_agreement ec.test_key_generation ec.test_mod ec.test_
 ec.test_mult ec.test_naf ec.test_op ec.test_point ec.test_signature ec.test_transformations ec.test_regress
 
 SCA_TESTS = sca.test_align sca.test_combine sca.test_edit sca.test_filter sca.test_match sca.test_process \
-sca.test_sampling sca.test_target sca.test_test sca.test_trace sca.test_traceset sca.test_plot
+sca.test_sampling sca.test_target sca.test_test sca.test_trace sca.test_traceset sca.test_plot sca.test_rpa
 
 TESTS = ${EC_TESTS} ${SCA_TESTS}
 
diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py
index 8a4b66a..1ada79b 100644
--- a/pyecsca/ec/mod.py
+++ b/pyecsca/ec/mod.py
@@ -316,6 +316,9 @@ class RawMod(Mod):
     def __repr__(self):
         return str(self.x)
 
+    def __hash__(self):
+        return hash(("RawMod", self.x, self.n))
+
     def __pow__(self, n):
         if type(n) is not int:
             raise TypeError
@@ -409,6 +412,9 @@ class Undefined(Mod):
     def __repr__(self):
         return "Undefined"
 
+    def __hash__(self):
+        return hash("Undefined") + 1
+
     def __pow__(self, n):
         raise NotImplementedError
 
@@ -515,6 +521,9 @@ if has_gmp:
         def __repr__(self):
             return str(int(self.x))
 
+        def __hash__(self):
+            return hash(("GMPMod", self.x, self.n))
+
         def __pow__(self, n):
             if type(n) not in (int, gmpy2.mpz):
                 raise TypeError
diff --git a/pyecsca/ec/point.py b/pyecsca/ec/point.py
index 88c925b..df9e054 100644
--- a/pyecsca/ec/point.py
+++ b/pyecsca/ec/point.py
@@ -165,7 +165,7 @@ class Point(object):
         return self.coords == other.coords
 
     def __hash__(self):
-        return hash(self.coords) + 1
+        return hash((tuple(self.coords.keys()), tuple(self.coords.values()))) + 1
 
     def __str__(self):
         args = ", ".join([f"{key}={val}" for key, val in self.coords.items()])
diff --git a/pyecsca/sca/re/__init__.py b/pyecsca/sca/re/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/pyecsca/sca/re/__init__.py
diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py
new file mode 100644
index 0000000..2be2320
--- /dev/null
+++ b/pyecsca/sca/re/rpa.py
@@ -0,0 +1,52 @@
+from public import public
+from typing import MutableMapping
+
+from ...ec.formula import FormulaAction, DoublingFormula, AdditionFormula, TriplingFormula, NegationFormula, \
+    DifferentialAdditionFormula, LadderFormula
+from ...ec.mult import ScalarMultiplicationAction
+from ...ec.point import Point
+from ...ec.context import Context, Action
+
+
+@public
+class MultipleContext(Context):
+    """A context that traces the multiples computed."""
+    base: Point
+    points: MutableMapping[Point, int]
+    inside: bool
+
+    def enter_action(self, action: Action) -> None:
+        if isinstance(action, ScalarMultiplicationAction):
+            self.base = action.point
+            self.points = {self.base: 1}
+            self.inside = True
+
+    def exit_action(self, action: Action) -> None:
+        if isinstance(action, ScalarMultiplicationAction):
+            self.inside = False
+        if isinstance(action, FormulaAction) and self.inside:
+            if isinstance(action.formula, DoublingFormula):
+                inp = action.input_points[0]
+                out = action.output_points[0]
+                self.points[out] = 2 * self.points[inp]
+            elif isinstance(action.formula, TriplingFormula):
+                inp = action.input_points[0]
+                out = action.output_points[0]
+                self.points[out] = 3 * self.points[inp]
+            elif isinstance(action.formula, AdditionFormula):
+                one, other = action.input_points
+                out = action.output_points[0]
+                self.points[out] = self.points[one] + self.points[other]
+            elif isinstance(action.formula, NegationFormula):
+                inp = action.input_points[0]
+                out = action.output_points[0]
+                self.points[out] = - self.points[inp]
+            elif isinstance(action.formula, DifferentialAdditionFormula):
+                diff, one, other = action.input_points
+                out = action.output_points[0]
+                self.points[out] = self.points[one] + self.points[other]
+            elif isinstance(action.formula, LadderFormula):
+                diff, one, other = action.input_points
+                dbl, add = action.output_points
+                self.points[dbl] = 2 * self.points[one]
+                self.points[add] = self.points[one] + self.points[other]
diff --git a/test/sca/test_rpa.py b/test/sca/test_rpa.py
new file mode 100644
index 0000000..b442ce2
--- /dev/null
+++ b/test/sca/test_rpa.py
@@ -0,0 +1,31 @@
+from unittest import TestCase
+
+from parameterized import parameterized
+
+from pyecsca.ec.context import local
+from pyecsca.ec.mult import LTRMultiplier
+from pyecsca.ec.params import get_params
+from pyecsca.sca.re.rpa import MultipleContext
+
+
+class MultipleContextTests(TestCase):
+
+    @parameterized.expand([
+        ("10", 10),
+        ("2355498743", 2355498743),
+        ("325385790209017329644351321912443757746", 325385790209017329644351321912443757746),
+        ("13613624287328732", 13613624287328732)
+    ])
+    def test_basic(self, name, scalar):
+        secp128r1 = get_params("secg", "secp128r1", "projective")
+        base = secp128r1.generator
+        coords = secp128r1.curve.coordinate_model
+        add = coords.formulas["add-1998-cmo"]
+        dbl = coords.formulas["dbl-1998-cmo"]
+        scl = coords.formulas["z"]
+        mult = LTRMultiplier(add, dbl, scl, always=False, complete=False, short_circuit=True)
+        with local(MultipleContext()) as ctx:
+            mult.init(secp128r1, base)
+            mult.multiply(scalar)
+        muls = list(ctx.points.values())
+        self.assertEqual(muls[-1], scalar)