From 538a06b79c029a4a9cc8e0f7724cbf3af36c1951 Mon Sep 17 00:00:00 2001
From: J08nY
Date: Tue, 29 Aug 2023 22:42:44 +0200
Subject: Cleanup ZVP computation.

---
 Makefile                 |  2 +-
 pyecsca/sca/re/zvp.py    | 13 +++++++++++--
 test/ec/bench_divpoly.py | 34 ++++++++++++++++++++++++++++++++++
 test/ec/perf_divpoly.py  | 30 ------------------------------
 test/sca/perf_zvp.py     | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 test/sca/test_zvp.py     | 30 ++++++++++++++++--------------
 6 files changed, 108 insertions(+), 47 deletions(-)
 create mode 100755 test/ec/bench_divpoly.py
 delete mode 100755 test/ec/perf_divpoly.py
 create mode 100644 test/sca/perf_zvp.py

diff --git a/Makefile b/Makefile
index c6b67f4..537e885 100644
--- a/Makefile
+++ b/Makefile
@@ -9,7 +9,7 @@ test.sca.test_zvp test.sca.test_stacked_combine test.sca.test_leakage_models
 
 TESTS = ${EC_TESTS} ${SCA_TESTS}
 
-PERF_SCRIPTS = test.ec.perf_mod test.ec.perf_formula test.ec.perf_mult test.sca.perf_combine
+PERF_SCRIPTS = test.ec.perf_mod test.ec.perf_formula test.ec.perf_mult test.sca.perf_combine test.sca.perf_zvp
 
 test:
 	pytest -m "not slow" --cov=pyecsca
diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py
index 9d1a6d1..b6e5fd0 100644
--- a/pyecsca/sca/re/zvp.py
+++ b/pyecsca/sca/re/zvp.py
@@ -105,7 +105,7 @@ def subs_dlog(poly: Poly, k: int, curve: EllipticCurve):
     :return:
     """
     X1, X2 = symbols("X1,X2")
-    if X2 not in poly.gens:
+    if X2 not in poly.gens or X1 not in poly.gens:
         return poly
     max_degree = poly.degree(X2)
     X2i = poly.gens.index(X2)
@@ -194,6 +194,9 @@ def zvp_point(poly: Poly, curve: EllipticCurve, k: int) -> Set[Point]:
     :param k: The discrete-log relationship between the two points, i.e. (X2, Y2) = [k](X1, Y1)
     :return: The set of points (X1, Y1).
     """
+    # If input poly is trivial (only in params), abort early
+    if not set(symbols("X1,X2,Y1,Y2")).intersection(poly.gens):
+        return set()
     # Start with removing all squares of Y1, Y2
     subbed = subs_curve_equation(poly, curve)
     # Remove the Zs by setting them to 1
@@ -210,5 +213,11 @@ def zvp_point(poly: Poly, curve: EllipticCurve, k: int) -> Set[Point]:
     # Finally lift the roots to find the points (if any)
     for root, multiplicity in roots.items():
         pt = curve.affine_lift_x(Mod(int(root), curve.prime))
-        points.update(pt)
+        # Check that the points zero out the original polynomial to filter out erroneous candidates
+        for point in pt:
+            other = curve.affine_multiply(point, k)
+            inputs = {"X1": point.x, "Y1": point.y, "X2": other.x, "Y2": other.y, "Z1": 1, "Z2": 1, **curve.parameters}
+            res = poly.eval([inputs[str(gen)] for gen in poly.gens])
+            if res == 0:
+                points.add(point)
     return points
diff --git a/test/ec/bench_divpoly.py b/test/ec/bench_divpoly.py
new file mode 100755
index 0000000..0df7d59
--- /dev/null
+++ b/test/ec/bench_divpoly.py
@@ -0,0 +1,34 @@
+#!/usr/bin/env python
+import sys
+
+import click
+
+from pyecsca.ec.divpoly import mult_by_n
+from pyecsca.ec.params import get_params
+from datetime import datetime
+
+
+@click.command()
+@click.option("-n", type=click.INT, default=21)
+def main(n):
+    p256 = get_params("secg", "secp256r1", "projective")
+
+    print("Benchmarking divpoly computation on P-256...", file=sys.stderr)
+
+    ns = []
+    durs = []
+    mems = []
+    for i in range(2, n):
+        start = datetime.now()
+        mx, my = mult_by_n(p256.curve, i)
+        end = datetime.now()
+        duration = (end - start).total_seconds()
+        memory = (mx[0].degree() + mx[1].degree() + my[0].degree() + my[1].degree()) * 32
+        ns.append(i)
+        durs.append((end - start).total_seconds())
+        mems.append(memory)
+        print(i, duration, memory, sep=",")
+
+
+if __name__ == "__main__":
+    main()
diff --git a/test/ec/perf_divpoly.py b/test/ec/perf_divpoly.py
deleted file mode 100755
index 2937af1..0000000
--- a/test/ec/perf_divpoly.py
+++ /dev/null
@@ -1,30 +0,0 @@
-#!/usr/bin/env python
-import click
-
-from pyecsca.ec.divpoly import mult_by_n
-from pyecsca.ec.params import get_params
-from datetime import datetime
-
-
-@click.command()
-@click.option("-n", type=click.INT, default=21)
-def main(n):
-    p256 = get_params("secg", "secp256r1", "projective")
-
-    ns = []
-    durs = []
-    mems = []
-    for i in range(2, n):
-        start = datetime.now()
-        mx, my = mult_by_n(p256.curve, i)
-        end = datetime.now()
-        duration = (end - start).total_seconds()
-        memory = (mx[0].degree() + mx[1].degree() + my[0].degree() + my[1].degree()) * 32
-        ns.append(i)
-        durs.append((end - start).total_seconds())
-        mems.append(memory)
-        print(i, duration, memory, sep=",")
-
-
-if __name__ == "__main__":
-    main()
diff --git a/test/sca/perf_zvp.py b/test/sca/perf_zvp.py
new file mode 100644
index 0000000..fd0e7d1
--- /dev/null
+++ b/test/sca/perf_zvp.py
@@ -0,0 +1,46 @@
+#!/usr/bin/env python
+import click
+
+from datetime import datetime
+from pyecsca.ec.mod import has_gmp
+from pyecsca.misc.cfg import TemporaryConfig
+from pyecsca.sca.re.zvp import zvp_point, unroll_formula
+from pyecsca.ec.params import get_params
+from test.utils import Profiler
+
+
+@click.command()
+@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py")
+@click.option(
+    "-m",
+    "--mod",
+    type=click.Choice(("python", "gmp")),
+    default="gmp" if has_gmp else "python",
+)
+@click.option("-o", "--operations", type=click.INT, default=1)
+@click.option(
+    "-d",
+    "--directory",
+    type=click.Path(file_okay=False, dir_okay=True),
+    default=None,
+    envvar="DIR",
+)
+def main(profiler, mod, operations, directory):
+    with TemporaryConfig() as cfg:
+        cfg.ec.mod_implementation = mod
+        p128 = get_params("secg", "secp128r1", "projective")
+        formula = p128.curve.coordinate_model.formulas["add-2016-rcb"]
+        unrolled = unroll_formula(formula, p128.curve.prime)
+        poly = unrolled[7]
+        k = 5
+
+        click.echo(
+            f"Profiling {operations} {p128.curve.prime.bit_length()}-bit (k = {k}) ZVP computations..."
+        )
+        with Profiler(profiler, directory, f"zvp_p128_{operations}_{mod}"):
+            for _ in range(operations):
+                zvp_point(poly, p128.curve, k)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py
index bcca4e1..28ed5d9 100644
--- a/test/sca/test_zvp.py
+++ b/test/sca/test_zvp.py
@@ -3,7 +3,6 @@ import pytest
 from pyecsca.sca.re.zvp import unroll_formula, subs_curve_equation, remove_z, eliminate_y, subs_dlog, subs_curve_params, \
     zvp_point
 from pyecsca.ec.context import local, DefaultContext
-from pyecsca.ec.formula import FormulaAction
 from sympy import symbols, Poly
 
 
@@ -68,18 +67,21 @@ def test_full(secp128r1, formula):
     assert final.gens == (X1,)
 
 
+@pytest.mark.slow
 def test_zvp(secp128r1, formula):
     unrolled = unroll_formula(formula, secp128r1.curve.prime)
-    poly = unrolled[-2]
-    points = zvp_point(poly, secp128r1.curve, 5)
-    assert isinstance(points, set)
-
-    for point in points:
-        second_point = secp128r1.curve.affine_multiply(point, 5)
-        p = point.to_model(formula.coordinate_model, secp128r1.curve)
-        q = second_point.to_model(formula.coordinate_model, secp128r1.curve)
-        with local(DefaultContext()) as ctx:
-            formula(secp128r1.curve.prime, p, q, **secp128r1.curve.parameters)
-        action = next(iter(ctx.actions.keys()))
-        results = list(map(lambda o: int(o.value), action.op_results))
-        assert 0 in results
+    # Try all intermediates, zvp_point should return empty set if ZVP points do not exist
+    for poly in unrolled:
+        points = zvp_point(poly, secp128r1.curve, 5)
+        assert isinstance(points, set)
+
+        # If points are produced, try them all.
+        for point in points:
+            second_point = secp128r1.curve.affine_multiply(point, 5)
+            p = point.to_model(formula.coordinate_model, secp128r1.curve)
+            q = second_point.to_model(formula.coordinate_model, secp128r1.curve)
+            with local(DefaultContext()) as ctx:
+                formula(secp128r1.curve.prime, p, q, **secp128r1.curve.parameters)
+            action = next(iter(ctx.actions.keys()))
+            results = list(map(lambda o: int(o.value), action.op_results))
+            assert 0 in results
-- 
cgit v1.2.3-70-g09d2