diff options
Diffstat (limited to 'pyecsca/ec/mult/window.py')
| -rw-r--r-- | pyecsca/ec/mult/window.py | 170 |
1 files changed, 148 insertions, 22 deletions
diff --git a/pyecsca/ec/mult/window.py b/pyecsca/ec/mult/window.py index f85a58a..d025cc1 100644 --- a/pyecsca/ec/mult/window.py +++ b/pyecsca/ec/mult/window.py @@ -4,15 +4,22 @@ from typing import Optional, MutableMapping from public import public from ..params import DomainParameters -from .base import ScalarMultiplier, AccumulationOrder, ScalarMultiplicationAction, PrecomputationAction, \ - ProcessingDirection, AccumulatorMultiplier +from .base import ( + ScalarMultiplier, + AccumulationOrder, + ScalarMultiplicationAction, + PrecomputationAction, + ProcessingDirection, + AccumulatorMultiplier, +) from ..formula import ( AdditionFormula, DoublingFormula, ScalingFormula, + NegationFormula, ) from ..point import Point -from ..scalar import convert_base, sliding_window_rtl, sliding_window_ltr +from ..scalar import convert_base, sliding_window_rtl, sliding_window_ltr, booth_window @public @@ -34,17 +41,21 @@ class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier): _points: MutableMapping[int, Point] def __init__( - self, - add: AdditionFormula, - dbl: DoublingFormula, - width: int, - scl: Optional[ScalingFormula] = None, - recoding_direction: ProcessingDirection = ProcessingDirection.LTR, - accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, - short_circuit: bool = True, + self, + add: AdditionFormula, + dbl: DoublingFormula, + width: int, + scl: Optional[ScalingFormula] = None, + recoding_direction: ProcessingDirection = ProcessingDirection.LTR, + accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, + short_circuit: bool = True, ): super().__init__( - short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, scl=scl + short_circuit=short_circuit, + accumulation_order=accumulation_order, + add=add, + dbl=dbl, + scl=scl, ) self.width = width self.recoding_direction = recoding_direction @@ -55,7 +66,13 @@ class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier): def __eq__(self, other): if not isinstance(other, SlidingWindowMultiplier): return False - return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.width == other.width and self.recoding_direction == other.recoding_direction and self.accumulation_order == other.accumulation_order + return ( + self.formulas == other.formulas + and self.short_circuit == other.short_circuit + and self.width == other.width + and self.recoding_direction == other.recoding_direction + and self.accumulation_order == other.accumulation_order + ) def __repr__(self): return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, width={self.width}, recoding_direction={self.recoding_direction.name}, accumulation_order={self.accumulation_order.name})" @@ -112,16 +129,20 @@ class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier): _points: MutableMapping[int, Point] def __init__( - self, - add: AdditionFormula, - dbl: DoublingFormula, - m: int, - scl: Optional[ScalingFormula] = None, - accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, - short_circuit: bool = True, + self, + add: AdditionFormula, + dbl: DoublingFormula, + m: int, + scl: Optional[ScalingFormula] = None, + accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, + short_circuit: bool = True, ): super().__init__( - short_circuit=short_circuit, accumulation_order=accumulation_order, add=add, dbl=dbl, scl=scl + short_circuit=short_circuit, + accumulation_order=accumulation_order, + add=add, + dbl=dbl, + scl=scl, ) if m < 2: raise ValueError("Invalid base.") @@ -134,7 +155,12 @@ class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier): def __eq__(self, other): if not isinstance(other, FixedWindowLTRMultiplier): return False - return self.formulas == other.formulas and self.short_circuit == other.short_circuit and self.m == other.m and self.accumulation_order == other.accumulation_order + return ( + self.formulas == other.formulas + and self.short_circuit == other.short_circuit + and self.m == other.m + and self.accumulation_order == other.accumulation_order + ) def __repr__(self): return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, m={self.m}, accumulation_order={self.accumulation_order.name})" @@ -180,3 +206,103 @@ class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier): if "scl" in self.formulas: q = self._scl(q) return action.exit(q) + + +@public +class WindowBoothMultiplier(AccumulatorMultiplier, ScalarMultiplier): + """ + + :param short_circuit: Whether the use of formulas will be guarded by short-circuit on inputs + of the point at infinity. + :param width: The width of the window. + :param accumulation_order: The order of accumulation of points. + :param precompute_negation: Whether to precompute the negation of the precomputed points as well. + It is computed on the fly otherwise. + """ + + requires = {AdditionFormula, DoublingFormula, NegationFormula} + optionals = {ScalingFormula} + _points: MutableMapping[int, Point] + _points_neg: MutableMapping[int, Point] + precompute_negation: bool = False + """Whether to precompute the negation of the precomputed points as well.""" + width: int + """The width of the window.""" + + def __init__( + self, + add: AdditionFormula, + dbl: DoublingFormula, + neg: NegationFormula, + width: int, + scl: Optional[ScalingFormula] = None, + accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR, + precompute_negation: bool = False, + short_circuit: bool = True, + ): + super().__init__( + short_circuit=short_circuit, + accumulation_order=accumulation_order, + add=add, + dbl=dbl, + neg=neg, + scl=scl, + ) + self.width = width + self.precompute_negation = precompute_negation + + def __hash__(self): + return id(self) + + def __eq__(self, other): + if not isinstance(other, WindowBoothMultiplier): + return False + return ( + self.formulas == other.formulas + and self.short_circuit == other.short_circuit + and self.width == other.width + and self.precompute_negation == other.precompute_negation + and self.accumulation_order == other.accumulation_order + ) + + def __repr__(self): + return f"{self.__class__.__name__}({', '.join(map(str, self.formulas.values()))}, short_circuit={self.short_circuit}, width={self.width}, precompute_negation={self.precompute_negation}, accumulation_order={self.accumulation_order.name})" + + def init(self, params: DomainParameters, point: Point): + with PrecomputationAction(params, point): + super().init(params, point) + double_point = self._dbl(point) + self._points = {1: point, 2: double_point} + if self.precompute_negation: + self._points_neg = {1: self._neg(point), 2: self._neg(double_point)} + current_point = double_point + for i in range(3, 2 ** (self.width - 1) + 1): + current_point = self._add(current_point, point) + self._points[i] = current_point + if self.precompute_negation: + self._points_neg[i] = self._neg(current_point) + + def multiply(self, scalar: int) -> Point: + if not self._initialized: + raise ValueError("ScalarMultiplier not initialized.") + with ScalarMultiplicationAction(self._point, scalar) as action: + if scalar == 0: + return action.exit(copy(self._params.curve.neutral)) + scalar_booth = booth_window( + scalar, self.width, self._params.order.bit_length() + ) + q = copy(self._params.curve.neutral) + for val in scalar_booth: + for _ in range(self.width): + q = self._dbl(q) + if val > 0: + q = self._accumulate(q, self._points[val]) + elif val < 0: + if self.precompute_negation: + neg = self._points_neg[-val] + else: + neg = self._neg(self._points[-val]) + q = self._accumulate(q, neg) + if "scl" in self.formulas: + q = self._scl(q) + return action.exit(q) |