Configuration space

This notebook explores the configuration space of Elliptic Curve crypto implementations.

An ECC implementation configuration in pyecsca has the following attributes:

from typing import get_args
from pyecsca.ec.configuration import Configuration
from dataclasses import fields

for field in fields(Configuration):
    name = field.name
    tp = field.type
    doc = tp.__doc__
    if get_args(field.type):
            doc = get_args(field.type)[0].__doc__
    print(name, tp)
    print("   ", doc)
    if hasattr(tp, "names"):
            for enum_name in tp.names():
                    print("       ", enum_name)
    print()

It is represented by the Configuration class.

Enumerating configurations

The possible configurations can be generated using the all_configurations() function. The whole space of configurations is quite huge.

Note that the amount of possible parametrizations of some scalar multipliers is very large (e.g. window size) so pyecsca has to resctrict this to a reasonable selection. Specifically the function below only considers a few options for window size and similar parameters.

from pyecsca.ec.configuration import all_configurations

total = sum(1 for _ in all_configurations())
print(total)

A large part of the configuration space is due to the independent options which consist of:

• hash_type of type HashType \(*6\)

• mod_rand of type RandomMod \(*2\)

• mult of type Multiplication \(*4\)

• sqr of type Squaring \(*4\)

• red of type Reduction \(*3\)

• inv of type Inversion \(*2\)

Without these, the space is somewhat smaller:

no_indep = (6*2*4*4*3*2)
no_ff = (6*2)

print(total // no_indep)

To restrict the generated configurations, pass keyword arguments to the all_configurations matching the names of the attributes of the Configuration object.

from pyecsca.ec.configuration import HashType, RandomMod, Multiplication, Squaring, Reduction, Inversion
from pyecsca.ec.model import ShortWeierstrassModel
from pyecsca.ec.mult import LTRMultiplier

model = ShortWeierstrassModel()
coords = model.coordinates["projective"]
scalarmult = LTRMultiplier
independent_opts = {
    "hash_type": HashType.SHA256,
    "mod_rand": RandomMod.SAMPLE,
    "mult": Multiplication.KARATSUBA,
    "sqr": Squaring.KARATSUBA,
    "red": Reduction.MONTGOMERY,
    "inv": Inversion.GCD
}

configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult,
                                                              **independent_opts))
print(len(configs))

We see that when we fixed all parameters except for the scalar multiplier arguments (see the LTRMultiplier constructor) we obtained 1280 configurations. That number expresses all of the possible ways to use addition formulas for the projective coordinate system in the binary left-to-right multiplier as well as internal options of that multiplier:

• whether it is “complete” in a sense that it starts processing at a constant bit (the bit-length od the order)

• whether it is “double-and-add-always”

• whether it “short-circuits” the formulas, i.e. detects that an exceptional point was input into them and returns correctly without executing them.

Models

We can explore the number of configurations for each of the supported curve models.

from IPython.display import HTML, display
import tabulate
from pyecsca.ec.model import *
from pyecsca.ec.mult import ProcessingDirection, AccumulationOrder

model_counts = [["Model", "All", "Without independent options", "Without independent options and scaling", "Without independent options and scalarmult options"]]
totals = ["Total", 0, 0, 0, 0]
for model in (ShortWeierstrassModel(), MontgomeryModel(), EdwardsModel(), TwistedEdwardsModel()):
    name = model.__class__.__name__
    count = sum(1 for _ in all_configurations(model=model, **independent_opts))
    count_no_scl = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={"scl": None}))
    count_no_opts = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={"scl": None, "always": True, "short_circuit": True, "complete": False, "precompute_negation": True, "width": 3, "m": 3, "direction": ProcessingDirection.LTR, "accumulation_order": AccumulationOrder.PeqPR, "recoding_direction": ProcessingDirection.LTR}))
    model_counts.append([name, count * no_ff, count, count_no_scl, count_no_opts])
    totals[1] += count * no_ff
    totals[2] += count
    totals[3] += count_no_scl
    totals[4] += count_no_opts
model_counts.append(totals)
display(HTML(tabulate.tabulate(model_counts, tablefmt="html", headers="firstrow")))

Coordinate systems

Let’s now look at the configuration split for coordinate systems:

coords_counts = [["Model", "Coords", "All", "Without independent options", "Without independent options and scaling", "Without independent options and scalarmult options"]]
for model in (ShortWeierstrassModel(), MontgomeryModel(), EdwardsModel(), TwistedEdwardsModel()):
    model_name = model.__class__.__name__
    coords_counts.append([model_name, "", "", "", "", ""])
    for coords in sorted(model.coordinates.values(), key=lambda c: c.name):
            coords_name = coords.name
            count = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts))
            count_no_scl = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={"scl": None}))
            count_no_opts = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={"scl": None, "always": True, "short_circuit": True, "complete": False, "precompute_negation": True, "width": 3, "m": 3, "direction": ProcessingDirection.LTR, "accumulation_order": AccumulationOrder.PeqPR, "recoding_direction": ProcessingDirection.LTR}))
            coords_counts.append(["", coords_name, count * no_ff, count, count_no_scl, count_no_opts])
display(HTML(tabulate.tabulate(coords_counts, tablefmt="html", headers="firstrow")))

Scalar multipliers

from pyecsca.ec.mult import ScalarMultiplier

def leaf_subclasses(cls):
    subs = cls.__subclasses__()
    result = set()
    for subclass in subs:
        if subclass.__subclasses__():
            result.update(leaf_subclasses(subclass))
        else:
            result.add(subclass)
    return result

mult_counts = [["ScalarMultiplier", "All", "Without independent options", "Without independent options and scaling", "Without independent options and scalarmult options"]]
for mult_cls in leaf_subclasses(ScalarMultiplier):
    count = sum(1 for _ in all_configurations(**independent_opts, scalarmult=mult_cls))
    count_no_scl = sum(1 for _ in all_configurations(**independent_opts, scalarmult={"cls": mult_cls, "scl": None}))
    count_no_opts = sum(1 for _ in all_configurations(**independent_opts, scalarmult={"cls": mult_cls, "scl": None, "always": True, "short_circuit": True, "complete": False, "precompute_negation": True, "width": 3, "m": 3, "direction": ProcessingDirection.LTR, "accumulation_order": AccumulationOrder.PeqPR, "recoding_direction": ProcessingDirection.LTR}))
    mult_counts.append([mult_cls.__name__, count * no_ff, count, count_no_scl, count_no_opts])
display(HTML(tabulate.tabulate(mult_counts, tablefmt="html", headers="firstrow")))