diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | docs/index.rst | 2 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 90 | ||||
| -rw-r--r-- | pyecsca/sca/re/zvp.py | 128 | ||||
| -rw-r--r-- | test/sca/test_zvp.py | 59 |
5 files changed, 260 insertions, 21 deletions
@@ -56,7 +56,7 @@ It is currently in an alpha stage of development and thus only provides: - [smartleia](https://pypi.org/project/smartleia/) - **Faster arithmetic:** - [gmpy2](https://gmpy2.readthedocs.io/) (and also GMP library) - + - [cypari2](https://cypari2.readthedocs.io/) (and also PARI library) *pyecsca* contains data from the [Explicit-Formulas Database](https://www.hyperelliptic.org/EFD/index.html) by Daniel J. Bernstein and Tanja Lange. The data was partially changed, to make working with it easier. It is available on Github at [crocs-muni/efd](https://github.com/crocs-muni/efd). diff --git a/docs/index.rst b/docs/index.rst index 64e84bc..88b9292 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -154,6 +154,7 @@ Requirements - **Faster arithmetic:** - gmpy2_ (and also GMP library) + - cypari2_ (and also PARI library) *pyecsca* contains data from the `Explicit-Formulas Database`_ by Daniel J. Bernstein and Tanja Lange. The data was partially changed, to make working with it easier. It is available on Github at `crocs-muni/efd`_. @@ -235,6 +236,7 @@ Development was supported by the Masaryk University grant `MUNI/C/1707/2018 <htt .. _pyscard: https://pyscard.sourceforge.io/ .. _leia: https://pypi.org/project/smartleia/ .. _gmpy2: https://gmpy2.readthedocs.io/ +.. _cypari2: https://cypari2.readthedocs.io/ .. _pytest: https://pytest.org .. _mypy: http://mypy-lang.org/ .. _flake8: https://flake8.pycqa.org/ diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index 6d2218b..5bbd145 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -21,7 +21,11 @@ from ...ec.formula import ( LadderFormula, ) from ...ec.mod import Mod -from ...ec.mult import ScalarMultiplicationAction, PrecomputationAction, ScalarMultiplier +from ...ec.mult import ( + ScalarMultiplicationAction, + PrecomputationAction, + ScalarMultiplier, +) from ...ec.params import DomainParameters from ...ec.model import ShortWeierstrassModel, MontgomeryModel from ...ec.point import Point @@ -38,6 +42,8 @@ class MultipleContext(Context): points: MutableMapping[Point, int] """The mapping of points to the multiples they represent (e.g., base -> 1).""" parents: MutableMapping[Point, List[Point]] + """The mapping of points to the formula types they are a result of.""" + formulas: MutableMapping[Point, str] """The mapping of points to their parent they were computed from.""" inside: bool @@ -45,6 +51,7 @@ class MultipleContext(Context): self.base = None self.points = {} self.parents = {} + self.formulas = {} self.inside = False def enter_action(self, action: Action) -> None: @@ -56,10 +63,12 @@ class MultipleContext(Context): self.base = action.point self.points = {self.base: 1} self.parents = {self.base: []} + self.formulas = {self.base: ""} else: self.base = action.point self.points = {self.base: 1} self.parents = {self.base: []} + self.formulas = {self.base: ""} self.inside = True def exit_action(self, action: Action) -> None: @@ -71,33 +80,40 @@ class MultipleContext(Context): out = action.output_points[0] self.points[out] = 2 * self.points[inp] self.parents[out] = [inp] + self.formulas[out] = action.formula.shortname elif isinstance(action.formula, TriplingFormula): inp = action.input_points[0] out = action.output_points[0] self.points[out] = 3 * self.points[inp] self.parents[out] = [inp] + self.formulas[out] = action.formula.shortname elif isinstance(action.formula, AdditionFormula): one, other = action.input_points out = action.output_points[0] self.points[out] = self.points[one] + self.points[other] self.parents[out] = [one, other] + self.formulas[out] = action.formula.shortname elif isinstance(action.formula, NegationFormula): inp = action.input_points[0] out = action.output_points[0] self.points[out] = -self.points[inp] self.parents[out] = [inp] + self.formulas[out] = action.formula.shortname elif isinstance(action.formula, DifferentialAdditionFormula): _, one, other = action.input_points out = action.output_points[0] self.points[out] = self.points[one] + self.points[other] self.parents[out] = [one, other] + self.formulas[out] = action.formula.shortname elif isinstance(action.formula, LadderFormula): _, one, other = action.input_points dbl, add = action.output_points self.points[add] = self.points[one] + self.points[other] self.parents[add] = [one, other] + self.formulas[add] = action.formula.shortname self.points[dbl] = 2 * self.points[one] self.parents[dbl] = [one] + self.formulas[dbl] = action.formula.shortname def __repr__(self): return f"{self.__class__.__name__}({self.base!r}, multiples={self.points.values()!r})" @@ -111,10 +127,15 @@ def rpa_point_0y(params: DomainParameters) -> Optional[Point]: return None y = params.curve.parameters["b"].sqrt() # TODO: We can take the negative as well. - return Point(AffineCoordinateModel(params.curve.model), x=Mod(0, params.curve.prime), y=y) + return Point( + AffineCoordinateModel(params.curve.model), x=Mod(0, params.curve.prime), y=y + ) elif isinstance(params.curve.model, MontgomeryModel): - return Point(AffineCoordinateModel(params.curve.model), x=Mod(0, params.curve.prime), - y=Mod(0, params.curve.prime)) + return Point( + AffineCoordinateModel(params.curve.model), + x=Mod(0, params.curve.prime), + y=Mod(0, params.curve.prime), + ) else: raise NotImplementedError @@ -134,10 +155,15 @@ def rpa_point_x0(params: DomainParameters) -> Optional[Point]: if not roots: return None x = Mod(int(next(iter(roots.keys()))), params.curve.prime) - return Point(AffineCoordinateModel(params.curve.model), x=x, y=Mod(0, params.curve.prime)) + return Point( + AffineCoordinateModel(params.curve.model), x=x, y=Mod(0, params.curve.prime) + ) elif isinstance(params.curve.model, MontgomeryModel): - return Point(AffineCoordinateModel(params.curve.model), x=Mod(0, params.curve.prime), - y=Mod(0, params.curve.prime)) + return Point( + AffineCoordinateModel(params.curve.model), + x=Mod(0, params.curve.prime), + y=Mod(0, params.curve.prime), + ) else: raise NotImplementedError @@ -150,8 +176,15 @@ def rpa_input_point(k: Mod, rpa_point: Point, params: DomainParameters) -> Point @public -def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], oracle: Callable[[int, Point], bool], - bound: Optional[int] = None, majority: int = 1, use_init: bool = True, use_multiply: bool = True) -> List[ScalarMultiplier]: +def rpa_distinguish( + params: DomainParameters, + mults: List[ScalarMultiplier], + oracle: Callable[[int, Point], bool], + bound: Optional[int] = None, + majority: int = 1, + use_init: bool = True, + use_multiply: bool = True, +) -> List[ScalarMultiplier]: """ Distinguish the scalar multiplier used (from the possible :paramref:`~.rpa_distinguish.mults`) using an [RPA]_ :paramref:`~.rpa_distinguish.oracle`. @@ -198,16 +231,30 @@ def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], ora # Take the computed points during init init_points = set(init_context.parents.keys()) # And get their parents (inputs to formulas) - init_parents = set(sum((init_context.parents[point] for point in init_points), [])) + init_parents = set( + sum((init_context.parents[point] for point in init_points), []) + ) # Go over the parents and map them to multiples of the base (plus-minus sign) - init_multiples = set(map(lambda v: Mod(v, params.order), (init_context.points[parent] for parent in init_parents))) + init_multiples = set( + map( + lambda v: Mod(v, params.order), + (init_context.points[parent] for parent in init_parents), + ) + ) init_multiples |= set(map(lambda v: -v, init_multiples)) # Now do the multiply and repeat the above, but only consider new computed points with local(init_context) as ctx: mult.multiply(scalar) all_points = set(ctx.parents.keys()) - multiply_parents = set(sum((ctx.parents[point] for point in all_points - init_points), [])) - multiply_multiples = set(map(lambda v: Mod(v, params.order), (ctx.points[parent] for parent in multiply_parents))) + multiply_parents = set( + sum((ctx.parents[point] for point in all_points - init_points), []) + ) + multiply_multiples = set( + map( + lambda v: Mod(v, params.order), + (ctx.points[parent] for parent in multiply_parents), + ) + ) multiply_multiples |= set(map(lambda v: -v, multiply_multiples)) used = set() if use_init: @@ -218,7 +265,13 @@ def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], ora tree = build_distinguishing_tree(mults_to_multiples) log("Built distinguishing tree.") - log(RenderTree(tree).by_attr(lambda n: n.name if n.name else [mult.__class__.__name__ for mult in n.cfgs])) + log( + RenderTree(tree).by_attr( + lambda n: n.name + if n.name + else [mult.__class__.__name__ for mult in n.cfgs] + ) + ) if tree is None or not tree.children: tries += 1 continue @@ -237,8 +290,13 @@ def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], ora break log(f"Oracle response -> {response}") for mult in mults: - log(mult.__class__.__name__, best_distinguishing_multiple in mults_to_multiples[mult]) - response_map = {child.oracle_response: child for child in current_node.children} + log( + mult.__class__.__name__, + best_distinguishing_multiple in mults_to_multiples[mult], + ) + response_map = { + child.oracle_response: child for child in current_node.children + } current_node = response_map[response] mults = current_node.cfgs log([mult.__class__.__name__ for mult in mults]) diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py index 6b1beac..2146966 100644 --- a/pyecsca/sca/re/zvp.py +++ b/pyecsca/sca/re/zvp.py @@ -3,16 +3,29 @@ Provides functionality inspired by the Zero-value point attack [ZVP]_. Implements ZVP point construction from [FFD]_. """ -from typing import List, Set, Tuple, Dict +from typing import List, Set, Tuple, Dict, Type, Mapping from public import public from astunparse import unparse from sympy import FF, Poly, Monomial, Symbol, Expr, sympify, symbols, div +from tqdm.auto import tqdm +from .rpa import MultipleContext +from ...ec.context import local from ...ec.curve import EllipticCurve from ...ec.divpoly import mult_by_n -from ...ec.formula import Formula +from ...ec.formula import ( + Formula, + AdditionFormula, + DoublingFormula, + DifferentialAdditionFormula, + LadderFormula, + NegationFormula, +) +from ...ec.formula.fake import FakePoint, FakeFormula from ...ec.mod import Mod +from ...ec.mult import ScalarMultiplier +from ...ec.params import DomainParameters from ...ec.point import Point @@ -183,7 +196,7 @@ def is_homogeneous(polynomial: Poly, weighted_variables: List[Tuple[str, int]]) @public -def compute_factor_set(formula: Formula, affine: bool = True) -> Set[Poly]: +def compute_factor_set(formula: Formula, affine: bool = True, filter_nonhomo: bool = True) -> Set[Poly]: """ Compute a set of factors present in the :paramref:`~.compute_factor_set.formula`. @@ -192,7 +205,8 @@ def compute_factor_set(formula: Formula, affine: bool = True) -> Set[Poly]: :return: The set of factors present in the formula. """ unrolled = unroll_formula(formula) - unrolled = filter_out_nonhomogenous_polynomials(formula, unrolled) + if filter_nonhomo: + unrolled = filter_out_nonhomogenous_polynomials(formula, unrolled) if affine: unrolled = map_to_affine(formula, unrolled) @@ -496,3 +510,109 @@ def zvp_points(poly: Poly, curve: EllipticCurve, k: int, n: int) -> Set[Point]: if res == 0: points.add(point) return points + + +def addition_chain( + scalar: int, + params: DomainParameters, + mult_class: Type[ScalarMultiplier], + mult_factory, +) -> List[Tuple[str, Tuple[int, ...]]]: + """ + Compute the addition chain for a given scalar and multiplier. + + :param scalar: The scalar to compute for. + :param params: The domain parameters to use. + :param mult_class: The class of the scalar multiplier to use. + :param mult_factory: A callable that takes the formulas and instantiates the multiplier. + :return: A list of tuples, where the first element is the formula shortname (e.g. "add") and the second is a tuple of the dlog + relationships to the input of the input points to the formula. + """ + formula_classes: List[Type[Formula]] = list( + filter( + lambda klass: klass in mult_class.requires, + [ + AdditionFormula, + DifferentialAdditionFormula, + DoublingFormula, + LadderFormula, + NegationFormula, + ], + ) + ) + formulas = [] + for formula in formula_classes: + for subclass in formula.__subclasses__(): + if issubclass(subclass, FakeFormula): + formulas.append(subclass(params.curve.coordinate_model)) + mult = mult_factory(*formulas) + mult.init(params, FakePoint(params.curve.coordinate_model)) + + with local(MultipleContext()) as mctx: + mult.multiply(scalar) + + chain = [] + for point, parents in mctx.parents.items(): + if not parents: + continue + formula_type = mctx.formulas[point] + ks = tuple(mctx.points[parent] for parent in parents) + chain.append((formula_type, ks)) + return chain + + +def precomp_zvp_points( + chain: List[Tuple[str, Tuple[int, ...]]], + formulas: Mapping[str, Formula], + params: DomainParameters, + bound: int = 25, +) -> List[Mapping[Poly, Set[Point]]]: + """ + + :param chain: + :param formulas: + :param params: + :param bound: + :return: + """ + factor_sets = { + formula: compute_factor_set(formula) for formula in formulas.values() + } + # A bit of a hack to rename the poly variables for double as zvp_points expects that. + for formula in formulas.values(): + if isinstance(formula, DoublingFormula): + fset = factor_sets[formula] + new_fset = set() + for poly in fset: + pl = poly.copy() + for symbol in poly.free_symbols: + original = str(symbol) + if original.endswith("1"): + new = original.replace("1", "2") + pl = pl.subs(original, new) + new_fset.add(pl) + factor_sets[formula] = new_fset + result: List[Mapping[Poly, Set[Point]]] = [] + for op, ks in chain: + if op not in formulas: + continue + formula = formulas[op] + factor_set = factor_sets[formula] + if len(ks) == 1: + k = ks[0] + else: + # zvp_points assumes (P, [k]P) + ks_mod = list(map(lambda v: Mod(v, params.order), ks)) + k = int(ks_mod[1] / ks_mod[0]) + points = {} + + for poly in factor_set: + only_1 = all((not str(gen).endswith("2")) for gen in poly.gens) # type: ignore[attr-defined] + only_2 = all((not str(gen).endswith("1")) for gen in poly.gens) # type: ignore[attr-defined] + # This is the hard case where a dlog needs to be substituted, so bound it. + if not (only_1 or only_2) and k > bound: + continue + + points[poly] = zvp_points(poly, params.curve, k, params.order) + result.append(points) + return result diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py index ceb8941..d1b7930 100644 --- a/test/sca/test_zvp.py +++ b/test/sca/test_zvp.py @@ -1,7 +1,11 @@ import pytest from pyecsca.ec.coordinates import AffineCoordinateModel +from pyecsca.ec.curve import EllipticCurve from pyecsca.ec.mod import Mod +from pyecsca.ec.model import ShortWeierstrassModel +from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder +from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point from pyecsca.sca.re.zvp import ( unroll_formula, @@ -13,6 +17,8 @@ from pyecsca.sca.re.zvp import ( subs_curve_params, zvp_points, compute_factor_set, + addition_chain, + precomp_zvp_points, ) from pyecsca.ec.context import local, DefaultContext from sympy import symbols, Poly, sympify, FF @@ -233,3 +239,56 @@ def test_points(secp128r1, poly_str, point, k): poly = Poly(poly_expr, domain=FF(secp128r1.curve.prime)) res = zvp_points(poly, secp128r1.curve, k, secp128r1.order) assert pt in res + + +def test_addition_chain(secp128r1): + res = addition_chain( + 78699, + secp128r1, + LTRMultiplier, + lambda add, dbl: LTRMultiplier( + add, dbl, None, False, AccumulationOrder.PeqPR, True, True + ), + ) + assert res is not None + assert len(res) == 25 + + +@pytest.fixture() +def small_params(): + model = ShortWeierstrassModel() + coords = model.coordinates["projective"] + p = 0xC50DE883F0E7B167 + a = Mod(0x4833D7AA73FA6694, p) + b = Mod(0xA6C44A61C5323F6A, p) + gx = Mod(0x5FD1F7D38D4F2333, p) + gy = Mod(0x21F43957D7E20CEB, p) + n = 0xC50DE885003B80EB + h = 1 + 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)) + params = DomainParameters(curve, g, n, h) + return params + + +def test_precomp(small_params): + chain = addition_chain( + 123456789, + small_params, + LTRMultiplier, + lambda add, dbl: LTRMultiplier( + add, dbl, None, False, AccumulationOrder.PeqRP, True, True + ), + ) + res = precomp_zvp_points( + chain, + { + "add": small_params.curve.coordinate_model.formulas["add-2007-bl"], + "dbl": small_params.curve.coordinate_model.formulas["dbl-2007-bl"], + }, + small_params, + ) + assert res is not None + assert len(res) == len(chain) |