diff options
| author | J08nY | 2024-08-28 12:37:38 +0200 |
|---|---|---|
| committer | J08nY | 2024-08-28 12:37:38 +0200 |
| commit | 979d86979313de02c4dab71f99ce1c5dddd5877a (patch) | |
| tree | 3f6e8930b0d15e293ae16ee2074e41ad8cf40f8c | |
| parent | f5af7b538692cdfdeab6f71751149b496062fde4 (diff) | |
| download | pyecsca-979d86979313de02c4dab71f99ce1c5dddd5877a.tar.gz pyecsca-979d86979313de02c4dab71f99ce1c5dddd5877a.tar.zst pyecsca-979d86979313de02c4dab71f99ce1c5dddd5877a.zip | |
| -rw-r--r-- | .pre-commit-config.yaml | 2 | ||||
| -rw-r--r-- | pyecsca/ec/mod/base.py | 11 | ||||
| -rw-r--r-- | pyecsca/ec/mult/base.py | 6 | ||||
| -rw-r--r-- | pyecsca/ec/mult/binary.py | 4 | ||||
| -rw-r--r-- | pyecsca/ec/mult/comb.py | 4 | ||||
| -rw-r--r-- | pyecsca/ec/mult/fixed.py | 2 | ||||
| -rw-r--r-- | pyecsca/ec/mult/ladder.py | 101 | ||||
| -rw-r--r-- | pyecsca/ec/mult/naf.py | 4 | ||||
| -rw-r--r-- | pyecsca/ec/mult/window.py | 6 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 20 | ||||
| -rw-r--r-- | test/ec/test_key_agreement.py | 34 | ||||
| -rw-r--r-- | test/sca/test_rpa.py | 66 |
12 files changed, 189 insertions, 71 deletions
diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml index 77da1c1..8c36dae 100644 --- a/.pre-commit-config.yaml +++ b/.pre-commit-config.yaml @@ -21,7 +21,7 @@ repos: - "python-flint" args: [--ignore-missing-imports, --show-error-codes, --namespace-packages, --explicit-package-bases, --check-untyped-defs] - repo: https://github.com/PyCQA/flake8 - rev: 6.0.0 + rev: 7.0.0 hooks: - id: flake8 args: ["--extend-ignore=E501,F405,F403,F401,E126,E203"] diff --git a/pyecsca/ec/mod/base.py b/pyecsca/ec/mod/base.py index 67e2b97..f5aab09 100644 --- a/pyecsca/ec/mod/base.py +++ b/pyecsca/ec/mod/base.py @@ -127,10 +127,8 @@ class Mod: """ An element x of ℤₙ. - .. note:: - This class dispatches to one of :py:class:`RawMod`, :py:class:`GMPMod` or :py:class:`FlintMod` - based on what packages are installed and what implementation is configured (see - :py:mod:`pyecsca.misc.cfg`). + .. attention: + Do not instantiate this class, it will not work, instead use the :py:func:`mod` function. Has all the usual special methods that upcast integers automatically: @@ -350,6 +348,11 @@ def mod(x: int, n: int) -> Mod: """ Construct a :py:class:`Mod`. + .. note:: + This function dispatches to one of :py:class:`RawMod`, :py:class:`GMPMod` or :py:class:`FlintMod` + based on what packages are installed and what implementation is configured (see + :py:mod:`pyecsca.misc.cfg`). + :param x: The value. :param n: The modulus. :return: A selected Mod implementation object. diff --git a/pyecsca/ec/mult/base.py b/pyecsca/ec/mult/base.py index 537f43e..469be39 100644 --- a/pyecsca/ec/mult/base.py +++ b/pyecsca/ec/mult/base.py @@ -34,15 +34,17 @@ class ScalarMultiplicationAction(ResultAction): """A scalar multiplication of a point on a curve by a scalar.""" point: Point + params: DomainParameters scalar: int - def __init__(self, point: Point, scalar: int): + def __init__(self, point: Point, params: DomainParameters, scalar: int): super().__init__() self.point = point + self.params = params self.scalar = scalar def __repr__(self): - return f"{self.__class__.__name__}({self.point}, {self.scalar})" + return f"{self.__class__.__name__}({self.point}, {self.params}, {self.scalar})" @public diff --git a/pyecsca/ec/mult/binary.py b/pyecsca/ec/mult/binary.py index 9b6a07a..5b6bed7 100644 --- a/pyecsca/ec/mult/binary.py +++ b/pyecsca/ec/mult/binary.py @@ -129,7 +129,7 @@ class DoubleAndAddMultiplier(AccumulatorMultiplier, ScalarMultiplier, ABC): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) if self.direction is ProcessingDirection.LTR: @@ -246,7 +246,7 @@ class CoronMultiplier(ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) q = self._point diff --git a/pyecsca/ec/mult/comb.py b/pyecsca/ec/mult/comb.py index 8cea19c..9557fe6 100644 --- a/pyecsca/ec/mult/comb.py +++ b/pyecsca/ec/mult/comb.py @@ -100,7 +100,7 @@ class BGMWMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) a = copy(self._params.curve.neutral) @@ -202,7 +202,7 @@ class CombMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) q = copy(self._params.curve.neutral) diff --git a/pyecsca/ec/mult/fixed.py b/pyecsca/ec/mult/fixed.py index afd02e5..2c60be2 100644 --- a/pyecsca/ec/mult/fixed.py +++ b/pyecsca/ec/mult/fixed.py @@ -132,7 +132,7 @@ class FullPrecompMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) if self.direction is ProcessingDirection.LTR: diff --git a/pyecsca/ec/mult/ladder.py b/pyecsca/ec/mult/ladder.py index f2939af..9f31b7f 100644 --- a/pyecsca/ec/mult/ladder.py +++ b/pyecsca/ec/mult/ladder.py @@ -1,4 +1,5 @@ """Provides ladder-based scalar multipliers, either using the ladder formula, or (diffadd, dbl) or (add, dbl).""" + from copy import copy from typing import Optional from public import public @@ -24,12 +25,15 @@ class LadderMultiplier(ScalarMultiplier): :param short_circuit: Whether the use of formulas will be guarded by short-circuit on inputs of the point at infinity. :param complete: Whether it starts processing at full order-bit-length. + :param full: Whether it start processing at top bit of the scalar. """ requires = {LadderFormula} optionals = {DoublingFormula, ScalingFormula} complete: bool """Whether it starts processing at full order-bit-length.""" + full: bool + """Whether it start processing at top bit of the scalar.""" def __init__( self, @@ -38,17 +42,27 @@ class LadderMultiplier(ScalarMultiplier): scl: Optional[ScalingFormula] = None, complete: bool = True, short_circuit: bool = True, + full: bool = False, ): super().__init__(short_circuit=short_circuit, ladd=ladd, dbl=dbl, scl=scl) self.complete = complete + self.full = full + + if complete and full: + raise ValueError("Only one of `complete` and `full` can be set.") + if dbl is None: - if not complete: - raise ValueError("When complete is not set LadderMultiplier requires a doubling formula.") - if short_circuit: # complete = True - raise ValueError("When short_circuit is set LadderMultiplier requires a doubling formula.") + if short_circuit: + raise ValueError( + "When `short_circuit` is set LadderMultiplier requires a doubling formula." + ) + if not (complete or full): + raise ValueError( + "When neither `complete` nor `full` is not set LadderMultiplier requires a doubling formula." + ) def __hash__(self): - return hash((LadderMultiplier, super().__hash__(), self.complete)) + return hash((LadderMultiplier, super().__hash__(), self.complete, self.full)) def __eq__(self, other): if not isinstance(other, LadderMultiplier): @@ -57,15 +71,16 @@ class LadderMultiplier(ScalarMultiplier): self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.complete == other.complete + and self.full == other.full ) def __repr__(self): - return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete})" + return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete}, full={self.full})" def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) q = self._point @@ -73,6 +88,10 @@ class LadderMultiplier(ScalarMultiplier): p0 = copy(self._params.curve.neutral) p1 = self._point top = self._params.full_order.bit_length() - 1 + elif self.full: + p0 = copy(self._params.curve.neutral) + p1 = self._point + top = scalar.bit_length() - 1 else: p0 = copy(q) p1 = self._dbl(q) @@ -97,12 +116,15 @@ class SwapLadderMultiplier(ScalarMultiplier): :param short_circuit: Whether the use of formulas will be guarded by short-circuit on inputs of the point at infinity. :param complete: Whether it starts processing at full order-bit-length. + :param full: Whether it start processing at top bit of the scalar. """ requires = {LadderFormula} optionals = {DoublingFormula, ScalingFormula} complete: bool """Whether it starts processing at full order-bit-length.""" + full: bool + """Whether it start processing at top bit of the scalar.""" def __init__( self, @@ -111,34 +133,45 @@ class SwapLadderMultiplier(ScalarMultiplier): scl: Optional[ScalingFormula] = None, complete: bool = True, short_circuit: bool = True, + full: bool = False, ): super().__init__(short_circuit=short_circuit, ladd=ladd, dbl=dbl, scl=scl) self.complete = complete + self.full = full + + if complete and full: + raise ValueError("Only one of `complete` and `full` can be set.") + if dbl is None: - if not complete: - raise ValueError("When complete is not set SwapLadderMultiplier requires a doubling formula.") - if short_circuit: # complete = True - raise ValueError("When short_circuit is set SwapLadderMultiplier requires a doubling formula.") + if short_circuit: + raise ValueError( + "When `short_circuit` is set SwapLadderMultiplier requires a doubling formula." + ) + if not (complete or full): + raise ValueError( + "When neither `complete` nor `full` is not set SwapLadderMultiplier requires a doubling formula." + ) def __hash__(self): - return hash((LadderMultiplier, super().__hash__(), self.complete)) + return hash((SwapLadderMultiplier, super().__hash__(), self.complete, self.full)) def __eq__(self, other): - if not isinstance(other, LadderMultiplier): + if not isinstance(other, SwapLadderMultiplier): return False return ( self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.complete == other.complete + and self.full == other.full ) def __repr__(self): - return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete})" + return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete}, full={self.full})" def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) q = self._point @@ -146,6 +179,10 @@ class SwapLadderMultiplier(ScalarMultiplier): p0 = copy(self._params.curve.neutral) p1 = self._point top = self._params.full_order.bit_length() - 1 + elif self.full: + p0 = copy(self._params.curve.neutral) + p1 = self._point + top = scalar.bit_length() - 1 else: p0 = copy(q) p1 = self._dbl(q) @@ -207,11 +244,11 @@ class SimpleLadderMultiplier(ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) if self.complete: - top = self._params.order.bit_length() - 1 + top = self._params.full_order.bit_length() - 1 else: top = scalar.bit_length() - 1 p0 = copy(self._params.curve.neutral) @@ -242,6 +279,8 @@ class DifferentialLadderMultiplier(ScalarMultiplier): optionals = {ScalingFormula} complete: bool """Whether it starts processing at full order-bit-length.""" + full: bool + """Whether it start processing at top bit of the scalar.""" def __init__( self, @@ -250,12 +289,19 @@ class DifferentialLadderMultiplier(ScalarMultiplier): scl: Optional[ScalingFormula] = None, complete: bool = True, short_circuit: bool = True, + full: bool = False, ): super().__init__(short_circuit=short_circuit, dadd=dadd, dbl=dbl, scl=scl) self.complete = complete + self.full = full + + if complete and full: + raise ValueError("Only one of `complete` and `full` can be set.") def __hash__(self): - return hash((DifferentialLadderMultiplier, super().__hash__(), self.complete)) + return hash( + (DifferentialLadderMultiplier, super().__hash__(), self.complete, self.full) + ) def __eq__(self, other): if not isinstance(other, DifferentialLadderMultiplier): @@ -264,24 +310,31 @@ class DifferentialLadderMultiplier(ScalarMultiplier): self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.complete == other.complete + and self.full == other.full ) def __repr__(self): - return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete})" + return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, complete={self.complete}, full={self.full})" def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) + q = self._point if self.complete: + p0 = copy(self._params.curve.neutral) + p1 = copy(q) top = self._params.full_order.bit_length() - 1 - else: + elif self.full: + p0 = copy(self._params.curve.neutral) + p1 = copy(q) top = scalar.bit_length() - 1 - q = self._point - p0 = copy(self._params.curve.neutral) - p1 = copy(q) + else: + p0 = copy(q) + p1 = self._dbl(q) + top = scalar.bit_length() - 2 for i in range(top, -1, -1): if scalar & (1 << i) == 0: p1 = self._dadd(q, p0, p1) diff --git a/pyecsca/ec/mult/naf.py b/pyecsca/ec/mult/naf.py index 408f489..6fc9131 100644 --- a/pyecsca/ec/mult/naf.py +++ b/pyecsca/ec/mult/naf.py @@ -112,7 +112,7 @@ class BinaryNAFMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) scalar_naf = naf(scalar) @@ -210,7 +210,7 @@ class WindowNAFMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) scalar_naf = wnaf(scalar, self.width) diff --git a/pyecsca/ec/mult/window.py b/pyecsca/ec/mult/window.py index b003e40..c200cc5 100644 --- a/pyecsca/ec/mult/window.py +++ b/pyecsca/ec/mult/window.py @@ -103,7 +103,7 @@ class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) if self.recoding_direction is ProcessingDirection.LTR: @@ -213,7 +213,7 @@ class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) # General case (any m) and special case (m = 2^k) are handled together here @@ -313,7 +313,7 @@ class WindowBoothMultiplier(AccumulatorMultiplier, ScalarMultiplier): def multiply(self, scalar: int) -> Point: if not self._initialized: raise ValueError("ScalarMultiplier not initialized.") - with ScalarMultiplicationAction(self._point, scalar) as action: + with ScalarMultiplicationAction(self._point, self._params, scalar) as action: if scalar == 0: return action.exit(copy(self._params.curve.neutral)) scalar_booth = booth_window( diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index 0456eac..61a4237 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -8,6 +8,7 @@ from typing import MutableMapping, Optional, Callable, List, Set, cast from sympy import FF, sympify, Poly, symbols +from pyecsca.ec.error import NonInvertibleError from pyecsca.sca.re.base import RE from pyecsca.sca.re.tree import Tree, Map from pyecsca.ec.coordinates import AffineCoordinateModel @@ -39,6 +40,8 @@ class MultipleContext(Context): base: Optional[Point] """The base point that all the multiples are counted from.""" + neutral: Optional[Point] + """The neutral point used in the computation.""" points: MutableMapping[Point, int] """The mapping of points to the multiples they represent (e.g., base -> 1).""" parents: MutableMapping[Point, List[Point]] @@ -61,12 +64,14 @@ class MultipleContext(Context): if self.base != action.point: # If we are not building on top of it we have to forget stuff and set a new base and mapping. self.base = action.point - self.points = {self.base: 1} + self.neutral = action.params.curve.neutral + self.points = {self.base: 1, self.neutral: 0} self.parents = {self.base: []} self.formulas = {self.base: ""} else: self.base = action.point - self.points = {self.base: 1} + self.neutral = action.params.curve.neutral + self.points = {self.base: 1, self.neutral: 0} self.parents = {self.base: []} self.formulas = {self.base: ""} self.inside = True @@ -288,12 +293,21 @@ class RPA(RE): ) ) multiply_multiples |= set(map(lambda v: -v, multiply_multiples)) + # Use only the multiples from the correct part (init vs multiply) used = set() if use_init: used |= init_multiples if use_multiply: used |= multiply_multiples - mults_to_multiples[mult] = used + # Filter out the multiples that are non-invertible because they are not usable for RPA. + usable = set() + for elem in used: + try: + elem.inverse() + usable.add(elem) + except NonInvertibleError: + pass + mults_to_multiples[mult] = usable dmap = Map.from_sets(set(mults), mults_to_multiples) if tree is None: diff --git a/test/ec/test_key_agreement.py b/test/ec/test_key_agreement.py index 4afb2de..a045c49 100644 --- a/test/ec/test_key_agreement.py +++ b/test/ec/test_key_agreement.py @@ -105,9 +105,11 @@ def test_ka_secg(): (SwapLadderMultiplier, "ladd-1987-m", "dbl-1987-m", "scale"), (DifferentialLadderMultiplier, "dadd-1987-m", "dbl-1987-m", "scale"), ], + ids=["ladd", "swap", "diff"] ) -@pytest.mark.parametrize("complete", [True, False]) -@pytest.mark.parametrize("short_circuit", [True, False]) +@pytest.mark.parametrize("complete", [True, False], ids=["complete", ""]) +@pytest.mark.parametrize("short_circuit", [True, False], ids=["shorted", ""]) +@pytest.mark.parametrize("full", [True, False], ids=["full", ""]) @pytest.mark.parametrize( "scalar_hex,coord_hex,result_hex", [ @@ -135,7 +137,7 @@ def test_ka_secg(): ids=["RFC7748tv1", "RFC7748tv2", "RFC7748dh1", "RFC7748dh2"], ) def test_x25519( - curve25519, mult_args, complete, short_circuit, scalar_hex, coord_hex, result_hex + curve25519, mult_args, complete, short_circuit, full, scalar_hex, coord_hex, result_hex ): mult_class = mult_args[0] mult_formulas = list( @@ -143,9 +145,12 @@ def test_x25519( lambda name: curve25519.curve.coordinate_model.formulas[name], mult_args[1:] ) ) - multiplier = mult_class( - *mult_formulas, complete=complete, short_circuit=short_circuit - ) + try: + multiplier = mult_class( + *mult_formulas, complete=complete, short_circuit=short_circuit, full=full + ) + except ValueError: + return scalar = int.from_bytes(bytes.fromhex(scalar_hex), "little") coord = int.from_bytes(bytes.fromhex(coord_hex), "little") @@ -165,9 +170,11 @@ def test_x25519( (SwapLadderMultiplier, "ladd-1987-m", "dbl-1987-m", "scale"), (DifferentialLadderMultiplier, "dadd-1987-m", "dbl-1987-m", "scale"), ], + ids=["ladd", "swap", "diff"] ) -@pytest.mark.parametrize("complete", [True, False]) -@pytest.mark.parametrize("short_circuit", [True, False]) +@pytest.mark.parametrize("complete", [True, False], ids=["complete", ""]) +@pytest.mark.parametrize("short_circuit", [True, False], ids=["shorted", ""]) +@pytest.mark.parametrize("full", [True, False], ids=["full", ""]) @pytest.mark.parametrize( "scalar_hex,coord_hex,result_hex", [ @@ -195,15 +202,18 @@ def test_x25519( ids=["RFC7748tv1", "RFC7748tv2", "RFC7748dh1", "RFC7748dh2"], ) def test_x448( - curve448, mult_args, complete, short_circuit, scalar_hex, coord_hex, result_hex + curve448, mult_args, complete, short_circuit, full, scalar_hex, coord_hex, result_hex ): mult_class = mult_args[0] mult_formulas = list( map(lambda name: curve448.curve.coordinate_model.formulas[name], mult_args[1:]) ) - multiplier = mult_class( - *mult_formulas, complete=complete, short_circuit=short_circuit - ) + try: + multiplier = mult_class( + *mult_formulas, complete=complete, short_circuit=short_circuit, full=full + ) + except ValueError: + return scalar = int.from_bytes(bytes.fromhex(scalar_hex), "little") coord = int.from_bytes(bytes.fromhex(coord_hex), "little") diff --git a/test/sca/test_rpa.py b/test/sca/test_rpa.py index 2fa533d..8924eae 100644 --- a/test/sca/test_rpa.py +++ b/test/sca/test_rpa.py @@ -1,4 +1,5 @@ import pytest +from math import isqrt from pyecsca.ec.context import local from pyecsca.ec.model import ShortWeierstrassModel @@ -18,6 +19,9 @@ from pyecsca.ec.mult import ( BGMWMultiplier, CombMultiplier, WindowBoothMultiplier, + LadderMultiplier, + SwapLadderMultiplier, + DifferentialLadderMultiplier, ) from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point @@ -61,8 +65,6 @@ def rpa_params(model, coords): b = mod(0x37113EA591B04527, p) gx = mod(0x80D2D78FDDB97597, p) gy = mod(0x5586D818B7910930, p) - # (0x4880bcf620852a54, 0) RPA point - # (0, 0x6bed3155c9ada064) RPA point infty = Point(coords, X=mod(0, p), Y=mod(1, p), Z=mod(0, p)) g = Point(coords, X=gx, Y=gy, Z=mod(1, p)) @@ -83,22 +85,20 @@ def test_0y_point(rpa_params): @pytest.fixture() -def distinguish_params(model, coords): - p = 0xcb5e1d94a6168511 - a = mod(0xb166ca7d2dfbf69f, p) - b = mod(0x855bb40cb6937c4b, p) - gx = mod(0x253b2638bd13d6f4, p) - gy = mod(0x1e91a1a182287e71, p) - # (0x4880bcf620852a54, 0) RPA point - # (0, 0x6bed3155c9ada064) RPA point +def distinguish_params_sw(model, coords): + p = 0xCB5E1D94A6168511 + a = mod(0xB166CA7D2DFBF69F, p) + b = mod(0x855BB40CB6937C4B, p) + gx = mod(0x253B2638BD13D6F4, p) + gy = mod(0x1E91A1A182287E71, p) infty = Point(coords, X=mod(0, p), Y=mod(1, p), Z=mod(0, p)) g = Point(coords, X=gx, Y=gy, Z=mod(1, p)) curve = EllipticCurve(model, coords, p, infty, dict(a=a, b=b)) - return DomainParameters(curve, g, 0xcb5e1d94601a3ac5, 1) + return DomainParameters(curve, g, 0xCB5E1D94601A3AC5, 1) -def test_distinguish(distinguish_params, add, dbl, neg): +def test_distinguish_basic(distinguish_params_sw, add, dbl, neg): multipliers = [ LTRMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True, True), LTRMultiplier(add, dbl, None, True, AccumulationOrder.PeqPR, True, True), @@ -193,15 +193,51 @@ def test_distinguish(distinguish_params, add, dbl, neg): def simulated_oracle(scalar, affine_point): point = affine_point.to_model( - distinguish_params.curve.coordinate_model, distinguish_params.curve + distinguish_params_sw.curve.coordinate_model, + distinguish_params_sw.curve, ) with local(MultipleContext()) as ctx: - real_mult.init(distinguish_params, point) + real_mult.init(distinguish_params_sw, point) real_mult.multiply(scalar) return any( map(lambda P: P.X == 0 or P.Y == 0, sum(ctx.parents.values(), [])) ) - result = rpa_distinguish(distinguish_params, multipliers, simulated_oracle) + result = rpa_distinguish(distinguish_params_sw, multipliers, simulated_oracle) assert real_mult in result assert 1 == len(result) + + +def test_distinguish_ladders(curve25519): + ladd = curve25519.curve.coordinate_model.formulas["ladd-1987-m"] + dbl = curve25519.curve.coordinate_model.formulas["dbl-1987-m"] + dadd = curve25519.curve.coordinate_model.formulas["dadd-1987-m"] + + multipliers = [ + LadderMultiplier(ladd, None, None, True, False, False), + SwapLadderMultiplier(ladd, None, None, True, False, False), + LadderMultiplier(ladd, dbl, None, False, False, False), + SwapLadderMultiplier(ladd, dbl, None, False, False, False), + LadderMultiplier(ladd, None, None, False, False, True), + SwapLadderMultiplier(ladd, None, None, False, False, True), + DifferentialLadderMultiplier(dadd, dbl, None, True, False, False), + DifferentialLadderMultiplier(dadd, dbl, None, False, False, True), + DifferentialLadderMultiplier(dadd, dbl, None, False, False, False), + ] + for real_mult in multipliers: + + def simulated_oracle(scalar, affine_point): + point = affine_point.to_model( + curve25519.curve.coordinate_model, curve25519.curve + ) + with local(MultipleContext()) as ctx: + real_mult.init(curve25519, point) + real_mult.multiply(scalar) + return any(map(lambda P: P.X == 0, sum(ctx.parents.values(), []))) + + result = rpa_distinguish( + curve25519, multipliers, simulated_oracle, bound=isqrt(curve25519.order) + ) + assert real_mult in result + # These multipliers are not distinguishable by a binary RPA oracle. + # assert 1 == len(result) |
