diff options
Diffstat (limited to 'pyecsca')
| -rw-r--r-- | pyecsca/ec/context.py | 21 | ||||
| -rw-r--r-- | pyecsca/ec/mult/comb.py | 2 | ||||
| -rw-r--r-- | pyecsca/ec/mult/naf.py | 3 | ||||
| -rw-r--r-- | pyecsca/ec/mult/window.py | 6 | ||||
| -rw-r--r-- | pyecsca/sca/re/epa.py | 105 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 117 | ||||
| -rw-r--r-- | pyecsca/sca/re/tree.py | 2 |
7 files changed, 218 insertions, 38 deletions
diff --git a/pyecsca/ec/context.py b/pyecsca/ec/context.py index b58db2a..33c961d 100644 --- a/pyecsca/ec/context.py +++ b/pyecsca/ec/context.py @@ -352,3 +352,24 @@ def local(ctx: Optional[Context] = None, copy: bool = True) -> ContextManager: :return: A context manager. """ return _ContextManager(ctx, copy) + + +@public +def compound(*contexts: Context) -> Context: + """ + Create a context that compounds multiple contexts. + + :param contexts: The contexts to compound. + :return: The compounded context. + """ + + class CompoundContext(Context): + def enter_action(self, action: Action) -> None: + for ctx in contexts: + ctx.enter_action(action) + + def exit_action(self, action: Action) -> None: + for ctx in contexts: + ctx.exit_action(action) + + return CompoundContext() diff --git a/pyecsca/ec/mult/comb.py b/pyecsca/ec/mult/comb.py index d24f557..ae6d0c1 100644 --- a/pyecsca/ec/mult/comb.py +++ b/pyecsca/ec/mult/comb.py @@ -198,7 +198,7 @@ class CombMultiplier(AccumulatorMultiplier, PrecompMultiplier, ScalarMultiplier) current_point = point for i in range(self.width): base_points[i] = current_point - if i != d - 1: + if i != self.width - 1: for _ in range(d): current_point = self._dbl(current_point) self._points = {} diff --git a/pyecsca/ec/mult/naf.py b/pyecsca/ec/mult/naf.py index 1d77056..4c6e0c2 100644 --- a/pyecsca/ec/mult/naf.py +++ b/pyecsca/ec/mult/naf.py @@ -270,7 +270,8 @@ class WindowNAFMultiplier(AccumulatorMultiplier, PrecompMultiplier, ScalarMultip self._points[2 * i + 1] = current_point if self.precompute_negation: self._points_neg[2 * i + 1] = self._neg(current_point) - current_point = self._add(current_point, double_point) + if i != 2 ** (self.width - 2) - 1: + current_point = self._add(current_point, double_point) result = {**self._points} if self.precompute_negation: result.update({-k: v for k, v in self._points_neg.items()}) diff --git a/pyecsca/ec/mult/window.py b/pyecsca/ec/mult/window.py index ed0cd05..e46179a 100644 --- a/pyecsca/ec/mult/window.py +++ b/pyecsca/ec/mult/window.py @@ -104,7 +104,8 @@ class SlidingWindowMultiplier( double_point = self._dbl(point) for i in range(0, 2 ** (self.width - 1)): self._points[2 * i + 1] = current_point - current_point = self._add(current_point, double_point) + if i != 2 ** (self.width - 1) - 1: + current_point = self._add(current_point, double_point) action.exit(self._points) def multiply(self, scalar: int) -> Point: @@ -232,7 +233,8 @@ class FixedWindowLTRMultiplier( converted = convert_base(scalar, self.m) q = copy(self._params.curve.neutral) for digit in reversed(converted): - q = self._mult_m(q) + if q != self._params.curve.neutral: + q = self._mult_m(q) if digit != 0: q = self._accumulate(q, self._points[digit]) if "scl" in self.formulas: diff --git a/pyecsca/sca/re/epa.py b/pyecsca/sca/re/epa.py index 1a6b19f..4ef1b74 100644 --- a/pyecsca/sca/re/epa.py +++ b/pyecsca/sca/re/epa.py @@ -1,8 +1,12 @@ """ Provides functionality inspired by the Exceptional Procedure Attack [EPA]_. """ + from typing import Callable, Literal, Union, Optional +import networkx as nx + + from public import public from pyecsca.ec.point import Point @@ -26,7 +30,8 @@ def graph_to_check_inputs( "affine" formula that checks the multiples of the points that need to be converted to affine coordinates. Which points this "affine" formula checks depends on the `precomp_to_affine` parameter. - :param ctx: The context containing the points and formulas. + :param precomp_ctx: The context containing the points and formulas (precomputation phase). + :param full_ctx: The context containing the points and formulas (full computation). :param out: The output point of the computation. :param check_condition: Whether to check all points or only those necessary for the output point. :param precomp_to_affine: Whether to include the precomputed points in the to-affine checks. @@ -73,9 +78,13 @@ def graph_to_check_inputs( if use_init and use_multiply: points = _necessary(full_ctx, affine_points) elif use_init: - points = _necessary(full_ctx, affine_points) & set(precomp_ctx.points.keys()) + points = _necessary(full_ctx, affine_points) & set( + precomp_ctx.points.keys() + ) elif use_multiply: - points = _necessary(full_ctx, affine_points) - set(precomp_ctx.points.keys()) + points = _necessary(full_ctx, affine_points) - set( + precomp_ctx.points.keys() + ) else: raise ValueError("check_condition must be 'all' or 'necessary'") # Special case the "to affine" transform and checks @@ -90,7 +99,9 @@ def graph_to_check_inputs( for point in points: formula = full_ctx.formulas[point] - if not formula or (check_formulas is not None and formula not in check_formulas): + if not formula or ( + check_formulas is not None and formula not in check_formulas + ): # Skip input point or infty point (they magically appear and do not have an origin formula) continue inputs = tuple(map(get_point, full_ctx.parents[point])) @@ -100,8 +111,79 @@ def graph_to_check_inputs( @public +def graph_plot_prepare( + precomp_ctx: MultipleContext, + full_ctx: MultipleContext, + out: Point, +) -> nx.DiGraph: + """ + Prepare the computation graph, highlighting necessary points and precomputed points. + + Legend: + - Circles: Necessary points in the computation. + - Triangles: Unnecessary points in the computation. + - Blue: Points computed during the full computation phase. + - Green: Points computed during the precomputation phase. + - Cyan: Precomputed points (stored by the multiplier). + + Plot the result using `nx.display`. + + :param precomp_ctx: The context containing the points and formulas (precomputation phase). + :param full_ctx: The context containing the points and formulas (full computation). + :param out: The output point of the computation. + :return: The networkx graph. + """ + graph = full_ctx.to_networkx() + + for layer, nodes in enumerate(nx.topological_generations(graph)): + for node in nodes: + graph.nodes[node]["layer"] = layer + for node in graph.nodes(): + graph.nodes[node]["necessary"] = False + queue = {out} + while queue: + node = queue.pop() + graph.nodes[node]["necessary"] = True + for n in graph.predecessors(node): + queue.add(n) + + pos = nx.multipartite_layout(graph, subset_key="layer") + nx.set_node_attributes(graph, pos, "pos") + + for point in graph.nodes(): + node = graph.nodes[point] + node["label"] = { + "label": node["multiple"], + "color": "black", + "bbox": {"boxstyle": "square", "alpha": 0.7, "facecolor": "white"} + } + + if point in precomp_ctx.points.keys(): + node["color"] = "#208020" + if node["precomp"]: + node["pos"][1] -= 0.01 + node["color"] = "#30a0a0" + else: + node["color"] = "#202080" + + if node["necessary"]: + node["shape"] = "o" + else: + node["shape"] = "^" + node["pos"][1] += 0.01 + + for u, v in graph.edges(): + edge = graph.edges[u, v] + edge["label"] = edge["formula"] + edge["curvature"] = "arc3,rad=0.05" + + return graph + + +@public def evaluate_checks( - check_funcs: dict[str, Union[Callable[[int, int], bool], Callable[[int], bool]]], check_inputs: dict[str, set[tuple[int, ...]]] + check_funcs: dict[str, Union[Callable[[int, int], bool], Callable[[int], bool]]], + check_inputs: dict[str, set[tuple[int, ...]]], ) -> bool: """ Evaluate the checks for each formula type based on the provided functions and inputs. @@ -141,7 +223,8 @@ def errors_out( """ Check whether the computation errors out based on the provided context, output point, and check functions. - :param ctx: The context containing the points and formulas. + :param precomp_ctx: The context containing the points and formulas (precomputation phase). + :param full_ctx: The context containing the points and formulas (full computation). :param out: The output point of the computation. :param check_funcs: The functions to apply for each formula type. There are two callable types: - `check(k, l)`, that gets applied to binary formulas (like `add`), where `k` and `l` are the input multiples @@ -157,5 +240,13 @@ def errors_out( .. note:: The scalar multiplier must not short-circuit. """ - formula_checks = graph_to_check_inputs(precomp_ctx, full_ctx, out, check_condition, precomp_to_affine, use_init, use_multiply) + formula_checks = graph_to_check_inputs( + precomp_ctx, + full_ctx, + out, + check_condition, + precomp_to_affine, + use_init, + use_multiply, + ) return evaluate_checks(check_funcs, formula_checks) diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index e899f20..2fd5973 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -18,6 +18,8 @@ from typing import ( Tuple, ) +import networkx as nx + from sympy import FF, sympify, Poly, symbols from pyecsca.ec.error import NonInvertibleError @@ -27,7 +29,7 @@ from pyecsca.sca.re.tree import Tree, Map from pyecsca.ec.coordinates import AffineCoordinateModel from pyecsca.ec.formula import ( FormulaAction, - ) +) from pyecsca.ec.mod import Mod, mod from pyecsca.ec.mult import ( ScalarMultiplicationAction, @@ -37,7 +39,7 @@ from pyecsca.ec.mult import ( from pyecsca.ec.params import DomainParameters from pyecsca.ec.model import ShortWeierstrassModel, MontgomeryModel from pyecsca.ec.point import Point -from pyecsca.ec.context import Context, Action, local +from pyecsca.ec.context import Context, Action, local, compound from pyecsca.ec.mult.fake import cached_fake_mult, fake_params from pyecsca.misc.utils import log, warn @@ -58,22 +60,50 @@ 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.""" + result: Optional[Point] + """The resulting point of the computation.""" inside: List[Action] """Whether we are inside a scalarmult/precomp action.""" keep_base: bool """Whether to keep the base point when building upon it.""" - def __init__(self, keep_base: bool = False): + def __init__( + self, + keep_base: bool = False, + track_precomp: bool = True, + track_scalarmult: bool = True, + ): self.base = None self.points = {} self.parents = {} self.formulas = {} self.precomp = {} self.inside = [] + self.result = None self.keep_base = keep_base + self._track_precomp = track_precomp + self._track_scalarmult = track_scalarmult + + @property + def track_precomp(self) -> bool: + """Whether to track PrecomputationAction actions.""" + return self._track_precomp + + @track_precomp.setter + def track_precomp(self, value: bool) -> None: + self._track_precomp = value + + @property + def track_scalarmult(self) -> bool: + """Whether to track ScalarMultiplicationAction actions.""" + return self._track_scalarmult + + @track_scalarmult.setter + def track_scalarmult(self, value: bool) -> None: + self._track_scalarmult = value def enter_action(self, action: Action) -> None: - if isinstance(action, (ScalarMultiplicationAction, PrecomputationAction)): + if (self._track_precomp and isinstance(action, PrecomputationAction)) or (self._track_scalarmult and isinstance(action, ScalarMultiplicationAction)): 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. @@ -100,10 +130,12 @@ class MultipleContext(Context): self.precomp = {} def exit_action(self, action: Action) -> None: - if isinstance(action, (ScalarMultiplicationAction, PrecomputationAction)): + if (self._track_precomp and isinstance(action, PrecomputationAction)) or (self._track_scalarmult and isinstance(action, ScalarMultiplicationAction)): self.inside.remove(action) if isinstance(action, PrecomputationAction): self.precomp.update(action.result) + if isinstance(action, ScalarMultiplicationAction): + self.result = action.result if isinstance(action, FormulaAction) and self.inside: action = cast(FormulaAction, action) shortname = action.formula.shortname @@ -156,6 +188,35 @@ class MultipleContext(Context): def __repr__(self): return f"{self.__class__.__name__}({self.base!r}, multiples={self.points.values()!r})" + def to_networkx(self) -> nx.DiGraph: + """ + Convert the context to a NetworkX graph. + + The nodes represent points, with attributes: + - multiple: The multiple of the base point. + - formula: The formula used to compute the point. + - precomp: Whether the point was the result of precomputation. + - result: Whether the point is the final result of the computation. + + The edges represent the computation steps, with attribute: + - formula: The formula used to compute the child point from the parent point. + + :return: A NetworkX DiGraph representing the computation. + """ + graph = nx.DiGraph() + for point, multiple in self.points.items(): + graph.add_node( + point, + multiple=multiple, + formula=self.formulas[point], + precomp=point in self.precomp.values(), + result=point == self.result, + ) + for point, parents in self.parents.items(): + for parent in parents: + graph.add_edge(parent, point, formula=self.formulas[point]) + return graph + @public def rpa_point_0y(params: DomainParameters) -> Optional[Point]: @@ -431,28 +492,29 @@ def multiple_graph( :param mult_factory: A callable that takes the formulas and instantiates the multiplier. :param dlog: Make an assumption that the symbolic input point is the `dlog` multiple of the base point. This is necessary if the multiplier does computation with the base point. - :return: The context with the computed multiples and the resulting point. + :return: The context with the computed multiples during precomputation, the context with the computed multiples + during the full computation, and the resulting point. """ params = fake_params(params) mult = cached_fake_mult(mult_class, mult_factory, params) - ctx = MultipleContext(keep_base=True) - with local(ctx, copy=False) as precomp_ctx: + precomp_ctx = MultipleContext(keep_base=True, track_scalarmult=False, track_precomp=True) + full_ctx = MultipleContext(keep_base=True, track_scalarmult=True, track_precomp=True) + with local(compound(precomp_ctx, full_ctx), copy=False): point = FakePoint(params.curve.coordinate_model) - if dlog: - ctx.base = params.generator - ctx.neutral = params.curve.neutral - ctx.points[ctx.base] = 1 - ctx.points[point] = dlog - ctx.points[ctx.neutral] = 0 - ctx.formulas[ctx.base] = "" - ctx.formulas[point] = "" - ctx.formulas[ctx.neutral] = "" - ctx.parents[ctx.base] = [] - ctx.parents[point] = [] - ctx.parents[ctx.neutral] = [] + if dlog is not None: + for ctx in (precomp_ctx, full_ctx): + ctx.base = params.generator + ctx.neutral = params.curve.neutral + ctx.points[ctx.base] = 1 + ctx.points[point] = dlog + ctx.points[ctx.neutral] = 0 + ctx.formulas[ctx.base] = "" + ctx.formulas[point] = "" + ctx.formulas[ctx.neutral] = "" + ctx.parents[ctx.base] = [] + ctx.parents[point] = [] + ctx.parents[ctx.neutral] = [] mult.init(params, point) - - with local(ctx, copy=True) as full_ctx: out = mult.multiply(scalar) return precomp_ctx, full_ctx, out @@ -472,10 +534,11 @@ def multiples_from_graph( use_multiply: bool = True, ): """ + Compute the multiples computed for a given scalar and multiplier from the multiple graph. - :param precomp_ctx: - :param full_ctx: - :param out: + :param precomp_ctx: The context containing the points and formulas (precomputation phase). + :param full_ctx: The context containing the points and formulas (full computation). + :param out: The output point of the computation. :param kind: The kind of multiples to return. Can be one of "all", "input", "necessary", or "precomp+necessary". :param use_init: Whether to consider the point multiples that happen in scalarmult initialization. :param use_multiply: Whether to consider the point multiples that happen in scalarmult multiply (after initialization). @@ -569,7 +632,9 @@ def multiples_computed( .. note:: The scalar multiplier must not short-circuit. """ - precomp_ctx, full_ctx, out = multiple_graph(scalar, params, mult_class, mult_factory) + precomp_ctx, full_ctx, out = multiple_graph( + scalar, params, mult_class, mult_factory + ) return ( multiples_from_graph(precomp_ctx, full_ctx, out, kind, use_init, use_multiply) diff --git a/pyecsca/sca/re/tree.py b/pyecsca/sca/re/tree.py index a45faaa..6d07ba4 100644 --- a/pyecsca/sca/re/tree.py +++ b/pyecsca/sca/re/tree.py @@ -667,7 +667,7 @@ def _build_tree( ) log(pad + f"Split {len(group_cfgs)} via dmap {best_i}.") # And build the tree recursively - child = _build_tree(group_cfgs, maps, response=output, depth=depth + 1, index=i, breadth=groups.ngroups, split=split) + child = _build_tree(group_cfgs, maps, response=output, depth=depth + 1, index=i, breadth=groups.ngroups, split=split, leaf_callback=leaf_callback) child.parent = result return result |