diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | docs/index.rst | 9 | ||||
| -rw-r--r-- | pyecsca/ec/context.py | 38 | ||||
| -rw-r--r-- | pyecsca/ec/coordinates.py | 9 | ||||
| -rw-r--r-- | pyecsca/ec/curve.py | 23 | ||||
| -rw-r--r-- | pyecsca/ec/formula.py | 6 | ||||
| -rw-r--r-- | pyecsca/ec/mod.py | 128 | ||||
| -rw-r--r-- | pyecsca/ec/model.py | 2 | ||||
| -rw-r--r-- | pyecsca/ec/mult.py | 62 | ||||
| -rw-r--r-- | pyecsca/ec/point.py | 19 | ||||
| -rw-r--r-- | test/ec/__init__.py | 0 | ||||
| -rw-r--r-- | test/ec/test_model.py | 13 | ||||
| -rw-r--r-- | test/ec/test_mult.py | 22 |
14 files changed, 330 insertions, 8 deletions
@@ -7,4 +7,7 @@ test-plots: test-all: nose2 -v -.PHONY: test test-plots test-all
\ No newline at end of file +typecheck: + mypy -p pyecsca --ignore-missing-imports + +.PHONY: test test-plots test-all typecheck
\ No newline at end of file @@ -10,6 +10,8 @@ - [atpublic](https://public.readthedocs.io/) - [fastdtw](https://github.com/slaypni/fastdtw) +*pyecsca* contains data from the [Explicit-Formulas Database](https://www.hyperelliptic.org/EFD/index.html) by Daniel J. Bernstein and Tanja Lange. + ### Testing - [nose2](https://nose2.readthedocs.io) diff --git a/docs/index.rst b/docs/index.rst index 43ed1fa..a1a7e33 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -27,6 +27,11 @@ Requirements - atpublic_ - fastdtw_ +*pyecsca* contains data from the `Explicit-Formulas Database`_ by Daniel J. Bernstein and Tanja Lange. + +It also supports working with Riscure_ Inspector trace sets, which are of a proprietary format. + + Testing ------- @@ -70,4 +75,6 @@ License .. _fastdtw: https://github.com/slaypni/fastdtw .. _nose2: https://nose2.readthedocs.io .. _green: https://github.com/CleanCut/green -.. _sphinx: https://www.sphinx-doc.org/
\ No newline at end of file +.. _sphinx: https://www.sphinx-doc.org/ +.. _Explicit-Formulas Database: https://www.hyperelliptic.org/EFD/index.html +.. _Riscure: https://www.riscure.com/
\ No newline at end of file diff --git a/pyecsca/ec/context.py b/pyecsca/ec/context.py new file mode 100644 index 0000000..a65f461 --- /dev/null +++ b/pyecsca/ec/context.py @@ -0,0 +1,38 @@ +from typing import List, Tuple + +from .formula import Formula +from .mod import Mod +from .point import Point + + +class Context(object): + intermediates: List[Tuple[str, Mod]] + + def __init__(self): + self.intermediates = [] + + def __enter__(self): + return self + + def __exit__(self, exc_type, exc_val, exc_tb): + pass + + def execute(self, formula: Formula, *points: Point, **params: Mod) -> Point: + coords = {} + for i, point in enumerate(points): + if point.coordinate_model != formula.coordinate_model: + raise ValueError + for coord, value in point.coords.items(): + coords[coord + str(i + 1)] = value + locals = {**coords, **params} + previous_locals = set(locals.keys()) + for line in formula.code: + exec(compile(line, "", mode="exec"), {}, locals) + diff = set(locals.keys()).difference(previous_locals) + previous_locals = set(locals.keys()) + for key in diff: + self.intermediates.append((key, locals[key])) + resulting = {variable: locals[variable + "3"] + for variable in formula.coordinate_model.variables + if variable + "3" in locals} + return Point(formula.coordinate_model, **resulting) diff --git a/pyecsca/ec/coordinates.py b/pyecsca/ec/coordinates.py index d1b7870..61ee5bf 100644 --- a/pyecsca/ec/coordinates.py +++ b/pyecsca/ec/coordinates.py @@ -2,7 +2,9 @@ from ast import parse, Expression from pkg_resources import resource_listdir, resource_isdir, resource_stream from typing import List, Any, MutableMapping -from .formula import Formula, AdditionFormula, DoublingFormula, TriplingFormula, DifferentialAdditionFormula, LadderFormula, ScalingFormula +from .formula import (Formula, AdditionFormula, DoublingFormula, TriplingFormula, + DifferentialAdditionFormula, LadderFormula, ScalingFormula) + class CoordinateModel(object): name: str @@ -59,12 +61,13 @@ class CoordinateModel(object): elif line.startswith("variable"): self.variables.append(line[9:]) elif line.startswith("satisfying"): - self.satisfying.append(parse(line[11:].replace("=", "==").replace("^", "**"), mode="eval")) + self.satisfying.append( + parse(line[11:].replace("=", "==").replace("^", "**"), mode="eval")) elif line.startswith("parameter"): self.parameters.append(line[10:]) elif line.startswith("assume"): self.assumptions.append( - parse(line[7:].replace("=", "==").replace("^", "**"), mode="eval")) + parse(line[7:].replace("=", "==").replace("^", "**"), mode="eval")) line = f.readline().decode("ascii") def __repr__(self): diff --git a/pyecsca/ec/curve.py b/pyecsca/ec/curve.py new file mode 100644 index 0000000..79939b7 --- /dev/null +++ b/pyecsca/ec/curve.py @@ -0,0 +1,23 @@ +from typing import Type, Mapping + +from .point import Point +from .coordinates import CoordinateModel +from .model import CurveModel + + +class EllipticCurve(object): + model: Type[CurveModel] + coordinate_model: CoordinateModel + parameters: Mapping[str, int] + neutral: Point + + def __init__(self, model: Type[CurveModel], coordinate_model: CoordinateModel, + parameters: Mapping[str, int], neutral: Point = None): + if coordinate_model not in model.coordinates.values(): + raise ValueError + if set(model.parameter_names).symmetric_difference(parameters.keys()): + raise ValueError + self.model = model + self.coordinate_model = coordinate_model + self.parameters = dict(parameters) + self.neutral = neutral diff --git a/pyecsca/ec/formula.py b/pyecsca/ec/formula.py index 42f73a7..877f4d5 100644 --- a/pyecsca/ec/formula.py +++ b/pyecsca/ec/formula.py @@ -9,13 +9,14 @@ class Formula(object): source: str parameters: List[str] assumptions: List[Expression] - code: Module + code: List[Module] def __init__(self, path: str, name: str, coordinate_model: Any): self.name = name self.coordinate_model = coordinate_model self.parameters = [] self.assumptions = [] + self.code = [] self.__read_meta_file(path) self.__read_op3_file(path + ".op3") @@ -35,7 +36,8 @@ class Formula(object): def __read_op3_file(self, path): with resource_stream(__name__, path) as f: - self.code = parse(f.read(), path, mode="exec") + for line in f.readlines(): + self.code.append(parse(line.decode("ascii").replace("^", "**"), path, mode="exec")) def __repr__(self): return self.__class__.__name__ + "({} for {})".format(self.name, self.coordinate_model) diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py new file mode 100644 index 0000000..1deb6de --- /dev/null +++ b/pyecsca/ec/mod.py @@ -0,0 +1,128 @@ +from functools import wraps + + +def gcd(a, b): + if abs(a) < abs(b): + return gcd(b, a) + + while abs(b) > 0: + q, r = divmod(a, b) + a, b = b, r + + return a + + +def extgcd(a, b): + if abs(b) > abs(a): + (x, y, d) = extgcd(b, a) + return y, x, d + + if abs(b) == 0: + return 1, 0, a + + x1, x2, y1, y2 = 0, 1, 1, 0 + while abs(b) > 0: + q, r = divmod(a, b) + x = x2 - q * x1 + y = y2 - q * y1 + a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y + + return x2, y2, a + + +def check(func): + @wraps(func) + def method(self, other): + if type(self) is not type(other): + other = self.__class__(other, self.n) + else: + if self.n != other.n: + raise ValueError + return func(self, other) + + return method + + +class Mod(object): + + def __init__(self, x: int, n: int): + self.x: int = x % n + self.n: int = n + + @check + def __add__(self, other): + return Mod((self.x + other.x) % self.n, self.n) + + @check + def __radd__(self, other): + return self + other + + @check + def __sub__(self, other): + return Mod((self.x - other.x) % self.n, self.n) + + @check + def __rsub__(self, other): + return -self + other + + def __neg__(self): + return Mod(self.n - self.x, self.n) + + def inverse(self): + x, y, d = extgcd(self.x, self.n) + return Mod(x, self.n) + + def __invert__(self): + return self.inverse() + + @check + def __mul__(self, other): + if self.n != other.n: + raise ValueError + return Mod((self.x * other.x) % self.n, self.n) + + @check + def __rmul__(self, other): + return self * other + + @check + def __truediv__(self, other): + return self * ~other + + @check + def __rtruediv__(self, other): + return ~self * other + + @check + def __div__(self, other): + return self.__truediv__(other) + + @check + def __rdiv__(self, other): + return self.__rtruediv__(other) + + @check + def __divmod__(self, divisor): + q, r = divmod(self.x, divisor.x) + return Mod(q, self.n), Mod(r, self.n) + + def __int__(self): + return self.x + + def __repr__(self): + return str(self.x) + + def __pow__(self, n): + if type(n) is not int: + raise TypeError + + q = self + r = self if n & 1 else Mod(1, self.n) + + i = 2 + while i <= n: + q = (q * q) + if n & i == i: + r = (q * r) + i = i << 1 + return r diff --git a/pyecsca/ec/model.py b/pyecsca/ec/model.py index 285f1d2..84928bc 100644 --- a/pyecsca/ec/model.py +++ b/pyecsca/ec/model.py @@ -21,7 +21,7 @@ class CurveModel(object): to_weierstrass: List[Module] from_weierstrass: List[Module] - def __init_subclass__(cls, efd_name: str = None, **kwargs): + def __init_subclass__(cls, efd_name: str = "", **kwargs): cls._efd_name = efd_name files = resource_listdir(__name__, "efd/" + efd_name) cls.coordinates = {} diff --git a/pyecsca/ec/mult.py b/pyecsca/ec/mult.py new file mode 100644 index 0000000..6a127d3 --- /dev/null +++ b/pyecsca/ec/mult.py @@ -0,0 +1,62 @@ +from copy import copy +from typing import Mapping + +from .context import Context +from .curve import EllipticCurve +from .formula import Formula, AdditionFormula, DoublingFormula, ScalingFormula +from .point import Point + + +class ScalarMultiplier(object): + curve: EllipticCurve + formulas: Mapping[str, Formula] + context: Context + + def __init__(self, curve: EllipticCurve, ctx: Context = None, **formulas: Formula): + for formula in formulas.values(): + if formula is not None and formula.coordinate_model is not curve.coordinate_model: + raise ValueError + self.curve = curve + if ctx: + self.context = ctx + else: + self.context = Context() + self.formulas = dict(formulas) + + def multiply(self, scalar: int, point: Point) -> Point: + raise NotImplementedError + + +class LTRMultiplier(ScalarMultiplier): + always: bool + + def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + scl: ScalingFormula = None, + ctx: Context = None, always: bool = False): + super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + self.always = always + + def multiply(self, scalar: int, point: Point) -> Point: + pass + + +class RTLMultiplier(ScalarMultiplier): + always: bool + + def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + scl: ScalingFormula = None, + ctx: Context = None, always: bool = False): + super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + self.always = always + + def multiply(self, scalar: int, point: Point) -> Point: + q = copy(point) + r = copy(self.curve.neutral) + while scalar > 0: + q = self.context.execute(self.formulas["dbl"], q, **self.curve.parameters) + if scalar & 1 != 0: + r = self.context.execute(self.formulas["add"], q, r, **self.curve.parameters) + elif self.always: + self.context.execute(self.formulas["add"], q, r, **self.curve.parameters) + scalar >>= 1 + return r diff --git a/pyecsca/ec/point.py b/pyecsca/ec/point.py new file mode 100644 index 0000000..6c793b8 --- /dev/null +++ b/pyecsca/ec/point.py @@ -0,0 +1,19 @@ +from typing import Mapping + +from .coordinates import CoordinateModel +from .mod import Mod + + +class Point(object): + coordinate_model: CoordinateModel + coords: Mapping[str, Mod] + + def __init__(self, model: CoordinateModel, **coords: Mod): + if not set(model.variables) == set(coords.keys()): + raise ValueError + self.coordinate_model = model + self.coords = coords + + def __repr__(self): + args = ", ".join(["{}={}".format(key, value) for key, value in self.coords.items()]) + return "Point([{}] in {})".format(args, self.coordinate_model) diff --git a/test/ec/__init__.py b/test/ec/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/test/ec/__init__.py diff --git a/test/ec/test_model.py b/test/ec/test_model.py new file mode 100644 index 0000000..6effa45 --- /dev/null +++ b/test/ec/test_model.py @@ -0,0 +1,13 @@ +from unittest import TestCase + +from pyecsca.ec.model import (ShortWeierstrassModel, MontgomeryModel, EdwardsModel, + TwistedEdwardsModel) + + +class CurveModelTests(TestCase): + + def test_load(self): + self.assertGreater(len(ShortWeierstrassModel.coordinates), 0) + self.assertGreater(len(MontgomeryModel.coordinates), 0) + self.assertGreater(len(EdwardsModel.coordinates), 0) + self.assertGreater(len(TwistedEdwardsModel.coordinates), 0) diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py new file mode 100644 index 0000000..021a6a3 --- /dev/null +++ b/test/ec/test_mult.py @@ -0,0 +1,22 @@ +from unittest import TestCase + +from pyecsca.ec.context import Context +from pyecsca.ec.curve import EllipticCurve +from pyecsca.ec.mod import Mod +from pyecsca.ec.model import ShortWeierstrassModel +from pyecsca.ec.mult import RTLMultiplier +from pyecsca.ec.point import Point + + +class ScalarMultiplierTests(TestCase): + + def test_rtl_simple(self): + p = 11 + coords = ShortWeierstrassModel.coordinates["projective"] + curve = EllipticCurve(ShortWeierstrassModel, coords, dict(a=5, b=7), + Point(coords, X=Mod(0, p), Y=Mod(0, p), Z=Mod(1, p))) + with Context() as ctx: + mult = RTLMultiplier(curve, coords.formulas["add-2002-bj"], + coords.formulas["dbl-2007-bl"], ctx=ctx) + result = mult.multiply(10, Point(coords, X=Mod(4, p), Y=Mod(3, p), Z=Mod(1, p))) + print(ctx.intermediates) |