diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | pyecsca/sca/re/zvp.py | 13 | ||||
| -rwxr-xr-x | test/ec/bench_divpoly.py (renamed from test/ec/perf_divpoly.py) | 4 | ||||
| -rw-r--r-- | test/sca/perf_zvp.py | 46 | ||||
| -rw-r--r-- | test/sca/test_zvp.py | 28 |
5 files changed, 77 insertions, 16 deletions
@@ -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/perf_divpoly.py b/test/ec/bench_divpoly.py index 2937af1..0df7d59 100755 --- a/test/ec/perf_divpoly.py +++ b/test/ec/bench_divpoly.py @@ -1,4 +1,6 @@ #!/usr/bin/env python +import sys + import click from pyecsca.ec.divpoly import mult_by_n @@ -11,6 +13,8 @@ from datetime import datetime def main(n): p256 = get_params("secg", "secp256r1", "projective") + print("Benchmarking divpoly computation on P-256...", file=sys.stderr) + ns = [] durs = [] mems = [] 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) + # 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) - 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 + # 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 |