aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJ08nY2020-02-20 19:52:24 +0100
committerJ08nY2020-02-20 19:52:24 +0100
commitc2d2771a0ed5e4462962f603b8b0e93a88f188a3 (patch)
tree8a8205fef0e5aa53d46642efd0bdd5dfb9e04df8
parent1672be7f66050579fba457153f31bd38f08f6465 (diff)
downloadpyecsca-c2d2771a0ed5e4462962f603b8b0e93a88f188a3.tar.gz
pyecsca-c2d2771a0ed5e4462962f603b8b0e93a88f188a3.tar.bz2
pyecsca-c2d2771a0ed5e4462962f603b8b0e93a88f188a3.zip
Add affine multiply and move neutral to curve class.
-rw-r--r--pyecsca/ec/curve.py25
-rw-r--r--pyecsca/ec/curves.py5
-rw-r--r--pyecsca/ec/mult.py48
-rw-r--r--pyecsca/ec/params.py11
-rw-r--r--test/ec/test_curve.py18
-rw-r--r--test/ec/test_mult.py4
-rw-r--r--test/ec/test_params.py4
7 files changed, 70 insertions, 45 deletions
diff --git a/pyecsca/ec/curve.py b/pyecsca/ec/curve.py
index b9a4770..797b288 100644
--- a/pyecsca/ec/curve.py
+++ b/pyecsca/ec/curve.py
@@ -1,4 +1,5 @@
from ast import Module
+from copy import copy
from typing import MutableMapping, Union, List
from public import public
@@ -11,13 +12,15 @@ from .point import Point
@public
class EllipticCurve(object):
+ """An elliptic curve."""
model: CurveModel
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]]):
+ prime: int, neutral: Point, 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()):
@@ -33,6 +36,7 @@ class EllipticCurve(object):
else:
value = Mod(value, prime)
self.parameters[name] = value
+ self.neutral = neutral
def _execute_base_formulas(self, formulas: List[Module], *points: Point) -> Point:
for point in points:
@@ -45,7 +49,7 @@ class EllipticCurve(object):
locals.update(self.parameters)
for line in formulas:
exec(compile(line, "", mode="exec"), None, locals)
- return Point(AffineCoordinateModel(self), x=locals["x"], y=locals["y"])
+ return Point(AffineCoordinateModel(self.model), x=locals["x"], y=locals["y"])
def affine_add(self, one: Point, other: Point) -> Point:
return self._execute_base_formulas(self.model.base_addition, one, other)
@@ -56,10 +60,27 @@ class EllipticCurve(object):
def affine_negate(self, one: Point) -> Point:
return self._execute_base_formulas(self.model.base_negation, one)
+ def affine_multiply(self, point: Point, scalar: int) -> Point:
+ if point.coordinate_model.curve_model != self.model:
+ raise ValueError
+ if not isinstance(point.coordinate_model, AffineCoordinateModel):
+ raise ValueError
+ q = copy(point)
+ r = copy(point)
+
+ for i in range(scalar.bit_length() - 2, -1, -1):
+ r = self.affine_double(r)
+ if scalar & (1 << i) != 0:
+ r = self.affine_add(r, q)
+ return r
+
@property
def neutral_is_affine(self):
return bool(self.model.base_neutral)
+ def is_neutral(self, point: Point) -> bool:
+ return self.neutral == point
+
def is_on_curve(self, point: Point) -> bool:
if point.coordinate_model.curve_model != self.model:
return False
diff --git a/pyecsca/ec/curves.py b/pyecsca/ec/curves.py
index e002a9c..9240be2 100644
--- a/pyecsca/ec/curves.py
+++ b/pyecsca/ec/curves.py
@@ -68,9 +68,8 @@ def get_params(category: str, name: str, coords: str) -> DomainParameters:
for param, value in locals.items():
if params[param] != value:
raise ValueError(f"Coordinate model {coord_model} has an unsatisifed assumption on the {param} parameter (= {value}).")
- elliptic_curve = EllipticCurve(model, coord_model, field, params)
+ elliptic_curve = EllipticCurve(model, coord_model, field, InfinityPoint(coord_model), params)
affine = Point(AffineCoordinateModel(model), x=Mod(int(curve["generator"]["x"], 16), field),
y=Mod(int(curve["generator"]["y"], 16), field))
generator = Point.from_affine(coord_model, affine)
- return DomainParameters(elliptic_curve, generator, InfinityPoint(coord_model), order, cofactor,
- name, category)
+ return DomainParameters(elliptic_curve, generator, order, cofactor, name, category)
diff --git a/pyecsca/ec/mult.py b/pyecsca/ec/mult.py
index 710594c..def7dab 100644
--- a/pyecsca/ec/mult.py
+++ b/pyecsca/ec/mult.py
@@ -54,9 +54,9 @@ class ScalarMultiplier(ABC):
if "add" not in self.formulas:
raise NotImplementedError
if self.short_circuit:
- if one == self._params.neutral:
+ if one == self._params.curve.neutral:
return copy(other)
- if other == self._params.neutral:
+ if other == self._params.curve.neutral:
return copy(one)
return self.formulas["add"](one, other, **self._params.curve.parameters)[0]
@@ -64,7 +64,7 @@ class ScalarMultiplier(ABC):
if "dbl" not in self.formulas:
raise NotImplementedError
if self.short_circuit:
- if point == self._params.neutral:
+ if point == self._params.curve.neutral:
return copy(point)
return self.formulas["dbl"](point, **self._params.curve.parameters)[0]
@@ -77,9 +77,9 @@ class ScalarMultiplier(ABC):
if "ladd" not in self.formulas:
raise NotImplementedError
if self.short_circuit:
- if to_dbl == self._params.neutral:
+ if to_dbl == self._params.curve.neutral:
return to_dbl, to_add
- if to_add == self._params.neutral:
+ if to_add == self._params.curve.neutral:
return self._dbl(to_dbl), to_dbl
return self.formulas["ladd"](start, to_dbl, to_add, **self._params.curve.parameters)
@@ -87,9 +87,9 @@ class ScalarMultiplier(ABC):
if "dadd" not in self.formulas:
raise NotImplementedError
if self.short_circuit:
- if one == self._params.neutral:
+ if one == self._params.curve.neutral:
return copy(other)
- if other == self._params.neutral:
+ if other == self._params.curve.neutral:
return copy(one)
return self.formulas["dadd"](start, one, other, **self._params.curve.parameters)[0]
@@ -137,18 +137,19 @@ class LTRMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
if self.complete:
q = self._point
- r = copy(self._params.neutral)
+ r = copy(self._params.curve.neutral)
top = self._params.order.bit_length() - 1
else:
- q = copy(self._point) # self._dbl(self._point)
+ 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)
@@ -178,11 +179,12 @@ class RTLMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
q = self._point
- r = copy(self._params.neutral)
+ 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)
@@ -213,7 +215,7 @@ class CoronMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
q = self._point
p0 = copy(q)
for i in range(scalar.bit_length() - 2, -1, -1):
@@ -247,10 +249,10 @@ class LadderMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
q = self._point
if self.complete:
- p0 = copy(self._params.neutral)
+ p0 = copy(self._params.curve.neutral)
p1 = self._point
top = self._params.order.bit_length() - 1
else:
@@ -286,12 +288,12 @@ class SimpleLadderMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
if self.complete:
top = self._params.order.bit_length() - 1
else:
top = scalar.bit_length() - 1
- p0 = copy(self._params.neutral)
+ p0 = copy(self._params.curve.neutral)
p1 = copy(self._point)
for i in range(top, -1, -1):
if scalar & (1 << i) == 0:
@@ -324,13 +326,13 @@ class DifferentialLadderMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
if self.complete:
top = self._params.order.bit_length() - 1
else:
top = scalar.bit_length() - 1
q = self._point
- p0 = copy(self._params.neutral)
+ p0 = copy(self._params.curve.neutral)
p1 = copy(q)
for i in range(top, -1, -1):
if scalar & (1 << i) == 0:
@@ -366,9 +368,9 @@ class BinaryNAFMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
bnaf = naf(scalar)
- q = copy(self._params.neutral)
+ q = copy(self._params.curve.neutral)
for val in bnaf:
q = self._dbl(q)
if val == 1:
@@ -416,9 +418,9 @@ class WindowNAFMultiplier(ScalarMultiplier):
raise ValueError("ScalaMultiplier not initialized.")
with ScalarMultiplicationAction(self._point, scalar):
if scalar == 0:
- return copy(self._params.neutral)
+ return copy(self._params.curve.neutral)
naf = wnaf(scalar, self.width)
- q = copy(self._params.neutral)
+ q = copy(self._params.curve.neutral)
for val in naf:
q = self._dbl(q)
if val > 0:
diff --git a/pyecsca/ec/params.py b/pyecsca/ec/params.py
index 41d8a78..2b0538e 100644
--- a/pyecsca/ec/params.py
+++ b/pyecsca/ec/params.py
@@ -11,29 +11,24 @@ class DomainParameters(object):
"""Domain parameters which specify a subgroup on an elliptic curve."""
curve: EllipticCurve
generator: Point
- neutral: Point
order: int
cofactor: int
name: Optional[str]
category: Optional[str]
- def __init__(self, curve: EllipticCurve, generator: Point, neutral: Point, order: int,
+ def __init__(self, curve: EllipticCurve, generator: Point, order: int,
cofactor: int, name: Optional[str] = None, category: Optional[str] = None):
self.curve = curve
self.generator = generator
- self.neutral = neutral
self.order = order
self.cofactor = cofactor
self.name = name
self.category = category
- def is_neutral(self, point: Point) -> bool:
- return self.neutral == point
-
def __eq__(self, other):
if not isinstance(other, DomainParameters):
return False
- return self.curve == other.curve and self.generator == other.generator and self.neutral == other.neutral and self.order == other.order and self.cofactor == other.cofactor
+ return self.curve == other.curve and self.generator == other.generator and self.order == other.order and self.cofactor == other.cofactor
def __get_name(self):
if self.name and self.category:
@@ -51,4 +46,4 @@ class DomainParameters(object):
return f"{self.__class__.__name__}({name})"
def __repr__(self):
- return f"{self.__class__.__name__}({self.curve!r}, {self.generator!r}, {self.neutral!r}, {self.order}, {self.cofactor})"
+ return f"{self.__class__.__name__}({self.curve!r}, {self.generator!r}, {self.order}, {self.cofactor})"
diff --git a/test/ec/test_curve.py b/test/ec/test_curve.py
index fa935fa..9cbf652 100644
--- a/test/ec/test_curve.py
+++ b/test/ec/test_curve.py
@@ -4,7 +4,7 @@ from pyecsca.ec.curve import EllipticCurve
from pyecsca.ec.curves import get_params
from pyecsca.ec.mod import Mod
from pyecsca.ec.model import MontgomeryModel
-from pyecsca.ec.point import Point
+from pyecsca.ec.point import Point, InfinityPoint
class CurveTests(TestCase):
@@ -18,16 +18,20 @@ class CurveTests(TestCase):
def test_init(self):
with self.assertRaises(ValueError):
EllipticCurve(MontgomeryModel(), self.secp128r1.curve.coordinate_model, 1,
- parameters={})
+ InfinityPoint(self.secp128r1.curve.coordinate_model), parameters={})
with self.assertRaises(ValueError):
EllipticCurve(self.secp128r1.curve.model, self.secp128r1.curve.coordinate_model, 15,
- parameters={"c": 0})
+ InfinityPoint(self.secp128r1.curve.coordinate_model), parameters={"c": 0})
with self.assertRaises(ValueError):
EllipticCurve(self.secp128r1.curve.model, self.secp128r1.curve.coordinate_model, 15,
+ InfinityPoint(self.secp128r1.curve.coordinate_model),
parameters={"a": Mod(1, 5), "b": Mod(2, 5)})
+ def test_is_neutral(self):
+ self.assertTrue(self.secp128r1.curve.is_neutral(InfinityPoint(self.secp128r1.curve.coordinate_model)))
+
def test_is_on_curve(self):
pt = Point(self.secp128r1.curve.coordinate_model,
X=Mod(0x161ff7528b899b2d0c28607ca52c5b86, self.secp128r1.curve.prime),
@@ -50,6 +54,14 @@ class CurveTests(TestCase):
def test_affine_negate(self):
self.assertIsNotNone(self.secp128r1.curve.affine_negate(self.affine_base))
+ def test_affine_multiply(self):
+ expected = self.affine_base
+ expected = self.secp128r1.curve.affine_double(expected)
+ expected = self.secp128r1.curve.affine_double(expected)
+ expected = self.secp128r1.curve.affine_add(expected, self.affine_base)
+ expected = self.secp128r1.curve.affine_double(expected)
+ self.assertEqual(self.secp128r1.curve.affine_multiply(self.affine_base, 10), expected)
+
def test_neutral_is_affine(self):
self.assertFalse(self.secp128r1.curve.neutral_is_affine)
self.assertFalse(self.curve25519.curve.neutral_is_affine)
diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py
index 63c6d25..5b3683f 100644
--- a/test/ec/test_mult.py
+++ b/test/ec/test_mult.py
@@ -89,8 +89,8 @@ class ScalarMultiplierTests(TestCase):
self.do_basic_test(SimpleLadderMultiplier, self.secp128r1, self.base, add, dbl, scale)
@parameterized.expand([
- ("10", 15, True),
- ("10", 15, False),
+ ("15", 15, True),
+ ("15", 15, False),
("2355498743", 2355498743, True),
("2355498743", 2355498743, False),
("325385790209017329644351321912443757746", 325385790209017329644351321912443757746, True),
diff --git a/test/ec/test_params.py b/test/ec/test_params.py
index b4d55ee..57cabe3 100644
--- a/test/ec/test_params.py
+++ b/test/ec/test_params.py
@@ -1,7 +1,6 @@
from unittest import TestCase
from pyecsca.ec.curves import get_params
-from pyecsca.ec.point import InfinityPoint
class DomainParameterTests(TestCase):
@@ -10,9 +9,6 @@ class DomainParameterTests(TestCase):
self.secp128r1 = get_params("secg", "secp128r1", "projective")
self.curve25519 = get_params("other", "Curve25519", "xz")
- def test_is_neutral(self):
- assert self.secp128r1.is_neutral(InfinityPoint(self.secp128r1.curve.coordinate_model))
-
def test_eq(self):
self.assertEqual(self.secp128r1, self.secp128r1)
self.assertNotEqual(self.secp128r1, self.curve25519)