5 files changed, 127 insertions, 0 deletions

diff --git a/pyecsca/sca/re/structural.py b/pyecsca/sca/re/structural.py
new file mode 100644
index 0000000..4fa8508
--- /dev/null
+++ b/pyecsca/sca/re/structural.py
@@ -0,0 +1,67 @@
+""""""
+from typing import Dict
+
+from ...ec.curve import EllipticCurve
+from ...ec.formula import Formula
+from ...ec.context import DefaultContext, local
+from .zvp import unroll_formula
+from operator import itemgetter, attrgetter
+
+
+def formula_similarity(one: Formula, other: Formula) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        raise ValueError("Mismatched coordinate model.")
+
+    one_unroll = unroll_formula(one)
+    other_unroll = unroll_formula(other)
+    one_results = {name: None for name in one.outputs}
+    for name, value in one_unroll:
+        if name in one_results:
+            one_results[name] = value
+    other_results = {name: None for name in other.outputs}
+    for name, value in other_unroll:
+        if name in other_results:
+            other_results[name] = value
+    one_result_polys = set(one_results.values())
+    other_result_polys = set(other_results.values())
+    one_polys = set(map(itemgetter(1), one_unroll))
+    other_polys = set(map(itemgetter(1), other_unroll))
+    return {
+        "output": len(one_result_polys.intersection(other_result_polys))
+        / max(len(one_result_polys), len(other_result_polys)),
+        "ivs": len(one_polys.intersection(other_polys))
+        / max(len(one_polys), len(other_polys)),
+    }
+
+
+def formula_similarity_fuzz(
+    one: Formula, other: Formula, curve: EllipticCurve, samples: int = 1000
+) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        raise ValueError("Mismatched coordinate model.")
+
+    output_matches = 0.0
+    iv_matches = 0.0
+    for _ in range(samples):
+        P = curve.affine_random().to_model(one.coordinate_model, curve)
+        Q = curve.affine_random().to_model(other.coordinate_model, curve)
+        with local(DefaultContext()) as ctx:
+            res_one = one(curve.prime, P, Q, **curve.parameters)
+        action_one = ctx.actions.get_by_index([0])
+        ivs_one = set(
+            map(attrgetter("value"), sum(action_one[0].intermediates.values(), []))
+        )
+        with local(DefaultContext()) as ctx:
+            res_other = other(curve.prime, P, Q, **curve.parameters)
+        action_other = ctx.actions.get_by_index([0])
+        ivs_other = set(
+            map(attrgetter("value"), sum(action_other[0].intermediates.values(), []))
+        )
+        iv_matches += len(ivs_one.intersection(ivs_other)) / max(len(ivs_one), len(ivs_other))
+        one_coords = set(res_one)
+        other_coords = set(res_other)
+        output_matches += len(one_coords.intersection(other_coords)) / max(len(one_coords), len(other_coords))
+    return {
+        "output": output_matches / samples,
+        "ivs": iv_matches / samples
+    }
diff --git a/test/data/formulas/__init__.py b/test/data/formulas/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/data/formulas/__init__.py
diff --git a/test/data/formulas/add-bc-r1rv76 b/test/data/formulas/add-bc-r1rv76
new file mode 100644
index 0000000..c33b915
--- /dev/null
+++ b/test/data/formulas/add-bc-r1rv76
@@ -0,0 +1 @@
+source BouncyCastle r1rv76 https://github.com/bcgit/bc-java/blob/r1rv76/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java#L749
diff --git a/test/data/formulas/add-bc-r1rv76.op3 b/test/data/formulas/add-bc-r1rv76.op3
new file mode 100644
index 0000000..5e7f521
--- /dev/null
+++ b/test/data/formulas/add-bc-r1rv76.op3
@@ -0,0 +1,23 @@
+Z1Squared = Z1^2
+U2 = Z1Squared * X2
+Z1Cubed = Z1Squared * Z1
+S2 = Z1Cubed * Y2
+Z2Squared = Z2^2
+U1 = Z2Squared * X1
+Z2Cubed = Z2Squared * Z2
+S1 = Z2Cubed * Y1
+H = U1 - U2
+R = S1 - S2
+HSquared = H^2
+G = HSquared * H
+V = HSquared * U1
+t0 = 2 * V
+t1 = R^2
+t2 = t1 + G
+X3 = t2 - t0
+t3 = V - X3
+t4 = G * S1
+t5 = t3 * R
+Y3 = t5 - t4
+Z3 = H * Z1
+Z3 = Z3 * Z2
diff --git a/test/sca/test_structural.py b/test/sca/test_structural.py
new file mode 100644
index 0000000..db75b12
--- /dev/null
+++ b/test/sca/test_structural.py
@@ -0,0 +1,36 @@
+from importlib_resources import files, as_file
+import test.data.formulas
+from pyecsca.ec.formula import AdditionEFDFormula
+from pyecsca.ec.model import ShortWeierstrassModel
+from pyecsca.ec.params import get_params
+from pyecsca.sca.re.structural import formula_similarity, formula_similarity_fuzz
+
+
+def test_formula_match():
+    model = ShortWeierstrassModel()
+    coords = model.coordinates["jacobian"]
+    secp128r1 = get_params("secg", "secp128r1", "jacobian")
+    with as_file(
+        files(test.data.formulas).joinpath("add-bc-r1rv76")
+    ) as meta_path, as_file(
+        files(test.data.formulas).joinpath("add-bc-r1rv76.op3")
+    ) as op3_path:
+        bc_formula = AdditionEFDFormula(meta_path, op3_path, "add-bc-r1rv76", coords)
+    print()
+    for other_name, other_formula in coords.formulas.items():
+        if not other_name.startswith("add"):
+            continue
+        print(other_name, "fuzz", formula_similarity_fuzz(other_formula, bc_formula, secp128r1.curve, 1000), "symbolic", formula_similarity(other_formula, bc_formula))
+
+
+def test_efd_formula_match():
+    model = ShortWeierstrassModel()
+    coords = model.coordinates["modified"]
+    print()
+    for other_name, other_formula in coords.formulas.items():
+        if not other_name.startswith("add"):
+            continue
+        for one_name, one_formula in coords.formulas.items():
+            if not one_name.startswith("add"):
+                continue
+            print(one_name, other_name, formula_similarity(one_formula, other_formula))