pyecsca.sca.re.rpa module

Provides functionality inspired by the Refined-Power Analysis attack by Goubin [RPA].

class MultipleContext(keep_base=False)

Bases: Context

Context that traces the multiples of points computed.

neutral: Optional[Point]

The neutral point used in the computation.

base: Optional[Point]

The base point that all the multiples are counted from.

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 their parent they were computed from.

formulas: MutableMapping[Point, str]

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: List[Action]

Whether we are inside a scalarmult/precomp action.

keep_base: bool

Whether to keep the base point when building upon it.

enter_action(action)

Enter into an action (i.e. start executing it).

Parameters:

action (Action) – The action.

Return type:

None

exit_action(action)

Exit from an action (i.e. stop executing it).

Parameters:

action (Action) – The action.

Return type:

None

rpa_point_0y(params)

Construct an (affine) [RPA] point (0, y) for given domain parameters.

Return type:

Optional[Point]

rpa_point_x0(params)

Construct an (affine) [RPA] point (x, 0) for given domain parameters.

Return type:

Optional[Point]

rpa_input_point(k, rpa_point, params)

Construct an (affine) input point P that will lead to an RPA point [k]P.

Return type:

Point

rpa_distinguish(params, multipliers, oracle, bound=None, tries=10, majority=1, use_init=True, use_multiply=True)

Distinguish the scalar multiplier used (from the possible multipliers) using an [RPA] oracle.

Parameters:

• params (DomainParameters) – The domain parameters to use.

• multipliers (List[ScalarMultiplier]) – The list of possible multipliers.

• oracle (Callable[[int, Point], bool]) – An oracle that returns True when an RPA point is encountered during scalar multiplication of the input by the scalar.

• bound (Optional[int]) – A bound on the size of the scalar to consider.

• tries (int) – Number of tries to get a non-trivial tree.

• majority (int) – Query the oracle up to majority times and take the majority vote of the results.

• use_init (bool) – Whether to consider the point multiples that happen in scalarmult initialization.

• use_multiply (bool) – Whether to consider the point multiples that happen in scalarmult multiply (after initialization).

Return type:

Set[ScalarMultiplier]

Returns:

The list of possible multipliers after distinguishing (ideally just one).

class RPA(configs)

Bases: RE

RPA-based RE.

tree: Optional[Tree] = None

The RE tree (if any).

configs: Set[Any]

The set of configurations to reverse-engineer.

params: Optional[DomainParameters] = None

The domain parameters to use.

P0: Optional[Point] = None

The zero-coordinate point that will be used in the RE.

scalars: Optional[List[int]] = None

A list of scalars that will be used in the RE.

build_tree(params, tries=10, bound=None, use_init=True, use_multiply=True)

Build an RPA distinguishing tree.

Parameters:

• params (DomainParameters) – The domain parameters to use.

• tries (int) – Number of tries to get a non-trivial tree.

• bound (Optional[int]) – A bound on the size of the scalar to consider.

• use_init (bool) – Whether to consider the point multiples that happen in scalarmult initialization.

• use_multiply (bool) – Whether to consider the point multiples that happen in scalarmult multiply (after initialization).

run(oracle, majority=1)

Run the RPA-RE with an oracle.

Parameters:

• oracle (Callable[[int, Point], bool]) – An oracle that returns True when an RPA point is encountered during scalar multiplication of the input by the scalar.

• majority (int) – Query the oracle up to majority times and take the majority vote of the results.

Return type:

Set[ScalarMultiplier]

Returns:

The set of possible multipliers.

multiple_graph(scalar, params, mult_class, mult_factory, dlog=None)

Compute the multiples computed for a given scalar and multiplier (quickly).

Parameters:

• scalar (int) – The scalar to compute for.

• params (DomainParameters) – The domain parameters to use.

• mult_class (Type[ScalarMultiplier]) – The class of the scalar multiplier to use.

• mult_factory (Callable) – A callable that takes the formulas and instantiates the multiplier.

• dlog (Optional[int]) – 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 type:

Tuple[MultipleContext, MultipleContext, Point]

Returns:

The context with the computed multiples and the resulting point.

multiples_from_graph(precomp_ctx, full_ctx, out, kind='all', use_init=True, use_multiply=True)

Parameters:

• precomp_ctx (MultipleContext)

• full_ctx (MultipleContext)

• out (Point)

• kind (Union[Literal['all'], Literal['input'], Literal['necessary'], Literal['precomp+necessary']]) – The kind of multiples to return. Can be one of “all”, “input”, “necessary”, or “precomp+necessary”.

• use_init (bool) – Whether to consider the point multiples that happen in scalarmult initialization.

• use_multiply (bool) – Whether to consider the point multiples that happen in scalarmult multiply (after initialization).

Returns:

A set of multiples computed for the scalar.

multiples_computed(scalar, params, mult_class, mult_factory, use_init=True, use_multiply=True, kind='all')

Compute the multiples computed for a given scalar and multiplier (quickly).

Parameters:

• scalar (int) – The scalar to compute for.

• params (DomainParameters) – The domain parameters to use.

• mult_class (Type[ScalarMultiplier]) – The class of the scalar multiplier to use.

• mult_factory (Callable) – A callable that takes the formulas and instantiates the multiplier.

• use_init (bool) – Whether to consider the point multiples that happen in scalarmult initialization.

• use_multiply (bool) – Whether to consider the point multiples that happen in scalarmult multiply (after initialization).

• kind (Union[Literal['all'], Literal['input'], Literal['necessary'], Literal['precomp+necessary']]) – The kind of multiples to return. Can be one of “all”, “input”, “necessary”, or “precomp+necessary”.

Return type:

set[int]

Returns:

A set of multiples computed for the scalar.

Note

The scalar multiplier must not short-circuit.