7 files changed, 543 insertions, 153 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())]
+    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
+    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)