Introduce symbolic Mod.

5 files changed, 172 insertions, 18 deletions

diff --git a/Makefile b/Makefile
index 0498208..b5457ae 100644
--- a/Makefile
+++ b/Makefile
@@ -19,9 +19,15 @@ test-all:
 typecheck:
 	mypy pyecsca --ignore-missing-imports --show-error-codes
 
+typecheck-all:
+	mypy pyecsca test --ignore-missing-imports --show-error-codes
+
 codestyle:
 	flake8 --ignore=E501,F405,F403,F401,E126 pyecsca
 
+codestyle-all:
+	flake8 --ignore=E501,F405,F403,F401,E126 pyecsca test
+
 doc-coverage:
 	interrogate -vv -nmps pyecsca
 
@@ -29,4 +35,4 @@ docs:
 	$(MAKE) -C docs apidoc
 	$(MAKE) -C docs html
 
-.PHONY: test test-plots test-all typecheck codestyle doc-coverage docs
\ No newline at end of file
+.PHONY: test test-plots test-all typecheck typecheck-all codestyle codestyle-all doc-coverage docs
\ No newline at end of file
diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py
index 1ada79b..c051e20 100644
--- a/pyecsca/ec/mod.py
+++ b/pyecsca/ec/mod.py
@@ -4,6 +4,7 @@ from functools import wraps, lru_cache
 from typing import Type, Dict
 
 from public import public
+from sympy import Expr, Mod as SympyMod, FF
 
 from .error import raise_non_invertible, raise_non_residue
 from .context import ResultAction
@@ -194,14 +195,6 @@ class Mod(object):
         return ~self * other
 
     @check
-    def __div__(self, other):
-        return self.__floordiv__(other)
-
-    @check
-    def __rdiv__(self, other):
-        return self.__rfloordiv__(other)
-
-    @check
     def __divmod__(self, divisor):
         q, r = divmod(self.x, divisor.x)
         return self.__class__(q, self.n), self.__class__(r, self.n)
@@ -388,12 +381,6 @@ class Undefined(Mod):
     def __rfloordiv__(self, other):
         raise NotImplementedError
 
-    def __div__(self, other):
-        raise NotImplementedError
-
-    def __rdiv__(self, other):
-        raise NotImplementedError
-
     def __divmod__(self, divisor):
         raise NotImplementedError
 
@@ -419,6 +406,118 @@ class Undefined(Mod):
         raise NotImplementedError
 
 
+def symbolic_check(func):
+    @wraps(func)
+    def method(self, other):
+        if type(self) is not type(other):
+            if type(other) is int:
+                other = self.__class__(FF(self.n)(other), self.n)
+            else:
+                other = self.__class__(other, self.n)
+        else:
+            if self.n != other.n:
+                raise ValueError
+        return func(self, other)
+
+    return method
+
+
+@public
+class SymbolicMod(Mod):
+    """A symbolic element x of ℤₙ."""
+    x: Expr
+    n: int
+
+    def __new__(cls, *args, **kwargs):
+        return object.__new__(cls)
+
+    def __init__(self, x: Expr, n: int):
+        super().__init__(x, n)
+
+    @symbolic_check
+    def __add__(self, other):
+        return self.__class__((self.x + other.x), self.n)
+
+    @symbolic_check
+    def __radd__(self, other):
+        return self + other
+
+    @symbolic_check
+    def __sub__(self, other):
+        return self.__class__((self.x - other.x), self.n)
+
+    @symbolic_check
+    def __rsub__(self, other):
+        return -self + other
+
+    def __neg__(self):
+        return self.__class__(- self.x, self.n)
+
+    def inverse(self):
+        return self.__class__(self.x**(-1), self.n)
+
+    def sqrt(self):
+        raise NotImplementedError
+
+    def is_residue(self) -> bool:
+        raise NotImplementedError
+
+    def __invert__(self):
+        return self.inverse()
+
+    @symbolic_check
+    def __mul__(self, other):
+        return self.__class__(self.x * other.x, self.n)
+
+    @symbolic_check
+    def __rmul__(self, other):
+        return self * other
+
+    @symbolic_check
+    def __truediv__(self, other):
+        return self * ~other
+
+    @symbolic_check
+    def __rtruediv__(self, other):
+        return ~self * other
+
+    @symbolic_check
+    def __floordiv__(self, other):
+        return self * ~other
+
+    @symbolic_check
+    def __rfloordiv__(self, other):
+        return ~self * other
+
+    def __divmod__(self, divisor):
+        raise NotImplementedError
+
+    def __bytes__(self):
+        return int(self.x).to_bytes((self.n.bit_length() + 7) // 8, byteorder="big")
+
+    def __int__(self):
+        return int(self.x)
+
+    def __eq__(self, other):
+        if type(other) is int:
+            return self.x == other % self.n
+        if type(other) is not SymbolicMod:
+            return False
+        return self.x == other.x and self.n == other.n
+
+    def __ne__(self, other):
+        return not self == other
+
+    def __repr__(self):
+        return str(self.x)
+
+    def __hash__(self):
+        return hash(("SymbolicMod", self.x, self.n)) + 1
+
+    def __pow__(self, n):
+        return SymbolicMod(pow(self.x, n, self.n), self.n)
+
+
 if has_gmp:
 
     @public
diff --git a/pyecsca/ec/point.py b/pyecsca/ec/point.py
index 11aee7d..ae6ded9 100644
--- a/pyecsca/ec/point.py
+++ b/pyecsca/ec/point.py
@@ -1,5 +1,5 @@
 from copy import copy
-from typing import Mapping, TYPE_CHECKING
+from typing import Mapping, TYPE_CHECKING, Optional
 
 from public import public
 
@@ -47,7 +47,7 @@ class Point(object):
             else:
                 if field != value.n:
                     raise ValueError(f"Mismatched coordinate field of definition, {field} vs {value.n}.")
-        self.field = field
+        self.field = field if field is not None else 0
 
     def __getattribute__(self, name):
         # Do the magic such that point.X1 works!
diff --git a/test/ec/test_formula.py b/test/ec/test_formula.py
index a7ef691..ec585ad 100644
--- a/test/ec/test_formula.py
+++ b/test/ec/test_formula.py
@@ -1,5 +1,8 @@
 from unittest import TestCase
 
+from sympy import FF, symbols
+
+from pyecsca.ec.mod import SymbolicMod, Mod
 from pyecsca.misc.cfg import TemporaryConfig
 from pyecsca.ec.error import UnsatisfiedAssumptionError
 from pyecsca.ec.params import get_params
@@ -59,3 +62,18 @@ class FormulaTests(TestCase):
     def test_parameters(self):
         res = self.jac_dbl(self.secp128r1.curve.prime, self.jac_secp128r1.generator, **self.jac_secp128r1.curve.parameters)
         self.assertIsNotNone(res)
+
+    def test_symbolic(self):
+        p = self.secp128r1.curve.prime
+        k = FF(p)
+        coords = self.secp128r1.curve.coordinate_model
+        sympy_params = {key: SymbolicMod(k(int(value)), p) for key, value in self.secp128r1.curve.parameters.items()}
+        symbolic_point = Point(coords, **{key: SymbolicMod(symbols(key), p) for key in coords.variables})
+        symbolic_double = self.dbl(p, symbolic_point, **sympy_params)[0]
+        generator_double = self.dbl(p, self.secp128r1.generator, **self.secp128r1.curve.parameters)[0]
+        for outer_var in coords.variables:
+            symbolic_val = getattr(symbolic_double, outer_var).x
+            generator_val = getattr(generator_double, outer_var).x
+            for inner_var in coords.variables:
+                symbolic_val = symbolic_val.subs(inner_var, k(getattr(self.secp128r1.generator, inner_var).x))
+            self.assertEqual(Mod(int(symbolic_val), p), Mod(generator_val, p))
diff --git a/test/ec/test_mod.py b/test/ec/test_mod.py
index 24b3302..d21238b 100644
--- a/test/ec/test_mod.py
+++ b/test/ec/test_mod.py
@@ -1,6 +1,7 @@
+from sympy import FF, symbols
 from unittest import TestCase
 
-from pyecsca.ec.mod import Mod, gcd, extgcd, Undefined, miller_rabin, has_gmp, RawMod
+from pyecsca.ec.mod import Mod, gcd, extgcd, Undefined, miller_rabin, has_gmp, RawMod, SymbolicMod
 from pyecsca.ec.error import NonInvertibleError, NonResidueError, NonInvertibleWarning, NonResidueWarning
 from pyecsca.misc.cfg import getconfig, TemporaryConfig
 
@@ -105,6 +106,7 @@ class ModTests(TestCase):
         self.assertEqual(5 + b, Mod(1, 7))
         self.assertEqual(a + 3, Mod(1, 7))
         self.assertNotEqual(a, 6)
+        self.assertIsNotNone(hash(a))
 
     def test_undefined(self):
         u = Undefined()
@@ -126,3 +128,32 @@ class ModTests(TestCase):
         with TemporaryConfig() as cfg:
             cfg.ec.mod_implementation = "python"
             self.assertIsInstance(Mod(5, 7), RawMod)
+
+    def test_symbolic(self):
+        x, y = symbols("x y")
+        p = 13
+        k = FF(p)
+        sx = SymbolicMod(x, p)
+        a = k(3)
+        b = k(5)
+        r = sx * a + b
+        self.assertIsInstance(r, SymbolicMod)
+        self.assertEqual(r.n, p)
+        sa = SymbolicMod(a, p)
+        sb = SymbolicMod(b, p)
+        self.assertEqual(sa, 3)
+        self.assertEqual(sa.inverse(), SymbolicMod(k(9), p))
+        self.assertEqual(1 / sa, SymbolicMod(k(9), p))
+        self.assertEqual(sa + sb, 8)
+        self.assertEqual(1 + sa, 4)
+        self.assertEqual(sa - 1, 2)
+        self.assertEqual(1 - sa, 11)
+        self.assertEqual(sa + 1, 4)
+        self.assertEqual(-sa, 10)
+        self.assertEqual(sa / 2, 8)
+        self.assertEqual(2 / sa, 5)
+        self.assertEqual(sa // 2, 8)
+        self.assertEqual(2 // sa, 5)
+        self.assertEqual(int(sa), 3)
+        self.assertNotEqual(sa, sb)
+        self.assertIsNotNone(hash(sa))