From 67723ffde0c37c6da87c06dbb36983ebd14b4926 Mon Sep 17 00:00:00 2001 From: J08nY Date: Fri, 1 Dec 2023 16:32:15 +0100 Subject: Add Window multiplier with Booth recoding. --- docs/references.rst | 2 + pyecsca/ec/mult/window.py | 170 ++++++++++++++++++--- pyecsca/ec/scalar.py | 63 +++++++- test/ec/test_configuration.py | 2 +- test/ec/test_mult.py | 345 +++++++++++++++++++++++++++++------------- test/ec/test_scalar.py | 26 +++- test/sca/test_rpa.py | 90 ++++++++--- 7 files changed, 544 insertions(+), 154 deletions(-) diff --git a/docs/references.rst b/docs/references.rst index de3beae..675a13a 100644 --- a/docs/references.rst +++ b/docs/references.rst @@ -16,3 +16,5 @@ References .. [CO2002] Jean-Sébastien Coron. Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, https://link.springer.com/chapter/10.1007/3-540-48059-5_25 .. [DJB02] D.J. Bernstein: Pippenger's Exponentiation Algorithm, https://cr.yp.to/papers/pippenger.pdf .. [SG14] Shay Gueron & Vlad Krasnov. Fast prime field elliptic-curve cryptography with 256-bit primes, https://link.springer.com/article/10.1007/s13389-014-0090-x +.. [B51] Andrew D. Booth. A signed binary multiplication technique. +.. [M61] O. L. Macsorley. High-speed arithmetic in binary computers. 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) diff --git a/pyecsca/ec/scalar.py b/pyecsca/ec/scalar.py index 3fadc00..af5a6ab 100644 --- a/pyecsca/ec/scalar.py +++ b/pyecsca/ec/scalar.py @@ -1,5 +1,5 @@ """Provides functions for computing various scalar representations (like NAF, or different bases).""" -from typing import List +from typing import List, Tuple, Literal from itertools import dropwhile from public import public @@ -11,7 +11,7 @@ def convert_base(i: int, base: int) -> List[int]: :param i: The scalar. :param base: The base. - :return: The resulting digit list. + :return: The resulting digit list (little-endian). """ if i == 0: return [0] @@ -131,3 +131,62 @@ def naf(k: int) -> List[int]: :return: The NAF. """ return wnaf(k, 2) + + +@public +def booth(k: int) -> List[int]: + """ + Original Booth binary recoding, from [B51]_. + + :param k: The scalar to recode. + :return: The recoded list of digits (0, 1, -1), little-endian. + """ + res = [] + for i in range(k.bit_length()): + a_i = (k >> i) & 1 + b_i = (k >> (i + 1)) & 1 + res.append(a_i - b_i) + res.insert(0, -(k & 1)) + return res + + +@public +def booth_word(digit: int, w: int) -> int: + """ + Modified Booth recoding, from [M61]_ and BoringSSL NIST impl. + + Needs `w+1` bits of scalar in digit, but the one bit is overlapping (window size is `w`). + + :param digit: + :param w: + :return: + """ + if digit.bit_length() > (w + 1): + raise ValueError("Invalid digit, cannot be larger than w + 1 bits.") + s = ~((digit >> w) - 1) + d = (1 << (w + 1)) - digit - 1 + d = (d & s) | (digit & ~s) + d = (d >> 1) + (d & 1) + + return -d if s else d + + +@public +def booth_window(k: int, w: int, blen: int) -> List[int]: + """ + Recode a whole scalar using Booth recoding as in BoringSSL. + + :param k: The scalar. + :param w: The window size. + :param blen: The bit-length of the group. + :return: The big-endian recoding + """ + mask = (1 << (w + 1)) - 1 + res = [] + for i in range(blen + (w - (blen % w) - 1), -1, -w): + if i >= w: + d = (k >> (i - w)) & mask + else: + d = (k << (w - i)) & mask + res.append(booth_word(d, w)) + return res diff --git a/test/ec/test_configuration.py b/test/ec/test_configuration.py index 54cc53a..15c9471 100644 --- a/test/ec/test_configuration.py +++ b/test/ec/test_configuration.py @@ -33,7 +33,7 @@ def test_weierstrass_projective(base_independents): coords = model.coordinates["projective"] configs = list(all_configurations(model=model, coords=coords, **base_independents)) assert len(set(map(lambda cfg: cfg.scalarmult, configs))) == len(configs) - assert len(configs) == 11360 + assert len(configs) == 12640 def test_mult_class(base_independents): diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py index 20e1c95..d5e3146 100644 --- a/test/ec/test_mult.py +++ b/test/ec/test_mult.py @@ -20,6 +20,7 @@ from pyecsca.ec.mult import ( SlidingWindowMultiplier, BGMWMultiplier, CombMultiplier, + WindowBoothMultiplier, ) from pyecsca.ec.mult.fixed import FullPrecompMultiplier from pyecsca.ec.point import InfinityPoint, Point @@ -36,12 +37,9 @@ def assert_pt_equality(one: Point, other: Point, scale): assert one.equals(other) -def do_basic_test( - mult_class, params, base, add, dbl, scale, neg=None, **kwargs -): +def do_basic_test(mult_class, params, base, add, dbl, scale, neg=None, **kwargs): mult = mult_class( - *get_formulas(params.curve.coordinate_model, add, dbl, neg, scale), - **kwargs + *get_formulas(params.curve.coordinate_model, add, dbl, neg, scale), **kwargs ) mult.init(params, base) res = mult.multiply(314) @@ -59,26 +57,28 @@ def do_basic_test( return res -@pytest.mark.parametrize("add,dbl,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), - ("add-2015-rcb", "dbl-2015-rcb", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", None), - ]) +@pytest.mark.parametrize( + "add,dbl,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), + ("add-2015-rcb", "dbl-2015-rcb", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", None), + ], +) def test_rtl(secp128r1, add, dbl, scale): do_basic_test(RTLMultiplier, secp128r1, secp128r1.generator, add, dbl, scale) -@pytest.mark.parametrize("add,dbl,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), - ("add-2015-rcb", "dbl-2015-rcb", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", None), - ]) +@pytest.mark.parametrize( + "add,dbl,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), + ("add-2015-rcb", "dbl-2015-rcb", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", None), + ], +) def test_ltr(secp128r1, add, dbl, scale): - a = do_basic_test( - LTRMultiplier, secp128r1, secp128r1.generator, add, dbl, scale - ) + a = do_basic_test(LTRMultiplier, secp128r1, secp128r1.generator, add, dbl, scale) b = do_basic_test( LTRMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, always=True ) @@ -100,22 +100,35 @@ def test_ltr(secp128r1, add, dbl, scale): assert_pt_equality(c, d, scale) -@pytest.mark.parametrize("add,dbl,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), - ("add-2015-rcb", "dbl-2015-rcb", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", None), - ]) +@pytest.mark.parametrize( + "add,dbl,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), + ("add-2015-rcb", "dbl-2015-rcb", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", None), + ], +) def test_doubleandadd(secp128r1, add, dbl, scale): a = do_basic_test( DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale ) b = do_basic_test( - DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, direction=ProcessingDirection.RTL + DoubleAndAddMultiplier, + secp128r1, + secp128r1.generator, + add, + dbl, + scale, + direction=ProcessingDirection.RTL, ) c = do_basic_test( - DoubleAndAddMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, - accumulation_order=AccumulationOrder.PeqPR + DoubleAndAddMultiplier, + secp128r1, + secp128r1.generator, + add, + dbl, + scale, + accumulation_order=AccumulationOrder.PeqPR, ) d = do_basic_test( DoubleAndAddMultiplier, @@ -132,13 +145,14 @@ def test_doubleandadd(secp128r1, add, dbl, scale): assert_pt_equality(c, d, scale) -@pytest.mark.parametrize("add,dbl,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), - ("add-2015-rcb", "dbl-2015-rcb", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", None), - ] - ) +@pytest.mark.parametrize( + "add,dbl,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), + ("add-2015-rcb", "dbl-2015-rcb", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", None), + ], +) def test_coron(secp128r1, add, dbl, scale): do_basic_test(CoronMultiplier, secp128r1, secp128r1.generator, add, dbl, scale) @@ -164,27 +178,31 @@ def test_ladder(curve25519): assert_pt_equality(a, b, True) -@pytest.mark.parametrize("add,dbl,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), - ("add-2015-rcb", "dbl-2015-rcb", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", None), - ]) +@pytest.mark.parametrize( + "add,dbl,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "z"), + ("add-2015-rcb", "dbl-2015-rcb", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", None), + ], +) def test_simple_ladder(secp128r1, add, dbl, scale): do_basic_test( SimpleLadderMultiplier, secp128r1, secp128r1.generator, add, dbl, scale ) -@pytest.mark.parametrize("num,complete", - [ - (15, True), - (15, False), - (2355498743, True), - (2355498743, False), - (325385790209017329644351321912443757746, True), - (325385790209017329644351321912443757746, False), - ]) +@pytest.mark.parametrize( + "num,complete", + [ + (15, True), + (15, False), + (2355498743, True), + (2355498743, False), + (325385790209017329644351321912443757746, True), + (325385790209017329644351321912443757746, False), + ], +) def test_ladder_differential(curve25519, num, complete): ladder = LadderMultiplier( curve25519.curve.coordinate_model.formulas["ladd-1987-m"], @@ -206,27 +224,31 @@ def test_ladder_differential(curve25519, num, complete): assert InfinityPoint(curve25519.curve.coordinate_model) == differential.multiply(0) -@pytest.mark.parametrize("add,dbl,neg,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", "z"), - ("add-2015-rcb", "dbl-2015-rcb", "neg", None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", None), - ]) +@pytest.mark.parametrize( + "add,dbl,neg,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", "z"), + ("add-2015-rcb", "dbl-2015-rcb", "neg", None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", None), + ], +) def test_binary_naf(secp128r1, add, dbl, neg, scale): do_basic_test( BinaryNAFMultiplier, secp128r1, secp128r1.generator, add, dbl, scale, neg ) -@pytest.mark.parametrize("add,dbl,neg,width,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 3, "z"), - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 3, None), - ("add-2015-rcb", "dbl-2015-rcb", "neg", 3, None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, "z"), - ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, None), - ("add-2015-rcb", "dbl-2015-rcb", "neg", 5, None), - ]) +@pytest.mark.parametrize( + "add,dbl,neg,width,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 3, "z"), + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 3, None), + ("add-2015-rcb", "dbl-2015-rcb", "neg", 3, None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, "z"), + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, None), + ("add-2015-rcb", "dbl-2015-rcb", "neg", 5, None), + ], +) def test_window_naf(secp128r1, add, dbl, neg, width, scale): formulas = get_formulas(secp128r1.curve.coordinate_model, add, dbl, neg, scale) mult = WindowNAFMultiplier(*formulas[:3], width, *formulas[3:]) @@ -247,12 +269,14 @@ def test_window_naf(secp128r1, add, dbl, neg, width, scale): assert_pt_equality(res_precompute, res, scale) -@pytest.mark.parametrize("add,dbl,width,scale", - [ - ("add-1998-cmo-2", "dbl-1998-cmo-2", 5, "z"), - ("add-2015-rcb", "dbl-2015-rcb", 5, None), - ("add-1998-cmo-2", "dbl-1998-cmo-2", 5, None), - ]) +@pytest.mark.parametrize( + "add,dbl,width,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", 5, "z"), + ("add-2015-rcb", "dbl-2015-rcb", 5, None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", 5, None), + ], +) def test_fixed_window(secp128r1, add, dbl, width, scale): formulas = get_formulas(secp128r1.curve.coordinate_model, add, dbl, scale) mult = FixedWindowLTRMultiplier(*formulas[:2], width, *formulas[2:]) @@ -266,6 +290,27 @@ def test_fixed_window(secp128r1, add, dbl, width, scale): assert InfinityPoint(secp128r1.curve.coordinate_model) == mult.multiply(0) +@pytest.mark.parametrize( + "add,dbl,neg,width,scale", + [ + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, "z"), + ("add-2015-rcb", "dbl-2015-rcb", "neg", 5, None), + ("add-1998-cmo-2", "dbl-1998-cmo-2", "neg", 5, None), + ], +) +def test_booth_window(secp128r1, add, dbl, neg, width, scale): + formulas = get_formulas(secp128r1.curve.coordinate_model, add, dbl, neg, scale) + mult = WindowBoothMultiplier(*formulas[:3], width, *formulas[3:]) + mult.init(secp128r1, secp128r1.generator) + res = mult.multiply(157 * 789) + other = mult.multiply(157) + mult.init(secp128r1, other) + other = mult.multiply(789) + assert_pt_equality(res, other, scale) + mult.init(secp128r1, secp128r1.generator) + assert InfinityPoint(secp128r1.curve.coordinate_model) == mult.multiply(0) + + @pytest.fixture(params=["add-1998-cmo-2", "add-2015-rcb"]) def add(secp128r1, request): return secp128r1.curve.coordinate_model.formulas[request.param] @@ -276,53 +321,137 @@ def dbl(secp128r1, request): return secp128r1.curve.coordinate_model.formulas[request.param] -@pytest.mark.parametrize("num", [10, 2355498743, 325385790209017329644351321912443757746]) +@pytest.mark.parametrize( + "num", [10, 2355498743, 325385790209017329644351321912443757746] +) def test_basic_multipliers(secp128r1, num, add, dbl): neg = secp128r1.curve.coordinate_model.formulas["neg"] scale = secp128r1.curve.coordinate_model.formulas["z"] - ltr_options = {"always": (True, False), - "complete": (True, False), - "accumulation_order": tuple(AccumulationOrder)} - ltrs = [LTRMultiplier(add, dbl, scale, **dict(zip(ltr_options.keys(), combination))) for combination in product(*ltr_options.values())] + ltr_options = { + "always": (True, False), + "complete": (True, False), + "accumulation_order": tuple(AccumulationOrder), + } + ltrs = [ + LTRMultiplier(add, dbl, scale, **dict(zip(ltr_options.keys(), combination))) + for combination in product(*ltr_options.values()) + ] rtl_options = ltr_options - rtls = [RTLMultiplier(add, dbl, scale, **dict(zip(rtl_options.keys(), combination))) for combination in product(*rtl_options.values())] - bnaf_options = {"direction": tuple(ProcessingDirection), - "accumulation_order": tuple(AccumulationOrder)} - bnafs = [BinaryNAFMultiplier(add, dbl, neg, scale, **dict(zip(bnaf_options.keys(), combination))) for combination in product(*bnaf_options.values())] - wnaf_options = {"precompute_negation": (True, False), - "width": (3, 5), - "accumulation_order": tuple(AccumulationOrder)} - wnafs = [WindowNAFMultiplier(add, dbl, neg, scl=scale, **dict(zip(wnaf_options.keys(), combination))) for combination in product(*wnaf_options.values())] + rtls = [ + RTLMultiplier(add, dbl, scale, **dict(zip(rtl_options.keys(), combination))) + for combination in product(*rtl_options.values()) + ] + bnaf_options = { + "direction": tuple(ProcessingDirection), + "accumulation_order": tuple(AccumulationOrder), + } + bnafs = [ + BinaryNAFMultiplier( + add, dbl, neg, scale, **dict(zip(bnaf_options.keys(), combination)) + ) + for combination in product(*bnaf_options.values()) + ] + wnaf_options = { + "precompute_negation": (True, False), + "width": (3, 5), + "accumulation_order": tuple(AccumulationOrder), + } + wnafs = [ + WindowNAFMultiplier( + add, dbl, neg, scl=scale, **dict(zip(wnaf_options.keys(), combination)) + ) + for combination in product(*wnaf_options.values()) + ] + booth_options = { + "precompute_negation": (True, False), + "width": (3, 5), + "accumulation_order": tuple(AccumulationOrder), + } + booths = [ + WindowBoothMultiplier( + add, dbl, neg, scl=scale, **dict(zip(booth_options.keys(), combination)) + ) + for combination in product(*booth_options.values()) + ] ladder_options = {"complete": (True, False)} - ladders = [SimpleLadderMultiplier(add, dbl, scale, **dict(zip(ladder_options.keys(), combination))) for combination in product(*ladder_options.values())] - fixed_options = {"m": (5, 8), - "accumulation_order": tuple(AccumulationOrder)} - fixeds = [FixedWindowLTRMultiplier(add, dbl, scl=scale, **dict(zip(fixed_options.keys(), combination))) for combination in product(*fixed_options.values())] - sliding_options = {"width": (3, 5), - "recoding_direction": tuple(ProcessingDirection), - "accumulation_order": tuple(AccumulationOrder)} - slides = [SlidingWindowMultiplier(add, dbl, scl=scale, **dict(zip(sliding_options.keys(), combination))) for combination in product(*sliding_options.values())] - precomp_options = {"always": (True, False), - "complete": (True, False), - "direction": tuple(ProcessingDirection), - "accumulation_order": tuple(AccumulationOrder)} - precomps = [FullPrecompMultiplier(add, dbl, scl=scale, **dict(zip(precomp_options.keys(), combination))) for combination in product(*precomp_options.values())] - bgmw_options = {"width": (3, 5), - "direction": tuple(ProcessingDirection), - "accumulation_order": tuple(AccumulationOrder)} - bgmws = [BGMWMultiplier(add, dbl, scl=scale, **dict(zip(bgmw_options.keys(), combination))) for combination in product(*bgmw_options.values())] - comb_options = {"width": (2, 3, 5), - "accumulation_order": tuple(AccumulationOrder)} - combs = [CombMultiplier(add, dbl, scl=scale, **dict(zip(comb_options.keys(), combination))) for combination in product(*comb_options.values())] - - mults: Sequence[ScalarMultiplier] = ltrs + rtls + bnafs + wnafs + [CoronMultiplier(add, dbl, scale)] + ladders + fixeds + slides + precomps + bgmws + combs + ladders = [ + SimpleLadderMultiplier( + add, dbl, scale, **dict(zip(ladder_options.keys(), combination)) + ) + for combination in product(*ladder_options.values()) + ] + fixed_options = {"m": (5, 8), "accumulation_order": tuple(AccumulationOrder)} + fixeds = [ + FixedWindowLTRMultiplier( + add, dbl, scl=scale, **dict(zip(fixed_options.keys(), combination)) + ) + for combination in product(*fixed_options.values()) + ] + sliding_options = { + "width": (3, 5), + "recoding_direction": tuple(ProcessingDirection), + "accumulation_order": tuple(AccumulationOrder), + } + slides = [ + SlidingWindowMultiplier( + add, dbl, scl=scale, **dict(zip(sliding_options.keys(), combination)) + ) + for combination in product(*sliding_options.values()) + ] + precomp_options = { + "always": (True, False), + "complete": (True, False), + "direction": tuple(ProcessingDirection), + "accumulation_order": tuple(AccumulationOrder), + } + precomps = [ + FullPrecompMultiplier( + add, dbl, scl=scale, **dict(zip(precomp_options.keys(), combination)) + ) + for combination in product(*precomp_options.values()) + ] + bgmw_options = { + "width": (3, 5), + "direction": tuple(ProcessingDirection), + "accumulation_order": tuple(AccumulationOrder), + } + bgmws = [ + BGMWMultiplier( + add, dbl, scl=scale, **dict(zip(bgmw_options.keys(), combination)) + ) + for combination in product(*bgmw_options.values()) + ] + comb_options = {"width": (2, 3, 5), "accumulation_order": tuple(AccumulationOrder)} + combs = [ + CombMultiplier( + add, dbl, scl=scale, **dict(zip(comb_options.keys(), combination)) + ) + for combination in product(*comb_options.values()) + ] + + mults: Sequence[ScalarMultiplier] = ( + ltrs + + rtls + + bnafs + + wnafs + + booths + + [CoronMultiplier(add, dbl, scale)] + + ladders + + fixeds + + slides + + precomps + + bgmws + + combs + ) results = [] for mult in mults: mult.init(secp128r1, secp128r1.generator) res = mult.multiply(num) if results: - assert res == results[-1], f"Points not equal {res} != {results[-1]} for mult = {mult}" + assert ( + res == results[-1] + ), f"Points not equal {res} != {results[-1]} for mult = {mult}" results.append(res) diff --git a/test/ec/test_scalar.py b/test/ec/test_scalar.py index 493690a..9c6cb60 100644 --- a/test/ec/test_scalar.py +++ b/test/ec/test_scalar.py @@ -1,4 +1,13 @@ -from pyecsca.ec.scalar import convert_base, sliding_window_ltr, sliding_window_rtl, wnaf, naf +from pyecsca.ec.scalar import ( + convert_base, + sliding_window_ltr, + sliding_window_rtl, + wnaf, + naf, + booth, + booth_word, + booth_window, +) def test_convert(): @@ -14,3 +23,18 @@ def test_sliding_window(): def test_nafs(): i = 0b1100110101001101011011 assert naf(i) == wnaf(i, 2) + + +def test_booth(): + assert booth(0b101) == [-1, 1, -1, 1] + for i in range(2**6): + bw = booth_word(i, 5) + # verified with BoringSSL recoding impl. (ec_GFp_nistp_recode_scalar_bits) + if i <= 31: + assert bw == (i + 1) // 2 + else: + assert bw == -((64 - i) // 2) + s = 0x12345678123456781234567812345678123456781234567812345678 + bw = booth_window(s, 5, 224) + # verified with BoringSSL ec_GFp_nistp224_point_mul + assert bw == [1, 4, 13, 3, -10, 15, 0, 9, 3, 9, -10, -12, -8, 2, 9, -6, 5, 13, -2, 1, -14, 7, -15, 11, 8, -16, 5, -14, -12, 11, -6, -4, 1, 4, 13, 3, -10, 15, 0, 9, 3, 9, -10, -12, -8] diff --git a/test/sca/test_rpa.py b/test/sca/test_rpa.py index f09a1a1..39c281d 100644 --- a/test/sca/test_rpa.py +++ b/test/sca/test_rpa.py @@ -12,12 +12,24 @@ from pyecsca.ec.mult import ( RTLMultiplier, BinaryNAFMultiplier, WindowNAFMultiplier, - SimpleLadderMultiplier, AccumulationOrder, ProcessingDirection, SlidingWindowMultiplier, FixedWindowLTRMultiplier, - FullPrecompMultiplier, BGMWMultiplier, CombMultiplier, + SimpleLadderMultiplier, + AccumulationOrder, + ProcessingDirection, + SlidingWindowMultiplier, + FixedWindowLTRMultiplier, + FullPrecompMultiplier, + BGMWMultiplier, + CombMultiplier, + WindowBoothMultiplier, ) from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point -from pyecsca.sca.re.rpa import MultipleContext, rpa_point_0y, rpa_point_x0, rpa_distinguish +from pyecsca.sca.re.rpa import ( + MultipleContext, + rpa_point_0y, + rpa_point_x0, + rpa_distinguish, +) @pytest.fixture() @@ -47,18 +59,18 @@ def neg(coords): @pytest.fixture() def rpa_params(model, coords): - p = 0x85d265945a4f5681 - a = Mod(0x7fc57b4110698bc0, p) - b = Mod(0x37113ea591b04527, p) - gx = Mod(0x80d2d78fddb97597, p) - gy = Mod(0x5586d818b7910930, p) + p = 0x85D265945A4F5681 + a = Mod(0x7FC57B4110698BC0, p) + 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)) curve = EllipticCurve(model, coords, p, infty, dict(a=a, b=b)) - return DomainParameters(curve, g, 0x85d265932d90785c, 1) + return DomainParameters(curve, g, 0x85D265932D90785C, 1) def test_x0_point(rpa_params): @@ -80,25 +92,63 @@ def test_distinguish(secp128r1, add, dbl, neg): RTLMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True), RTLMultiplier(add, dbl, None, True, AccumulationOrder.PeqPR, False), SimpleLadderMultiplier(add, dbl, None, True, True), - BinaryNAFMultiplier(add, dbl, neg, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True), - WindowNAFMultiplier(add, dbl, neg, 3, None, AccumulationOrder.PeqPR, True, True), - WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, True, True), + BinaryNAFMultiplier( + add, dbl, neg, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True + ), + WindowNAFMultiplier( + add, dbl, neg, 3, None, AccumulationOrder.PeqPR, True, True + ), + WindowNAFMultiplier( + add, dbl, neg, 4, None, AccumulationOrder.PeqPR, True, True + ), + WindowBoothMultiplier( + add, dbl, neg, 4, None, AccumulationOrder.PeqPR, True, True + ), # WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, False, True), - SlidingWindowMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True), - SlidingWindowMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True), + SlidingWindowMultiplier( + add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True + ), + SlidingWindowMultiplier( + add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True + ), FixedWindowLTRMultiplier(add, dbl, 4, None, AccumulationOrder.PeqPR, True), FixedWindowLTRMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True), - FullPrecompMultiplier(add, dbl, None, True, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True), - FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True), + FullPrecompMultiplier( + add, + dbl, + None, + True, + ProcessingDirection.LTR, + AccumulationOrder.PeqPR, + True, + True, + ), + FullPrecompMultiplier( + add, + dbl, + None, + False, + ProcessingDirection.LTR, + AccumulationOrder.PeqPR, + True, + True, + ), # FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.RTL, AccumulationOrder.PeqPR, True, True), - BGMWMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True), - BGMWMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True), + BGMWMultiplier( + add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True + ), + BGMWMultiplier( + add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True + ), CombMultiplier(add, dbl, 3, None, AccumulationOrder.PeqPR, True), - CombMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True) + CombMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True), ] for real_mult in multipliers: + def simulated_oracle(scalar, affine_point): - point = affine_point.to_model(secp128r1.curve.coordinate_model, secp128r1.curve) + point = affine_point.to_model( + secp128r1.curve.coordinate_model, secp128r1.curve + ) with local(MultipleContext()) as ctx: real_mult.init(secp128r1, point) real_mult.multiply(scalar) -- cgit v1.2.3-70-g09d2