1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
"""
Provides functionality inspired by the Exceptional Procedure Attack [EPA]_.
"""
from typing import Callable, Literal, Union, Optional
from public import public
from pyecsca.ec.point import Point
from pyecsca.sca.re.rpa import MultipleContext
@public
def graph_to_check_inputs(
precomp_ctx: MultipleContext,
full_ctx: MultipleContext,
out: Point,
check_condition: Union[Literal["all"], Literal["necessary"]],
precomp_to_affine: bool,
use_init: bool = True,
use_multiply: bool = True,
check_formulas: Optional[set[str]] = None,
) -> dict[str, set[tuple[int, ...]]]:
"""
Compute the inputs for the checks based on the context and output point. This function traverses the graph of points
and collects the inputs for each formula type, in the form of tuples of input multiples. It also adds a special
"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 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.
: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).
:param check_formulas: If provided, only formulas in this set will be considered for checks.
:return: A dictionary mapping formula names to sets of tuples of input multiples.
.. note::
The scalar multiplier must not short-circuit.
"""
if not use_init and not use_multiply:
raise ValueError("At least one of use_init or use_multiply must be True.")
affine_points: set[Point] = set()
if use_init and use_multiply:
affine_points = (
{out, *precomp_ctx.precomp.values()} if precomp_to_affine else {out}
)
elif use_init:
affine_points = {*precomp_ctx.precomp.values()} if precomp_to_affine else set()
elif use_multiply:
affine_points = {out}
def _necessary(ctx, for_what):
res = {out}
queue = {*for_what}
while queue:
point = queue.pop()
for parent in ctx.parents[point]:
res.add(parent)
queue.add(parent)
return res
points: set[Point] = set()
if check_condition == "all":
if use_init and use_multiply:
points = set(full_ctx.points.keys())
elif use_init:
points = set(precomp_ctx.points.keys())
elif use_multiply:
points = set(full_ctx.points.keys()) - set(precomp_ctx.points.keys())
elif check_condition == "necessary":
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())
elif use_multiply:
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
formula_checks: dict[str, set[tuple[int, ...]]] = {
"affine": {(full_ctx.points[point],) for point in affine_points}
}
# This actually passes the multiple itself to the check, not the inputs(parents)
# Now handle the regular checks
def get_point(pt):
return full_ctx.points[pt]
for point in points:
formula = full_ctx.formulas[point]
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]))
check_list = formula_checks.setdefault(formula, set())
check_list.add(inputs)
return formula_checks
@public
def evaluate_checks(
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.
: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
of the base point and `q` is the base point order.
- `check(k)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple
of the base point and `q` is the base point order.
:param check_inputs: A dictionary mapping formula names to sets of tuples of input multiples. The output of
:func:`graph_to_check_inputs`.
:return: Whether any of the checks returned True -> whether the computation errors out.
.. note::
The scalar multiplier must not short-circuit.
"""
for name, func in check_funcs.items():
if name not in check_inputs:
continue
for inputs in check_inputs[name]:
if func(*inputs):
return True
return False
@public
def errors_out(
precomp_ctx: MultipleContext,
full_ctx: MultipleContext,
out: Point,
check_funcs: dict[str, Union[Callable[[int, int], bool], Callable[[int], bool]]],
check_condition: Union[Literal["all"], Literal["necessary"]],
precomp_to_affine: bool,
use_init: bool = True,
use_multiply: bool = True,
) -> bool:
"""
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 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
of the base point and `q` is the base point order.
- `check(k)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple
of the base point and `q` is the base point order.
: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.
: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).
:return: Whether any of the checks returned True -> whether the computation 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)
return evaluate_checks(check_funcs, formula_checks)
|
