Add special cases to ZVP point construction.

3 files changed, 68 insertions, 28 deletions

diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py
index b0aebed..206fc5e 100644
--- a/pyecsca/sca/re/zvp.py
+++ b/pyecsca/sca/re/zvp.py
@@ -293,46 +293,84 @@ def eliminate_y(poly: Poly, curve: EllipticCurve) -> Poly:
 
 
 @public
-def zvp_points(poly: Poly, curve: EllipticCurve, k: int) -> Set[Point]:
+def zvp_points(poly: Poly, curve: EllipticCurve, k: int, n: int) -> Set[Point]:
     """
     Find a set of (affine) ZVP points for a given intermediate value and dlog relationship.
 
     :param poly: The polynomial to zero out, obtained as a result of :py:meth:`.unroll_formula` (or its factor).
     :param curve: The curve to compute over.
     :param k: The discrete-log relationship between the two points, i.e. (x2, x2) = [k](x1, x1)
+    :param n: The curve order.
     :return: The set of points (x1, x1).
     """
     # If input poly is trivial (only in params), abort early
     if not set(symbols("x1,x2,y1,y2")).intersection(poly.gens):  # type: ignore[attr-defined]
         return set()
     poly = Poly(poly, domain=FF(curve.prime))
+    only_1 = all((not str(gen).endswith("2")) for gen in poly.gens)
+    only_2 = all((not str(gen).endswith("1")) for gen in poly.gens)
     # Start with removing all squares of Y1, Y2
     subbed = subs_curve_equation(poly, curve)
     # Remove the Zs by setting them to 1
     removed = remove_z(subbed)
-    # Now remove the rest of the Ys by clever curve equation use
+    # Now remove the rest of the Ys by clever curve equation use, the poly is x-only now
     eliminated = eliminate_y(removed, curve)
-    # Substitute in the mult-by-k map
-    dlog = subs_dlog(eliminated, k, curve)
-    # Put in concrete curve parameters
-    final = subs_curve_params(dlog, curve)
-    # Find the roots (X1)
-    roots = final.ground_roots()
     points = set()
-    # 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))
-        # 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,
-                **curve.parameters,
-            }
-            res = poly.eval([inputs[str(gen)] for gen in poly.gens])  # type: ignore[attr-defined]
-            if res == 0:
-                points.add(point)
+    # Now decide on the special case:
+    if only_1:
+        # if only_1, dlog sub is not necessary, also computing the other point is not necessary
+        final = subs_curve_params(eliminated, curve)
+        roots = final.ground_roots()
+        for root, multiplicity in roots.items():
+            pt = curve.affine_lift_x(Mod(int(root), curve.prime))
+            for point in pt:
+                inputs = {
+                    "x1": point.x,
+                    "y1": point.y,
+                    **curve.parameters
+                }
+                res = poly.eval([inputs[str(gen)] for gen in poly.gens])  # type: ignore[attr-defined]
+                if res == 0:
+                    points.add(point)
+    elif only_2:
+        # if only_2, dlog sub is not necessary, then multiply with k_inverse to obtain target point
+        final = subs_curve_params(eliminated, curve)
+        roots = final.ground_roots()
+        k_inv = Mod(k, n).inverse()
+        for root, multiplicity in roots.items():
+            pt = curve.affine_lift_x(Mod(int(root), curve.prime))
+            for point in pt:
+                inputs = {
+                    "x2": point.x,
+                    "y2": point.y,
+                    **curve.parameters
+                }
+                res = poly.eval([inputs[str(gen)] for gen in poly.gens])  # type: ignore[attr-defined]
+                if res == 0:
+                    one = curve.affine_multiply(point, int(k_inv))
+                    points.add(one)
+    else:
+        # otherwise we need to sub in the dlog and solve the general case
+        # Substitute in the mult-by-k map
+        dlog = subs_dlog(eliminated, k, curve)
+        # Put in concrete curve parameters
+        final = subs_curve_params(dlog, curve)
+        # Find the roots (X1)
+        roots = final.ground_roots()
+        # 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))
+            # 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,
+                    **curve.parameters,
+                }
+                res = poly.eval([inputs[str(gen)] for gen in poly.gens])  # type: ignore[attr-defined]
+                if res == 0:
+                    points.add(point)
     return points
diff --git a/test/sca/perf_zvp.py b/test/sca/perf_zvp.py
index a329d59..ba8ee11 100644
--- a/test/sca/perf_zvp.py
+++ b/test/sca/perf_zvp.py
@@ -38,7 +38,7 @@ def main(profiler, mod, operations, directory):
         )
         with Profiler(profiler, directory, f"zvp_p128_{operations}_{mod}"):
             for _ in range(operations):
-                zvp_points(poly, p128.curve, k)
+                zvp_points(poly, p128.curve, k, p128.order)
 
 
 if __name__ == "__main__":
diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py
index 56266f6..e0e4cfe 100644
--- a/test/sca/test_zvp.py
+++ b/test/sca/test_zvp.py
@@ -131,7 +131,7 @@ def test_zvp(secp128r1, formula):
     unrolled = unroll_formula(formula, affine=True)
     # Try all intermediates, zvp_point should return empty set if ZVP points do not exist
     for poly in unrolled:
-        points = zvp_points(poly, secp128r1.curve, 5)
+        points = zvp_points(poly, secp128r1.curve, 5, secp128r1.order)
         assert isinstance(points, set)
 
         # If points are produced, try them all.
@@ -150,7 +150,9 @@ def test_zvp(secp128r1, formula):
     ("y1 + y2", (54027047743185503031379008986257148598, 42633567686060343012155773792291852040), 4),
     ("x1 + x2", (285130337309757533508049972949147801522, 55463852278545391044040942536845640298), 3),
     ("x1*x2 + y1*y2", (155681799415564546404955983367992137717, 227436010604106449719780498844151836756), 5),
-    ("y1*y2 - x1*a - x2*a - 3*b", (169722400242675158455680894146658513260, 33263376472545436059176357032150610796), 4)
+    ("y1*y2 - x1*a - x2*a - 3*b", (169722400242675158455680894146658513260, 33263376472545436059176357032150610796), 4),
+    ("x1", (0, 594107526960909229279178399525926007), 3),
+    ("x2", (234937379492809870217296988280059595814, 101935882302108071650074851009662355573), 4),
 ])
 def test_points(secp128r1, poly_str, point, k):
     pt = Point(AffineCoordinateModel(secp128r1.curve.model),
@@ -158,5 +160,5 @@ def test_points(secp128r1, poly_str, point, k):
                y=Mod(point[1], secp128r1.curve.prime))
     poly_expr = sympify(poly_str)
     poly = Poly(poly_expr, domain=FF(secp128r1.curve.prime))
-    res = zvp_points(poly, secp128r1.curve, k)
+    res = zvp_points(poly, secp128r1.curve, k, secp128r1.order)
     assert pt in res