diff options
| -rw-r--r-- | docs/_static/custom.css | 5 | ||||
| -rw-r--r-- | pyecsca/ec/countermeasures.py | 152 | ||||
| -rw-r--r-- | pyecsca/ec/mult/base.py | 2 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 10 | ||||
| -rw-r--r-- | test/sca/test_rpa.py | 6 |
5 files changed, 132 insertions, 43 deletions
diff --git a/docs/_static/custom.css b/docs/_static/custom.css index ba69356..4c4e201 100644 --- a/docs/_static/custom.css +++ b/docs/_static/custom.css @@ -26,3 +26,8 @@ dt:target, .highlight { width: 107px; font-weight: normal !important; } + +.frame mjx-math { + border: 1px solid #e0e0e0; + padding: 5px; +}
\ No newline at end of file diff --git a/pyecsca/ec/countermeasures.py b/pyecsca/ec/countermeasures.py index 5c52f35..8a479b6 100644 --- a/pyecsca/ec/countermeasures.py +++ b/pyecsca/ec/countermeasures.py @@ -7,7 +7,7 @@ from public import public from pyecsca.ec.formula import AdditionFormula from pyecsca.ec.mod import Mod, mod -from pyecsca.ec.mult import ScalarMultiplier +from pyecsca.ec.mult import ScalarMultiplier, ScalarMultiplicationAction from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point @@ -29,102 +29,180 @@ class ScalarMultiplierCountermeasure(ABC): self.mult = mult def init(self, params: DomainParameters, point: Point): + """Initialize the countermeasure with the parameters and the point.""" self.params = params self.point = point self.mult.init(self.params, self.point) @abstractmethod def multiply(self, scalar: int) -> Point: + """ + Multiply the point with the scalar using the countermeasure. + + .. note:: + The countermeasure may compute multiple scalar multiplications internally. + Thus, it may call the init method of the scalar multiplier multiple times. + """ raise NotImplementedError @public class GroupScalarRandomization(ScalarMultiplierCountermeasure): + r""" + Group scalar randomization countermeasure. + + Samples a random multiple, multiplies the order with it and adds it to the scalar. + + .. math:: + :class: frame + + &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\text{rand_bits}}\} \\ + &\textbf{return}\ [k + r n]G + + """ rand_bits: int def __init__(self, mult: ScalarMultiplier, rand_bits: int = 32): + """ + :param mult: The multiplier to use. + :param rand_bits: How many random bits to sample. + """ super().__init__(mult) self.rand_bits = rand_bits def multiply(self, scalar: int) -> Point: if self.params is None or self.point is None: raise ValueError("Not initialized.") - order = self.params.order - mask = int(Mod.random(1 << self.rand_bits)) - masked_scalar = scalar + mask * order - return self.mult.multiply(masked_scalar) + with ScalarMultiplicationAction(self.point, self.params, scalar) as action: + order = self.params.order + mask = int(Mod.random(1 << self.rand_bits)) + masked_scalar = scalar + mask * order + return action.exit(self.mult.multiply(masked_scalar)) @public class AdditiveSplitting(ScalarMultiplierCountermeasure): + r""" + Additive splitting countermeasure. + + Splits the scalar into two parts additively, multiplies the point with them and adds the results. + + .. math:: + :class: frame + + &r \xleftarrow{\$} \{0, 1, \ldots, n\} \\ + &\textbf{return}\ [k - r]G + [r]G + + """ add: Optional[AdditionFormula] def __init__(self, mult: ScalarMultiplier, add: Optional[AdditionFormula] = None): + """ + :param mult: The multiplier to use. + :param add: Addition formula to use, if None, the formula from the multiplier is used. + """ super().__init__(mult) self.add = add def multiply(self, scalar: int) -> Point: if self.params is None or self.point is None: raise ValueError("Not initialized.") - - order = self.params.order - r = Mod.random(order) - s = scalar - r - R = self.mult.multiply(int(r)) - S = self.mult.multiply(int(s)) - if self.add is None: - return self.mult._add(R, S) # noqa: This is OK. - else: - return self.add( - self.params.curve.prime, R, S, **self.params.curve.parameters - )[0] + with ScalarMultiplicationAction(self.point, self.params, scalar) as action: + order = self.params.order + r = Mod.random(order) + s = scalar - r + R = self.mult.multiply(int(r)) + S = self.mult.multiply(int(s)) + if self.add is None: + res = self.mult._add(R, S) # noqa: This is OK. + else: + res = self.add(self.params.curve.prime, R, S, **self.params.curve.parameters)[0] + return action.exit(res) @public class MultiplicativeSplitting(ScalarMultiplierCountermeasure): + r""" + Multiplicative splitting countermeasure. + + Splits the scalar into two parts multiplicatively, multiplies the point with them and adds the results. + + .. math:: + :class: frame + + &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\text{rand_bits}}\} \\ + &S = [r]G \\ + &\textbf{return}\ [k r^{-1} \mod n]S + + """ rand_bits: int def __init__(self, mult: ScalarMultiplier, rand_bits: int = 32): + """ + :param mult: The multiplier to use. + :param rand_bits: How many random bits to sample. + """ super().__init__(mult) self.rand_bits = rand_bits def multiply(self, scalar: int) -> Point: if self.params is None or self.point is None: raise ValueError("Not initialized.") - r = Mod.random(1 << self.rand_bits) - R = self.mult.multiply(int(r)) + with ScalarMultiplicationAction(self.point, self.params, scalar) as action: + r = Mod.random(1 << self.rand_bits) + R = self.mult.multiply(int(r)) - self.mult.init(self.params, R) - kr_inv = scalar * mod(int(r), self.params.order).inverse() - return self.mult.multiply(int(kr_inv)) + self.mult.init(self.params, R) + kr_inv = scalar * mod(int(r), self.params.order).inverse() + return action.exit(self.mult.multiply(int(kr_inv))) @public class EuclideanSplitting(ScalarMultiplierCountermeasure): + r""" + Euclidean splitting countermeasure. + + Picks a random value half the size of the curve, then splits the scalar + into the remainder and the quotient of the division by the random value. + + .. math:: + :class: frame + + &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\log_2{(n)}/2}\} \\ + &S = [r]G \\ + &k_1 = k \mod r \\ + &k_2 = \lfloor \frac{k}{r} \rfloor \\ + &\textbf{return}\ [k_1]G + [k_2]S + + """ add: Optional[AdditionFormula] def __init__(self, mult: ScalarMultiplier, add: Optional[AdditionFormula] = None): + """ + :param mult: The multiplier to use. + :param add: Addition formula to use, if None, the formula from the multiplier is used. + """ super().__init__(mult) self.add = add def multiply(self, scalar: int) -> Point: if self.params is None or self.point is None: raise ValueError("Not initialized.") + with ScalarMultiplicationAction(self.point, self.params, scalar) as action: + order = self.params.order + half_bits = order.bit_length() // 2 + r = Mod.random(1 << half_bits) + R = self.mult.multiply(int(r)) - order = self.params.order - half_bits = order.bit_length() // 2 - r = Mod.random(1 << half_bits) - R = self.mult.multiply(int(r)) + k1 = scalar % int(r) + k2 = scalar // int(r) + T = self.mult.multiply(k1) - k1 = scalar % int(r) - k2 = scalar // int(r) - T = self.mult.multiply(k1) + self.mult.init(self.params, R) + S = self.mult.multiply(k2) - self.mult.init(self.params, R) - S = self.mult.multiply(k2) - if self.add is None: - return self.mult._add(S, T) # noqa: This is OK. - else: - return self.add( - self.params.curve.prime, S, T, **self.params.curve.parameters - )[0] + if self.add is None: + res = self.mult._add(S, T) # noqa: This is OK. + else: + res = self.add(self.params.curve.prime, S, T, **self.params.curve.parameters)[0] + return action.exit(res) diff --git a/pyecsca/ec/mult/base.py b/pyecsca/ec/mult/base.py index 1c51271..f7a8c5b 100644 --- a/pyecsca/ec/mult/base.py +++ b/pyecsca/ec/mult/base.py @@ -7,7 +7,7 @@ from enum import Enum from public import public from typing import Mapping, Tuple, Optional, ClassVar, Set, Type -from pyecsca.ec.context import ResultAction, Action +from pyecsca.ec.context import ResultAction from pyecsca.ec.formula import Formula from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index e7796cf..4f30d07 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -54,7 +54,7 @@ class MultipleContext(Context): """The mapping of points to the formula types they are a result of.""" precomp: MutableMapping[int, Point] """The mapping of precomputed multiples to the points they represent.""" - inside: bool + inside: List[Action] """Whether we are inside a scalarmult/precomp action.""" keep_base: bool """Whether to keep the base point when building upon it.""" @@ -65,12 +65,12 @@ class MultipleContext(Context): self.parents = {} self.formulas = {} self.precomp = {} - self.inside = False + self.inside = [] self.keep_base = keep_base def enter_action(self, action: Action) -> None: if isinstance(action, (ScalarMultiplicationAction, PrecomputationAction)): - self.inside = True + self.inside.append(action) if self.base: # If we already did some computation with this context try to see if we are building on top of it. if self.base != action.point: @@ -97,9 +97,9 @@ class MultipleContext(Context): def exit_action(self, action: Action) -> None: if isinstance(action, (ScalarMultiplicationAction, PrecomputationAction)): - self.inside = False + self.inside.remove(action) if isinstance(action, PrecomputationAction): - self.precomp = action.result + self.precomp.update(action.result) if isinstance(action, FormulaAction) and self.inside: action = cast(FormulaAction, action) if isinstance(action.formula, DoublingFormula): diff --git a/test/sca/test_rpa.py b/test/sca/test_rpa.py index 7027a7d..af90fb4 100644 --- a/test/sca/test_rpa.py +++ b/test/sca/test_rpa.py @@ -4,6 +4,7 @@ from math import isqrt import pytest from pyecsca.ec.context import local +from pyecsca.ec.countermeasures import AdditiveSplitting from pyecsca.ec.curve import EllipticCurve from pyecsca.ec.mod import mod from pyecsca.ec.model import ShortWeierstrassModel @@ -128,6 +129,11 @@ def test_multiples_kind(rpa_params): assert multiples_precomp != multiples_necessary +def test_multiples_additive(rpa_params): + mults = multiples_computed(1454656138887897564, rpa_params, LTRMultiplier, lambda *args, **kwargs: AdditiveSplitting(LTRMultiplier(*args, **kwargs)), True, True, kind="precomp+necessary") + assert mults is not None + + def test_x0_point(rpa_params): res = rpa_point_x0(rpa_params) assert res is not None |