Merge pull request #43 from vojtechsu/master

Add filtering of non-homogeneous polynomials

3 files changed, 70 insertions, 4 deletions

diff --git a/pyecsca/ec/coordinates.py b/pyecsca/ec/coordinates.py
index 8684223..25c4d09 100644
--- a/pyecsca/ec/coordinates.py
+++ b/pyecsca/ec/coordinates.py
@@ -86,6 +86,7 @@ class EFDCoordinateModel(CoordinateModel):
         self.satisfying = []
         self.toaffine = []
         self.tosystem = []
+        self.homogweights = {}
         self.parameters = []
         self.assumptions = []
         self.neutral = []
@@ -146,6 +147,12 @@ class EFDCoordinateModel(CoordinateModel):
                         self.tosystem.append(code)
                     except SyntaxError:
                         pass
+                elif line.startswith("homogweight"):
+                    try:
+                        var, weight = line[11:].split("=")
+                        self.homogweights[var.strip()] = int(weight)
+                    except SyntaxError:
+                        pass
                 elif line.startswith("parameter"):
                     self.parameters.append(line[10:])
                 elif line.startswith("assume"):
diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py
index 9189ae7..8aae076 100644
--- a/pyecsca/sca/re/zvp.py
+++ b/pyecsca/sca/re/zvp.py
@@ -70,6 +70,8 @@ def unroll_formula(formula: Formula, affine: bool = False) -> List[Tuple[str, Po
         locls[op.result] = result
         values.append((op.result, result))
 
+    values = filter_out_nonhomogenous_polynomials(formula, values)
+
     results = []
     for result_var, value in values:
         if affine:
@@ -89,6 +91,61 @@ def unroll_formula(formula: Formula, affine: bool = False) -> List[Tuple[str, Po
     return results
 
 
+def filter_out_nonhomogenous_polynomials(formula: Formula, unrolled: List[Tuple[str, Poly]]) -> List[Tuple[str, Poly]]:
+    """
+    Remove unrolled polynomials from unrolled formula that are not homogenous.
+
+    :param formula: The original formula.
+    :param unrolled: The unrolled formula to filter.
+    :return: The filtered unrolled formula.
+    """
+    if "mmadd" in formula.name:
+        return unrolled
+    homogenity_weights = formula.coordinate_model.homogweights
+    
+    # we have to group variables by points and check homogenity for each group
+    input_variables_grouped = {}
+    for var in formula.inputs:
+        # here we assume that the index of the variable is <10 and on the last position
+        group = input_variables_grouped.setdefault(var[-1],[])
+        group.append(var)
+
+    # zadd formulas have Z1=Z2 and so we put all variables in the same group
+    if "zadd" in formula.name:
+        input_variables_grouped = {1: sum(input_variables_grouped.values(), [])}
+
+    filtered_unroll = []
+    for name, polynomial in unrolled:
+        homogenous = True
+        for point_index, variables in input_variables_grouped.items():
+            weighted_variables = [(var, homogenity_weights[var[:-1]]) for var in variables]
+
+            # we dont check homogenity for the second point in madd formulas (which is affine)
+            if "madd" in formula.name and point_index == 2:
+                continue
+            homogenous &= is_homogeneous(Poly(polynomial), weighted_variables)
+        if homogenous:
+            filtered_unroll.append((name, polynomial))
+    return filtered_unroll   
+            
+
+def is_homogeneous(polynomial: Poly, weighted_variables: List[Tuple[str, int]]) -> bool:
+    """
+    Determines whether the polynomial is homogenous with respect to the variables and their weights.
+
+    :param polynomial: The polynomial.
+    :param weighted_variables: The variables and their weights.
+    :return: True if the polynomial is homogenous, otherwise False.
+    """
+    hom = symbols('hom')
+    new_gens = polynomial.gens+(hom,)
+    univariate_poly = polynomial.subs({var: hom**weight for var, weight in weighted_variables})
+    univariate_poly = Poly(univariate_poly, *new_gens, domain = polynomial.domain)
+    hom_index = univariate_poly.gens.index(hom)
+    degrees = set(monom[hom_index] for monom in univariate_poly.monoms())
+    return len(degrees)<=1
+
+
 @public
 def compute_factor_set(formula: Formula, affine: bool = False) -> Set[Poly]:
     """
diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py
index f54f72a..d7e3a42 100644
--- a/test/sca/test_zvp.py
+++ b/test/sca/test_zvp.py
@@ -9,7 +9,7 @@ from pyecsca.ec.context import local, DefaultContext
 from sympy import symbols, Poly, sympify, FF
 
 
-@pytest.fixture(params=["add-2007-bl", "add-2015-rcb"])
+@pytest.fixture(params=["add-2007-bl", "add-2015-rcb", "dbl-2007-bl"])
 def formula(secp128r1, request):
     return secp128r1.curve.coordinate_model.formulas[request.param]
 
@@ -36,8 +36,8 @@ def test_factor_set(formula):
             # "x2", RPA
             # "x1", RPA
             "x1 + x2",
-            "y1^2 + 2*y1*y2 + y2^2 + x1 + x2",
-            "y1^2 + 2*y1*y2 + y2^2 + 2*x1 + 2*x2",
+            #"y1^2 + 2*y1*y2 + y2^2 + x1 + x2", Non-homogenous
+            #"y1^2 + 2*y1*y2 + y2^2 + 2*x1 + 2*x2", Non-homogenous
             "x1^2 + x1*x2 + x2^2",
             "a + x1^2 + x1*x2 + x2^2",
             # "a^2 + x1^4 + 2*x1^3*x2 + 3*x1^2*x2^2 + 2*x1*x2^3 + x2^4 - x1*y1^2 - x2*y1^2 - 2*x1*y1*y2 - 2*x2*y1*y2 - x1*y2^2 - x2*y2^2 + 2*x1^2*a + 2*x1*x2*a + 2*x2^2*a", RPA
@@ -70,7 +70,9 @@ def test_factor_set(formula):
             # "x2*y1^2*y2 + x1*y1*y2^2 - 2*x1*x2*y1*a - x2^2*y1*a - x1^2*y2*a - 2*x1*x2*y2*a + y1*a^2 + y2*a^2 - 3*x1*y1*b - 6*x2*y1*b - 6*x1*y2*b - 3*x2*y2*b", RPA
             # "3*x1*x2^2*y1 + 3*x1^2*x2*y2 + y1^2*y2 + y1*y2^2 + x1*y1*a + 2*x2*y1*a + 2*x1*y2*a + x2*y2*a + 3*y1*b + 3*y2*b", RPA
             # "-3*x1^2*x2^2*a - y1^2*y2^2 + x1^2*a^2 + 4*x1*x2*a^2 + x2^2*a^2 - 9*x1^2*x2*b - 9*x1*x2^2*b + a^3 + 3*x1*a*b + 3*x2*a*b + 9*b^2" RPA
-        }
+        },
+        "dbl-2007-bl": {"a + 3*x1^2", "a^2 + 6*x1^2*a + 9*x1^4 - 12*x1*y1^2"}
+
     }
     if formula.name in expected_factors:
         expected_set = set(map(lambda s: Poly(s).as_expr(), expected_factors[formula.name]))