path: root/pyecsca/ec/mult/window.py

"""Provides sliding window and fixed window scalar multipliers (including m-ary, for non power-of-2 m)."""
from copy import copy
from typing import Optional, MutableMapping
from public import public

from ..params import DomainParameters
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, booth_window


@public
class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier):
    """
    Sliding window scalar multiplier.

    :param width: The width of the sliding-window recoding.
    :param recoding_direction: The direction for the sliding-window recoding.
    :param accumulation_order: The order of accumulation of points.
    """

    requires = {AdditionFormula, DoublingFormula}
    optionals = {ScalingFormula}
    width: int
    """The width of the sliding-window recoding."""
    recoding_direction: ProcessingDirection
    """The direction for the sliding-window recoding."""
    _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,
    ):
        super().__init__(
            short_circuit=short_circuit,
            accumulation_order=accumulation_order,
            add=add,
            dbl=dbl,
            scl=scl,
        )
        self.width = width
        self.recoding_direction = recoding_direction

    def __hash__(self):
        return id(self)

    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
        )

    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})"

    def init(self, params: DomainParameters, point: Point):
        with PrecomputationAction(params, point):
            super().init(params, point)
            self._points = {}
            current_point = point
            double_point = self._dbl(point)
            for i in range(0, 2 ** (self.width - 1)):
                self._points[2 * i + 1] = current_point
                current_point = self._add(current_point, double_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))
            if self.recoding_direction is ProcessingDirection.LTR:
                scalar_sliding = sliding_window_ltr(scalar, self.width)
            elif self.recoding_direction is ProcessingDirection.RTL:
                scalar_sliding = sliding_window_rtl(scalar, self.width)
            q = copy(self._params.curve.neutral)
            for val in scalar_sliding:
                q = self._dbl(q)
                if val != 0:
                    q = self._accumulate(q, self._points[val])
            if "scl" in self.formulas:
                q = self._scl(q)
            return action.exit(q)


@public
class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier):
    """
    Like LTRMultiplier, but m-ary, not binary.

    For `m` a power-of-2 this is a fixed window multiplier
    that works on `log_2(m)` wide windows and uses only doublings
    to perform the multiplication-by-m between each window addition.

    For other `m` values, this is the m-ary multiplier.

    :param m: The arity of the multiplier.
    :param accumulation_order: The order of accumulation of points.
    """

    requires = {AdditionFormula, DoublingFormula}
    optionals = {ScalingFormula}
    m: int
    """The arity of the multiplier."""
    _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,
    ):
        super().__init__(
            short_circuit=short_circuit,
            accumulation_order=accumulation_order,
            add=add,
            dbl=dbl,
            scl=scl,
        )
        if m < 2:
            raise ValueError("Invalid base.")
        self.accumulation_order = accumulation_order
        self.m = m

    def __hash__(self):
        return id(self)

    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
        )

    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})"

    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}
            current_point = double_point
            for i in range(3, self.m):
                current_point = self._add(current_point, point)
                self._points[i] = current_point

    def _mult_m(self, point: Point) -> Point:
        if self.m & (self.m - 1) == 0:
            # Power of 2
            q = point
            for _ in range(self.m.bit_length() - 1):
                q = self._dbl(q)
        else:
            # Not power of 2
            r = copy(point)
            q = self._dbl(point)
            # TODO: This could be made via a different chain.
            for _ in range(self.m - 2):
                q = self._accumulate(q, r)
        return q

    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))
            # General case (any m) and special case (m = 2^k) are handled together here
            converted = convert_base(scalar, self.m)
            q = copy(self._params.curve.neutral)
            for digit in reversed(converted):
                q = self._mult_m(q)
                if digit != 0:
                    q = self._accumulate(q, self._points[digit])
            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)