Integrate formula expansion.

 - Moved into pyecsca.ec.formula subpackage.
 - Unified formula metrics.
 - Moved tests into tests with library_formula fixture.
 - Cleaned up typing.

1 files changed, 305 insertions, 23 deletions

diff --git a/test/ec/test_formula.py b/test/ec/test_formula.py
index bb3d123..0e19d91 100644
--- a/test/ec/test_formula.py
+++ b/test/ec/test_formula.py
@@ -1,13 +1,33 @@
 import pickle
+from typing import Tuple
 
 import pytest
 from sympy import FF, symbols
-
+from importlib_resources import files, as_file
+import test.data.formulas
+from pyecsca.ec.formula.fliparoo import generate_fliparood_formulas
+from pyecsca.ec.formula.graph import rename_ivs
+from pyecsca.ec.formula.partitions import (
+    reduce_all_adds,
+    expand_all_muls,
+    expand_all_nopower2_muls,
+)
+from pyecsca.ec.formula.switch_sign import generate_switched_formulas
 from pyecsca.ec.mod import SymbolicMod, Mod
 from pyecsca.misc.cfg import TemporaryConfig
 from pyecsca.ec.error import UnsatisfiedAssumptionError
-from pyecsca.ec.params import get_params
+from pyecsca.ec.params import get_params, DomainParameters
 from pyecsca.ec.point import Point
+from pyecsca.ec.model import ShortWeierstrassModel, MontgomeryModel, TwistedEdwardsModel
+from pyecsca.ec.formula import (
+    AdditionEFDFormula,
+    DoublingEFDFormula,
+    LadderEFDFormula,
+    Formula,
+    AdditionFormula,
+    DoublingFormula,
+    LadderFormula,
+)
 
 
 @pytest.fixture()
@@ -62,39 +82,27 @@ def test_num_ops(add):
 
 
 def test_assumptions(secp128r1, mdbl):
-    res = mdbl(
-        secp128r1.curve.prime,
-        secp128r1.generator,
-        **secp128r1.curve.parameters
-    )
+    res = mdbl(secp128r1.curve.prime, secp128r1.generator, **secp128r1.curve.parameters)
     assert res is not None
 
-    coords = {
-        name: value * 5 for name, value in secp128r1.generator.coords.items()
-    }
+    coords = {name: value * 5 for name, value in secp128r1.generator.coords.items()}
     other = Point(secp128r1.generator.coordinate_model, **coords)
     with pytest.raises(UnsatisfiedAssumptionError):
-        mdbl(
-            secp128r1.curve.prime, other, **secp128r1.curve.parameters
-        )
+        mdbl(secp128r1.curve.prime, other, **secp128r1.curve.parameters)
     with TemporaryConfig() as cfg:
         cfg.ec.unsatisfied_formula_assumption_action = "ignore"
-        pt = mdbl(
-            secp128r1.curve.prime, other, **secp128r1.curve.parameters
-        )
+        pt = mdbl(secp128r1.curve.prime, other, **secp128r1.curve.parameters)
         assert pt is not None
 
 
 def test_parameters():
     jac_secp128r1 = get_params("secg", "secp128r1", "jacobian")
-    jac_dbl = jac_secp128r1.curve.coordinate_model.formulas[
-        "dbl-1998-hnm"
-    ]
+    jac_dbl = jac_secp128r1.curve.coordinate_model.formulas["dbl-1998-hnm"]
 
     res = jac_dbl(
         jac_secp128r1.curve.prime,
         jac_secp128r1.generator,
-        **jac_secp128r1.curve.parameters
+        **jac_secp128r1.curve.parameters,
     )
     assert res is not None
 
@@ -111,9 +119,7 @@ def test_symbolic(secp128r1, dbl):
         coords, **{key: SymbolicMod(symbols(key), p) for key in coords.variables}
     )
     symbolic_double = dbl(p, symbolic_point, **sympy_params)[0]
-    generator_double = dbl(
-        p, secp128r1.generator, **secp128r1.curve.parameters
-    )[0]
+    generator_double = dbl(p, secp128r1.generator, **secp128r1.curve.parameters)[0]
     for outer_var in coords.variables:
         symbolic_val = getattr(symbolic_double, outer_var).x
         generator_val = getattr(generator_double, outer_var).x
@@ -126,3 +132,279 @@ def test_symbolic(secp128r1, dbl):
 
 def test_pickle(add, dbl):
     assert add == pickle.loads(pickle.dumps(add))
+
+
+LIBRARY_FORMULAS = [
+    [
+        "add-bc-r1rv76-jac",
+        ShortWeierstrassModel,
+        "jacobian",
+        ("secg", "secp128r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "add-bc-r1rv76-mod",
+        ShortWeierstrassModel,
+        "modified",
+        ("secg", "secp128r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "dbl-bc-r1rv76-jac",
+        ShortWeierstrassModel,
+        "jacobian",
+        ("secg", "secp128r1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "dbl-bc-r1rv76-mod",
+        ShortWeierstrassModel,
+        "modified",
+        ("secg", "secp128r1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "dbl-bc-r1rv76-x25519",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        DoublingEFDFormula,
+    ],
+    [
+        "ladd-bc-r1rv76-x25519",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        LadderEFDFormula,
+    ],
+    [
+        "dbl-boringssl-p224",
+        ShortWeierstrassModel,
+        "jacobian-3",
+        ("secg", "secp224r1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "add-boringssl-p224",
+        ShortWeierstrassModel,
+        "jacobian-3",
+        ("secg", "secp224r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "add-libressl-v382",
+        ShortWeierstrassModel,
+        "jacobian",
+        ("secg", "secp128r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "dbl-libressl-v382",
+        ShortWeierstrassModel,
+        "jacobian",
+        ("secg", "secp128r1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "dbl-secp256k1-v040",
+        ShortWeierstrassModel,
+        "jacobian",
+        ("secg", "secp256k1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "add-openssl-z256",
+        ShortWeierstrassModel,
+        "jacobian-3",
+        ("secg", "secp256r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "add-openssl-z256a",
+        ShortWeierstrassModel,
+        "jacobian-3",
+        ("secg", "secp256r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "ladd-openssl-x25519",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        LadderEFDFormula,
+    ],
+    [
+        "ladd-hacl-x25519",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        LadderEFDFormula,
+    ],
+    [
+        "dbl-hacl-x25519",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        DoublingEFDFormula,
+    ],
+    [
+        "dbl-sunec-v21",
+        ShortWeierstrassModel,
+        "projective-3",
+        ("secg", "secp256r1"),
+        DoublingEFDFormula,
+    ],
+    [
+        "add-sunec-v21",
+        ShortWeierstrassModel,
+        "projective-3",
+        ("secg", "secp256r1"),
+        AdditionEFDFormula,
+    ],
+    [
+        "add-sunec-v21-ed25519",
+        TwistedEdwardsModel,
+        "extended",
+        ("other", "Ed25519"),
+        AdditionEFDFormula,
+    ],
+    [
+        "dbl-sunec-v21-ed25519",
+        TwistedEdwardsModel,
+        "extended",
+        ("other", "Ed25519"),
+        DoublingEFDFormula,
+    ],
+    [
+        "ladd-rfc7748",
+        MontgomeryModel,
+        "xz",
+        ("other", "Curve25519"),
+        LadderEFDFormula,
+    ],
+]
+
+
+@pytest.fixture(params=LIBRARY_FORMULAS)
+def library_formula_params(request) -> Tuple[Formula, DomainParameters]:
+    name, model, coords_name, param_spec, formula_type = request.param
+    model = model()
+    coordinate_model = model.coordinates[coords_name]
+    with as_file(files(test.data.formulas).joinpath(name)) as meta_path, as_file(
+        files(test.data.formulas).joinpath(name + ".op3")
+    ) as op3_path:
+        formula = formula_type(meta_path, op3_path, name, coordinate_model)
+    params = get_params(*param_spec, coords_name)
+    return formula, params
+
+
+def choose_curve(coordinate_model, name, library):
+    if library:
+        return next(filter(lambda x: x[0] == name, LIBRARY_FORMULAS))[3]
+    model = coordinate_model.curve_model
+    if model.__class__ == ShortWeierstrassModel:
+        return "secg", "secp128r1"
+    if model.__class__ == MontgomeryModel:
+        return "other", "Curve25519"
+    if model.__class__ == TwistedEdwardsModel:
+        return "other", "Ed25519"
+    raise NotImplementedError(model)
+
+
+def test_formula_graph(library_formula_params):
+    formula, params = library_formula_params
+    do_test_formula(rename_ivs(formula), params)
+
+
+def test_switch_sign(library_formula_params):
+    formula, params = library_formula_params
+    for switch_formula in generate_switched_formulas(formula):
+        do_test_formula(switch_formula, params)
+
+
+def test_fliparood_formula(library_formula_params):
+    formula, params = library_formula_params
+    for fliparood in generate_fliparood_formulas(formula):
+        do_test_formula(fliparood, params)
+
+
+def test_reductions(library_formula_params):
+    formula, params = library_formula_params
+    do_test_formula(reduce_all_adds(formula), params)
+
+
+def test_expansions(library_formula_params):
+    formula, params = library_formula_params
+    do_test_formula(expand_all_muls(formula), params)
+    do_test_formula(expand_all_nopower2_muls(formula), params)
+
+
+def do_test_formula(formula, params):
+    try:
+        do_test_formula0(formula, params)
+    except AssertionError:
+        print(formula.name)
+
+
+def do_test_formula0(formula, params):
+    coordinate_model = formula.coordinate_model
+    scale = coordinate_model.formulas.get("z", None)
+    if scale is None:
+        scale = coordinate_model.formulas.get("scale", None)
+
+    formula_type = formula.__class__
+    for _ in range(10):
+        Paff = params.curve.affine_random()
+        P2aff = params.curve.affine_double(Paff)
+        Qaff = params.curve.affine_random()
+        Q2aff = params.curve.affine_double(Qaff)
+        Raff = params.curve.affine_add(Paff, Qaff)
+        R2aff = params.curve.affine_double(Raff)
+        QRaff = params.curve.affine_add(Qaff, Raff)
+        P = Paff.to_model(coordinate_model, params.curve)
+        P2 = P2aff.to_model(coordinate_model, params.curve)
+        Q = Qaff.to_model(coordinate_model, params.curve)
+        Q2 = Q2aff.to_model(coordinate_model, params.curve)
+        R = Raff.to_model(coordinate_model, params.curve)
+        R2 = R2aff.to_model(coordinate_model, params.curve)  # noqa
+        QR = QRaff.to_model(coordinate_model, params.curve)
+        inputs = (P, Q, R)[: formula.num_inputs]
+        res = formula(params.curve.prime, *inputs, **params.curve.parameters)
+        if issubclass(formula_type, AdditionFormula):
+            try:
+                assert res[0].to_affine() == Raff
+            except NotImplementedError:
+                assert (
+                    scale(params.curve.prime, res[0], **params.curve.parameters)[0] == R
+                )
+        elif issubclass(formula_type, DoublingFormula):
+            try:
+                assert res[0].to_affine() == P2aff
+            except NotImplementedError:
+                assert (
+                    scale(params.curve.prime, res[0], **params.curve.parameters)[0]
+                    == P2
+                )
+        elif issubclass(formula_type, LadderFormula):
+            try:
+                assert res[0].to_affine() == Q2aff
+                assert res[1].to_affine() == QRaff
+            except NotImplementedError:
+                # print(scale(params.curve.prime, res[0], **params.curve.parameters)[0])
+                # print(scale(params.curve.prime, res[1], **params.curve.parameters)[0])
+                # print(P)
+                # print(Q)
+                # print(R)
+                # print(P2)
+                # print(Q2)
+                # print(R2)
+                # print(QR)
+                # print("------------------------------------")
+                assert (
+                    scale(params.curve.prime, res[1], **params.curve.parameters)[0]
+                    == QR
+                )
+                assert (
+                    scale(params.curve.prime, res[0], **params.curve.parameters)[0]
+                    == Q2
+                )