diff options
| -rw-r--r-- | pyecsca/ec/coordinates.py | 7 | ||||
| -rw-r--r-- | pyecsca/sca/re/zvp.py | 57 | ||||
| -rw-r--r-- | test/sca/test_zvp.py | 10 |
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])) |