diff options
| author | J08nY | 2019-04-21 18:52:27 +0200 |
|---|---|---|
| committer | J08nY | 2019-04-21 18:52:27 +0200 |
| commit | 037194fd8cfe50aa2367c2f3c7fae5b41e7b46f9 (patch) | |
| tree | da5f51fa930cbf1c2ebdbf9f4af6f2935114097a | |
| parent | a843a055b76223cfd00f996b836a105ab5ea77d4 (diff) | |
| download | pyecsca-037194fd8cfe50aa2367c2f3c7fae5b41e7b46f9.tar.gz pyecsca-037194fd8cfe50aa2367c2f3c7fae5b41e7b46f9.tar.zst pyecsca-037194fd8cfe50aa2367c2f3c7fae5b41e7b46f9.zip | |
| -rw-r--r-- | pyecsca/ec/curve.py | 13 | ||||
| -rw-r--r-- | pyecsca/ec/group.py | 26 | ||||
| -rw-r--r-- | pyecsca/ec/mult.py | 85 | ||||
| -rw-r--r-- | test/ec/curves.py | 27 | ||||
| -rw-r--r-- | test/ec/test_coordinates.py | 24 | ||||
| -rw-r--r-- | test/ec/test_curve.py | 18 | ||||
| -rw-r--r-- | test/ec/test_mult.py | 10 | ||||
| -rw-r--r-- | test/ec/test_point.py | 48 |
8 files changed, 126 insertions, 125 deletions
diff --git a/pyecsca/ec/curve.py b/pyecsca/ec/curve.py index 97ccb58..7c30700 100644 --- a/pyecsca/ec/curve.py +++ b/pyecsca/ec/curve.py @@ -1,6 +1,7 @@ -from public import public from typing import MutableMapping, Union +from public import public + from .coordinates import CoordinateModel from .mod import Mod from .model import CurveModel @@ -13,17 +14,13 @@ class EllipticCurve(object): coordinate_model: CoordinateModel prime: int parameters: MutableMapping[str, Mod] - neutral: Point def __init__(self, model: CurveModel, coordinate_model: CoordinateModel, - prime: int, parameters: MutableMapping[str, Union[Mod, int]], neutral: Point): - # TODO: Add base_point arg, order arg, cofactor arg. + prime: int, parameters: MutableMapping[str, Union[Mod, int]]): if coordinate_model not in model.coordinates.values(): raise ValueError if set(model.parameter_names).symmetric_difference(parameters.keys()): raise ValueError - if neutral.coordinate_model != coordinate_model: - raise ValueError self.model = model self.coordinate_model = coordinate_model self.prime = prime @@ -35,7 +32,6 @@ class EllipticCurve(object): else: value = Mod(value, prime) self.parameters[name] = value - self.neutral = neutral def is_on_curve(self, point: Point) -> bool: if point.coordinate_model != self.coordinate_model: @@ -43,9 +39,6 @@ class EllipticCurve(object): loc = {**self.parameters, **point.to_affine().coords} return eval(compile(self.model.equation, "", mode="eval"), loc) - def is_neutral(self, point: Point) -> bool: - return self.neutral == point - def __repr__(self): params = ", ".join((f"{key}={val}" for key, val in self.parameters.items())) return f"EllipticCurve([{params}] on {self.model} using {self.coordinate_model})" diff --git a/pyecsca/ec/group.py b/pyecsca/ec/group.py new file mode 100644 index 0000000..4c471cc --- /dev/null +++ b/pyecsca/ec/group.py @@ -0,0 +1,26 @@ +from typing import Optional + +from public import public + +from .curve import EllipticCurve +from .point import Point + + +@public +class AbelianGroup(object): + curve: EllipticCurve + generator: Point + neutral: Point + order: Optional[int] + cofactor: Optional[int] + + def __init__(self, curve: EllipticCurve, generator: Point, neutral: Point, order: int = None, + cofactor: int = None): + self.curve = curve + self.generator = generator + self.neutral = neutral + self.order = order + self.cofactor = cofactor + + def is_neutral(self, point: Point) -> bool: + return self.neutral == point diff --git a/pyecsca/ec/mult.py b/pyecsca/ec/mult.py index fa225b3..2576d7a 100644 --- a/pyecsca/ec/mult.py +++ b/pyecsca/ec/mult.py @@ -5,22 +5,23 @@ from typing import Mapping, Tuple, Optional, MutableMapping, Union from pyecsca.ec.naf import naf, wnaf from .context import Context from .curve import EllipticCurve +from .group import AbelianGroup from .formula import (Formula, AdditionFormula, DoublingFormula, ScalingFormula, LadderFormula, NegationFormula, DifferentialAdditionFormula) from .point import Point class ScalarMultiplier(object): - curve: EllipticCurve + group: AbelianGroup formulas: Mapping[str, Formula] context: Context _point: Point = None - def __init__(self, curve: EllipticCurve, ctx: Context = None, **formulas: Optional[Formula]): + def __init__(self, group: AbelianGroup, ctx: Context = None, **formulas: Optional[Formula]): for formula in formulas.values(): - if formula is not None and formula.coordinate_model is not curve.coordinate_model: + if formula is not None and formula.coordinate_model is not group.curve.coordinate_model: raise ValueError - self.curve = curve + self.group = group if ctx: self.context = ctx else: @@ -30,44 +31,44 @@ class ScalarMultiplier(object): def _add(self, one: Point, other: Point) -> Point: if "add" not in self.formulas: raise NotImplementedError - if one == self.curve.neutral: + if one == self.group.neutral: return copy(other) - if other == self.curve.neutral: + if other == self.group.neutral: return copy(one) - return self.context.execute(self.formulas["add"], one, other, **self.curve.parameters)[0] + return self.context.execute(self.formulas["add"], one, other, **self.group.curve.parameters)[0] def _dbl(self, point: Point) -> Point: if "dbl" not in self.formulas: raise NotImplementedError - if point == self.curve.neutral: + if point == self.group.neutral: return copy(point) - return self.context.execute(self.formulas["dbl"], point, **self.curve.parameters)[0] + return self.context.execute(self.formulas["dbl"], point, **self.group.curve.parameters)[0] def _scl(self, point: Point) -> Point: if "scl" not in self.formulas: raise NotImplementedError - return self.context.execute(self.formulas["scl"], point, **self.curve.parameters)[0] + return self.context.execute(self.formulas["scl"], point, **self.group.curve.parameters)[0] def _ladd(self, start: Point, to_dbl: Point, to_add: Point) -> Tuple[Point, ...]: if "ladd" not in self.formulas: raise NotImplementedError return self.context.execute(self.formulas["ladd"], start, to_dbl, to_add, - **self.curve.parameters) + **self.group.curve.parameters) def _dadd(self, start: Point, one: Point, other: Point) -> Point: if "dadd" not in self.formulas: raise NotImplementedError - if one == self.curve.neutral: + if one == self.group.neutral: return copy(other) - if other == self.curve.neutral: + if other == self.group.neutral: return copy(one) return self.context.execute(self.formulas["dadd"], start, one, other, - **self.curve.parameters)[0] + **self.group.curve.parameters)[0] def _neg(self, point: Point) -> Point: if "neg" not in self.formulas: raise NotImplementedError - return self.context.execute(self.formulas["neg"], point, **self.curve.parameters)[0] + return self.context.execute(self.formulas["neg"], point, **self.group.curve.parameters)[0] def init(self, point: Point): self._point = point @@ -94,17 +95,17 @@ class LTRMultiplier(ScalarMultiplier): """ always: bool - def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + def __init__(self, group: AbelianGroup, add: AdditionFormula, dbl: DoublingFormula, scl: ScalingFormula = None, ctx: Context = None, always: bool = False): - super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, scl=scl) self.always = always def multiply(self, scalar: int, point: Optional[Point] = None) -> Point: if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) q = self._init_multiply(point) - r = copy(self.curve.neutral) + r = copy(self.group.neutral) for i in range(scalar.bit_length() - 1, -1, -1): r = self._dbl(r) if scalar & (1 << i) != 0: @@ -125,17 +126,17 @@ class RTLMultiplier(ScalarMultiplier): """ always: bool - def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + def __init__(self, group: AbelianGroup, add: AdditionFormula, dbl: DoublingFormula, scl: ScalingFormula = None, ctx: Context = None, always: bool = False): - super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, scl=scl) self.always = always def multiply(self, scalar: int, point: Optional[Point] = None) -> Point: if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) q = self._init_multiply(point) - r = copy(self.curve.neutral) + r = copy(self.group.neutral) while scalar > 0: if scalar & 1 != 0: r = self._add(r, q) @@ -157,13 +158,13 @@ class CoronMultiplier(ScalarMultiplier): https://link.springer.com/content/pdf/10.1007/3-540-48059-5_25.pdf """ - def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + def __init__(self, group: AbelianGroup, add: AdditionFormula, dbl: DoublingFormula, scl: ScalingFormula = None, ctx: Context = None): - super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, scl=scl) def multiply(self, scalar: int, point: Optional[Point] = None): if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) q = self._init_multiply(point) p0 = copy(q) for i in range(scalar.bit_length() - 2, -1, -1): @@ -182,13 +183,13 @@ class LadderMultiplier(ScalarMultiplier): Montgomery ladder multiplier, using a three input, two output ladder formula. """ - def __init__(self, curve: EllipticCurve, ladd: LadderFormula, dbl: DoublingFormula, scl: ScalingFormula = None, + def __init__(self, group: AbelianGroup, ladd: LadderFormula, dbl: DoublingFormula, scl: ScalingFormula = None, ctx: Context = None): - super().__init__(curve, ctx, ladd=ladd, dbl=dbl, scl=scl) + super().__init__(group, ctx, ladd=ladd, dbl=dbl, scl=scl) def multiply(self, scalar: int, point: Optional[Point] = None) -> Point: if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) q = self._init_multiply(point) p0 = copy(q) p1 = self._dbl(q) @@ -209,22 +210,22 @@ class SimpleLadderMultiplier(ScalarMultiplier): """ _differential: bool = False - def __init__(self, curve: EllipticCurve, + def __init__(self, group: AbelianGroup, add: Union[AdditionFormula, DifferentialAdditionFormula], dbl: DoublingFormula, scl: ScalingFormula = None, ctx: Context = None): if isinstance(add, AdditionFormula): - super().__init__(curve, ctx, add=add, dbl=dbl, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, scl=scl) elif isinstance(add, DifferentialAdditionFormula): - super().__init__(curve, ctx, dadd=add, dbl=dbl, scl=scl) + super().__init__(group, ctx, dadd=add, dbl=dbl, scl=scl) self._differential = True else: raise ValueError def multiply(self, scalar: int, point: Optional[Point] = None) -> Point: if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) q = self._init_multiply(point) - p0 = copy(self.curve.neutral) + p0 = copy(self.group.neutral) p1 = copy(q) for i in range(scalar.bit_length() - 1, -1, -1): if scalar & (1 << i) == 0: @@ -251,9 +252,9 @@ class BinaryNAFMultiplier(ScalarMultiplier): """ _point_neg: Point - def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + def __init__(self, group: AbelianGroup, add: AdditionFormula, dbl: DoublingFormula, neg: NegationFormula, scl: ScalingFormula = None, ctx: Context = None): - super().__init__(curve, ctx, add=add, dbl=dbl, neg=neg, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, neg=neg, scl=scl) def init(self, point: Point): super().init(point) @@ -261,10 +262,10 @@ class BinaryNAFMultiplier(ScalarMultiplier): def multiply(self, scalar: int, point: Optional[Point] = None) -> Point: if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) self._init_multiply(point) bnaf = naf(scalar) - q = copy(self.curve.neutral) + q = copy(self.group.neutral) for val in bnaf: q = self._dbl(q) if val == 1: @@ -286,10 +287,10 @@ class WindowNAFMultiplier(ScalarMultiplier): _precompute_neg: bool = False _width: int - def __init__(self, curve: EllipticCurve, add: AdditionFormula, dbl: DoublingFormula, + def __init__(self, group: AbelianGroup, add: AdditionFormula, dbl: DoublingFormula, neg: NegationFormula, width: int, scl: ScalingFormula = None, ctx: Context = None, precompute_negation: bool = False): - super().__init__(curve, ctx, add=add, dbl=dbl, neg=neg, scl=scl) + super().__init__(group, ctx, add=add, dbl=dbl, neg=neg, scl=scl) self._width = width self._precompute_neg = precompute_negation @@ -307,10 +308,10 @@ class WindowNAFMultiplier(ScalarMultiplier): def multiply(self, scalar: int, point: Optional[Point] = None): if scalar == 0: - return copy(self.curve.neutral) + return copy(self.group.neutral) self._init_multiply(point) naf = wnaf(scalar, self._width) - q = copy(self.curve.neutral) + q = copy(self.group.neutral) for val in naf: q = self._dbl(q) if val > 0: diff --git a/test/ec/curves.py b/test/ec/curves.py index d36e702..c7453c7 100644 --- a/test/ec/curves.py +++ b/test/ec/curves.py @@ -1,26 +1,29 @@ from pyecsca.ec.curve import EllipticCurve +from pyecsca.ec.group import AbelianGroup from pyecsca.ec.mod import Mod from pyecsca.ec.model import ShortWeierstrassModel, MontgomeryModel -from pyecsca.ec.point import InfinityPoint, Point +from pyecsca.ec.point import Point, InfinityPoint def get_secp128r1(): prime = 0xfffffffdffffffffffffffffffffffff model = ShortWeierstrassModel() - coords = ShortWeierstrassModel().coordinates["projective"] - return (EllipticCurve(model, coords, prime, dict(a=0xfffffffdfffffffffffffffffffffffc, - b=0xe87579c11079f43dd824993c2cee5ed3), - InfinityPoint(coords)), - Point(coords, X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, prime), - Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, prime), - Z=Mod(1, prime))) + coords = model.coordinates["projective"] + curve = EllipticCurve(model, coords, prime, dict(a=0xfffffffdfffffffffffffffffffffffc, + b=0xe87579c11079f43dd824993c2cee5ed3)) + return AbelianGroup(curve, Point(coords, X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, prime), + Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, prime), + Z=Mod(1, prime)), InfinityPoint(coords), + order=0xfffffffe0000000075a30d1b9038a115, cofactor=1) def get_curve25519(): prime = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed model = MontgomeryModel() coords = model.coordinates["xz"] - return (EllipticCurve(model, coords, prime, - dict(a=486662, b=1), - InfinityPoint(coords)), - Point(coords, X=Mod(9, prime), Z=Mod(1, prime))) + curve = EllipticCurve(model, coords, prime, + dict(a=486662, b=1)) + return AbelianGroup(curve, Point(coords, X=Mod(9, prime), Z=Mod(1, prime)), + InfinityPoint(coords), + order=0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED, + cofactor=2) diff --git a/test/ec/test_coordinates.py b/test/ec/test_coordinates.py deleted file mode 100644 index 31f3edf..0000000 --- a/test/ec/test_coordinates.py +++ /dev/null @@ -1,24 +0,0 @@ -from unittest import TestCase - -from pyecsca.ec.curve import EllipticCurve -from pyecsca.ec.mod import Mod -from pyecsca.ec.model import ShortWeierstrassModel -from pyecsca.ec.point import Point, InfinityPoint - - -class CoordinateTests(TestCase): - - def setUp(self): - self.p = 0xfffffffdffffffffffffffffffffffff - self.coords = ShortWeierstrassModel().coordinates["projective"] - self.secp128r1 = EllipticCurve(ShortWeierstrassModel(), self.coords, self.p, - dict(a=0xfffffffdfffffffffffffffffffffffc, - b=0xe87579c11079f43dd824993c2cee5ed3), - InfinityPoint(self.coords)) - - def test_affine(self): - pt = Point(self.coords, X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.p), - Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.p), - Z=Mod(1, self.p)) - affine_Point = pt.to_affine() - assert pt.equals(affine_Point) diff --git a/test/ec/test_curve.py b/test/ec/test_curve.py index 7e8e7eb..382d144 100644 --- a/test/ec/test_curve.py +++ b/test/ec/test_curve.py @@ -1,20 +1,18 @@ from unittest import TestCase from pyecsca.ec.mod import Mod -from pyecsca.ec.point import Point, InfinityPoint +from pyecsca.ec.point import Point from test.ec.curves import get_secp128r1 class CurveTests(TestCase): def setUp(self): - self.secp128r1, self.base = get_secp128r1() + self.secp128r1 = get_secp128r1() + self.base = self.secp128r1.generator def test_is_on_curve(self): - pt = Point(self.secp128r1.coordinate_model, - X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.prime), - Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.prime), - Z=Mod(1, self.secp128r1.prime)) - assert self.secp128r1.is_on_curve(pt) - - def test_is_neutral(self): - assert self.secp128r1.is_neutral(InfinityPoint(self.secp128r1.coordinate_model)) + pt = Point(self.secp128r1.curve.coordinate_model, + X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.curve.prime), + Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.curve.prime), + Z=Mod(1, self.secp128r1.curve.prime)) + assert self.secp128r1.curve.is_on_curve(pt) diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py index 8a82e3a..2d167f3 100644 --- a/test/ec/test_mult.py +++ b/test/ec/test_mult.py @@ -9,11 +9,13 @@ from test.ec.curves import get_secp128r1, get_curve25519 class ScalarMultiplierTests(TestCase): def setUp(self): - self.secp128r1, self.base = get_secp128r1() - self.coords = self.secp128r1.coordinate_model + self.secp128r1 = get_secp128r1() + self.base = self.secp128r1.generator + self.coords = self.secp128r1.curve.coordinate_model - self.curve25519, self.base25519 = get_curve25519() - self.coords25519 = self.curve25519.coordinate_model + self.curve25519 = get_curve25519() + self.base25519 = self.curve25519.generator + self.coords25519 = self.curve25519.curve.coordinate_model def test_rtl(self): mult = RTLMultiplier(self.secp128r1, self.coords.formulas["add-1998-cmo"], diff --git a/test/ec/test_point.py b/test/ec/test_point.py index a89a44f..a59204b 100644 --- a/test/ec/test_point.py +++ b/test/ec/test_point.py @@ -9,14 +9,16 @@ from test.ec.curves import get_secp128r1 class PointTests(TestCase): def setUp(self): - self.secp128r1, self.base = get_secp128r1() + self.secp128r1 = get_secp128r1() + self.base = self.secp128r1.generator + self.coords = self.secp128r1.curve.coordinate_model self.affine = AffineCoordinateModel(ShortWeierstrassModel()) def test_to_affine(self): - pt = Point(self.secp128r1.coordinate_model, - X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.prime), - Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.prime), - Z=Mod(1, self.secp128r1.prime)) + pt = Point(self.coords, + X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.curve.prime), + Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.curve.prime), + Z=Mod(1, self.secp128r1.curve.prime)) affine = pt.to_affine() self.assertIsInstance(affine.coordinate_model, AffineCoordinateModel) @@ -24,37 +26,37 @@ class PointTests(TestCase): self.assertEqual(affine.coords["x"], pt.coords["X"]) self.assertEqual(affine.coords["y"], pt.coords["Y"]) - affine = InfinityPoint(self.secp128r1.coordinate_model).to_affine() + affine = InfinityPoint(self.coords).to_affine() self.assertIsInstance(affine, InfinityPoint) def test_from_affine(self): - affine = Point(self.affine, x=Mod(0xabcd, self.secp128r1.prime), - y=Mod(0xef, self.secp128r1.prime)) - projective_model = self.secp128r1.coordinate_model + affine = Point(self.affine, x=Mod(0xabcd, self.secp128r1.curve.prime), + y=Mod(0xef, self.secp128r1.curve.prime)) + projective_model = self.coords other = Point.from_affine(projective_model, affine) self.assertEqual(other.coordinate_model, projective_model) self.assertSetEqual(set(other.coords.keys()), set(projective_model.variables)) self.assertEqual(other.coords["X"], affine.coords["x"]) self.assertEqual(other.coords["Y"], affine.coords["y"]) - self.assertEqual(other.coords["Z"], Mod(1, self.secp128r1.prime)) + self.assertEqual(other.coords["Z"], Mod(1, self.secp128r1.curve.prime)) def test_to_from_affine(self): - pt = Point(self.secp128r1.coordinate_model, - X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.prime), - Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.prime), - Z=Mod(1, self.secp128r1.prime)) - other = Point.from_affine(self.secp128r1.coordinate_model, pt.to_affine()) + pt = Point(self.coords, + X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.curve.prime), + Y=Mod(0xcf5ac8395bafeb13c02da292dded7a83, self.secp128r1.curve.prime), + Z=Mod(1, self.secp128r1.curve.prime)) + other = Point.from_affine(self.coords, pt.to_affine()) self.assertEqual(pt, other) def test_equals(self): - pt = Point(self.secp128r1.coordinate_model, - X=Mod(0x4, self.secp128r1.prime), - Y=Mod(0x6, self.secp128r1.prime), - Z=Mod(2, self.secp128r1.prime)) - other = Point(self.secp128r1.coordinate_model, - X=Mod(0x2, self.secp128r1.prime), - Y=Mod(0x3, self.secp128r1.prime), - Z=Mod(1, self.secp128r1.prime)) + pt = Point(self.coords, + X=Mod(0x4, self.secp128r1.curve.prime), + Y=Mod(0x6, self.secp128r1.curve.prime), + Z=Mod(2, self.secp128r1.curve.prime)) + other = Point(self.coords, + X=Mod(0x2, self.secp128r1.curve.prime), + Y=Mod(0x3, self.secp128r1.curve.prime), + Z=Mod(1, self.secp128r1.curve.prime)) assert pt.equals(other) self.assertNotEquals(pt, other) |
