diff options
Diffstat (limited to 'test/ec/test_formula.py')
| -rw-r--r-- | test/ec/test_formula.py | 426 |
1 files changed, 403 insertions, 23 deletions
diff --git a/test/ec/test_formula.py b/test/ec/test_formula.py index bb3d123..3f8d45c 100644 --- a/test/ec/test_formula.py +++ b/test/ec/test_formula.py @@ -1,13 +1,39 @@ import pickle +from operator import itemgetter +from typing import Tuple import pytest from sympy import FF, symbols - +from importlib_resources import files, as_file +import test.data.formulas +from pyecsca.ec.formula.expand import expand_formula_list +from pyecsca.ec.formula.fliparoo import generate_fliparood_formulas +from pyecsca.ec.formula.graph import rename_ivs +from pyecsca.ec.formula.metrics import ( + formula_similarity, + formula_similarity_abs, + formula_similarity_fuzz, +) +from pyecsca.ec.formula.partitions import ( + reduce_all_adds, + expand_all_muls, + expand_all_nopower2_muls, + generate_partitioned_formulas, +) +from pyecsca.ec.formula.switch_sign import generate_switched_formulas from pyecsca.ec.mod import SymbolicMod, Mod from pyecsca.misc.cfg import TemporaryConfig from pyecsca.ec.error import UnsatisfiedAssumptionError -from pyecsca.ec.params import get_params +from pyecsca.ec.params import get_params, DomainParameters from pyecsca.ec.point import Point +from pyecsca.ec.model import ShortWeierstrassModel, MontgomeryModel, TwistedEdwardsModel +from pyecsca.ec.formula.efd import ( + AdditionEFDFormula, + DoublingEFDFormula, + LadderEFDFormula, + EFDFormula, +) +from pyecsca.ec.formula import AdditionFormula, DoublingFormula, LadderFormula @pytest.fixture() @@ -62,39 +88,27 @@ def test_num_ops(add): def test_assumptions(secp128r1, mdbl): - res = mdbl( - secp128r1.curve.prime, - secp128r1.generator, - **secp128r1.curve.parameters - ) + res = mdbl(secp128r1.curve.prime, secp128r1.generator, **secp128r1.curve.parameters) assert res is not None - coords = { - name: value * 5 for name, value in secp128r1.generator.coords.items() - } + coords = {name: value * 5 for name, value in secp128r1.generator.coords.items()} other = Point(secp128r1.generator.coordinate_model, **coords) with pytest.raises(UnsatisfiedAssumptionError): - mdbl( - secp128r1.curve.prime, other, **secp128r1.curve.parameters - ) + mdbl(secp128r1.curve.prime, other, **secp128r1.curve.parameters) with TemporaryConfig() as cfg: cfg.ec.unsatisfied_formula_assumption_action = "ignore" - pt = mdbl( - secp128r1.curve.prime, other, **secp128r1.curve.parameters - ) + pt = mdbl(secp128r1.curve.prime, other, **secp128r1.curve.parameters) assert pt is not None def test_parameters(): jac_secp128r1 = get_params("secg", "secp128r1", "jacobian") - jac_dbl = jac_secp128r1.curve.coordinate_model.formulas[ - "dbl-1998-hnm" - ] + jac_dbl = jac_secp128r1.curve.coordinate_model.formulas["dbl-1998-hnm"] res = jac_dbl( jac_secp128r1.curve.prime, jac_secp128r1.generator, - **jac_secp128r1.curve.parameters + **jac_secp128r1.curve.parameters, ) assert res is not None @@ -111,9 +125,7 @@ def test_symbolic(secp128r1, dbl): coords, **{key: SymbolicMod(symbols(key), p) for key in coords.variables} ) symbolic_double = dbl(p, symbolic_point, **sympy_params)[0] - generator_double = dbl( - p, secp128r1.generator, **secp128r1.curve.parameters - )[0] + generator_double = dbl(p, secp128r1.generator, **secp128r1.curve.parameters)[0] for outer_var in coords.variables: symbolic_val = getattr(symbolic_double, outer_var).x generator_val = getattr(generator_double, outer_var).x @@ -126,3 +138,371 @@ def test_symbolic(secp128r1, dbl): def test_pickle(add, dbl): assert add == pickle.loads(pickle.dumps(add)) + + +def test_formula_similarity(secp128r1): + add_bl = secp128r1.curve.coordinate_model.formulas["add-2007-bl"] + add_rcb = secp128r1.curve.coordinate_model.formulas["add-2015-rcb"] + out = formula_similarity(add_bl, add_rcb) + assert out["output"] == 0 + assert out["ivs"] < 0.5 + out_abs = formula_similarity_abs(add_bl, add_rcb) + assert out_abs["output"] == 0 + assert out_abs["ivs"] < 0.5 + out_fuzz = formula_similarity_fuzz(add_bl, add_rcb, secp128r1.curve, samples=100) + assert out_fuzz["output"] == 0 + assert out_fuzz["ivs"] < 0.5 + out_same = formula_similarity(add_bl, add_bl) + assert out_same["output"] == 1 + assert out_same["ivs"] == 1 + + +LIBRARY_FORMULAS = [ + [ + "add-bc-r1rv76-jac", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp128r1"), + AdditionEFDFormula, + ], + [ + "add-bc-r1rv76-mod", + ShortWeierstrassModel, + "modified", + ("secg", "secp128r1"), + AdditionEFDFormula, + ], + [ + "dbl-bc-r1rv76-jac", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp128r1"), + DoublingEFDFormula, + ], + [ + "dbl-bc-r1rv76-mod", + ShortWeierstrassModel, + "modified", + ("secg", "secp128r1"), + DoublingEFDFormula, + ], + [ + "dbl-bc-r1rv76-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + DoublingEFDFormula, + ], + [ + "ladd-bc-r1rv76-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "dbl-boringssl-p224", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp224r1"), + DoublingEFDFormula, + ], + [ + "add-boringssl-p224", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp224r1"), + AdditionEFDFormula, + ], + [ + "add-libressl-v382", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp128r1"), + AdditionEFDFormula, + ], + [ + "dbl-libressl-v382", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp128r1"), + DoublingEFDFormula, + ], + [ + "dbl-secp256k1-v040", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp256k1"), + DoublingEFDFormula, + ], + [ + "add-openssl-z256", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "add-openssl-z256a", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "ladd-openssl-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "ladd-hacl-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "dbl-hacl-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + DoublingEFDFormula, + ], + [ + "dbl-sunec-v21", + ShortWeierstrassModel, + "projective-3", + ("secg", "secp256r1"), + DoublingEFDFormula, + ], + [ + "add-sunec-v21", + ShortWeierstrassModel, + "projective-3", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "add-sunec-v21-ed25519", + TwistedEdwardsModel, + "extended", + ("other", "Ed25519"), + AdditionEFDFormula, + ], + [ + "dbl-sunec-v21-ed25519", + TwistedEdwardsModel, + "extended", + ("other", "Ed25519"), + DoublingEFDFormula, + ], + [ + "ladd-rfc7748", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "add-bearssl-v06", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "dbl-bearssl-v06", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp256r1"), + DoublingEFDFormula, + ], + [ + "add-libgcrypt-v1102", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "dbl-libgcrypt-v1102", + ShortWeierstrassModel, + "jacobian", + ("secg", "secp256r1"), + DoublingEFDFormula, + ], + [ + "ladd-go-1214", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "add-gecc-322", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp256r1"), + AdditionEFDFormula, + ], + [ + "dbl-gecc-321", + ShortWeierstrassModel, + "jacobian-3", + ("secg", "secp256r1"), + DoublingEFDFormula, + ], + [ + "ladd-boringssl-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], + [ + "dbl-ipp-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + DoublingEFDFormula, + ], + [ + "ladd-botan-x25519", + MontgomeryModel, + "xz", + ("other", "Curve25519"), + LadderEFDFormula, + ], +] + + +@pytest.fixture(params=LIBRARY_FORMULAS, ids=list(map(itemgetter(0), LIBRARY_FORMULAS))) +def library_formula_params(request) -> Tuple[EFDFormula, DomainParameters]: + name, model, coords_name, param_spec, formula_type = request.param + model = model() + coordinate_model = model.coordinates[coords_name] + with as_file(files(test.data.formulas).joinpath(name)) as meta_path, as_file( + files(test.data.formulas).joinpath(name + ".op3") + ) as op3_path: + formula = formula_type(meta_path, op3_path, name, coordinate_model) + params = get_params(*param_spec, coords_name) + return formula, params + + +def test_formula_graph(library_formula_params): + formula, params = library_formula_params + do_test_formula(rename_ivs(formula), params) + + +def test_switch_sign(library_formula_params): + formula, params = library_formula_params + for switch_formula in generate_switched_formulas(formula): + do_test_formula(switch_formula, params) + + +def test_fliparood_formula(library_formula_params): + formula, params = library_formula_params + for fliparood in generate_fliparood_formulas(formula): + do_test_formula(fliparood, params) + + +def test_partition_formula_single(library_formula_params): + formula, params = library_formula_params + try: + next(iter(generate_partitioned_formulas(formula))) + except StopIteration: + pass + + +@pytest.mark.slow +def test_partition_formula(library_formula_params): + formula, params = library_formula_params + for partitioned in generate_partitioned_formulas(formula): + do_test_formula(partitioned, params) + + +def test_reductions(library_formula_params): + formula, params = library_formula_params + do_test_formula(reduce_all_adds(formula), params) + + +def test_expansions(library_formula_params): + formula, params = library_formula_params + do_test_formula(expand_all_muls(formula), params) + do_test_formula(expand_all_nopower2_muls(formula), params) + + +def do_test_formula(formula, params): + coordinate_model = formula.coordinate_model + scale = coordinate_model.formulas.get("z", None) + if scale is None: + scale = coordinate_model.formulas.get("scale", None) + + formula_type = formula.__class__ + for _ in range(10): + Paff = params.curve.affine_random() + P2aff = params.curve.affine_double(Paff) + Qaff = params.curve.affine_random() + Q2aff = params.curve.affine_double(Qaff) + Raff = params.curve.affine_add(Paff, Qaff) + R2aff = params.curve.affine_double(Raff) + QRaff = params.curve.affine_add(Qaff, Raff) + P = Paff.to_model(coordinate_model, params.curve) + P2 = P2aff.to_model(coordinate_model, params.curve) + Q = Qaff.to_model(coordinate_model, params.curve) + Q2 = Q2aff.to_model(coordinate_model, params.curve) + R = Raff.to_model(coordinate_model, params.curve) + R2 = R2aff.to_model(coordinate_model, params.curve) # noqa + QR = QRaff.to_model(coordinate_model, params.curve) + inputs = (P, Q, R)[: formula.num_inputs] + res = formula(params.curve.prime, *inputs, **params.curve.parameters) + if issubclass(formula_type, AdditionFormula): + try: + assert res[0].to_affine() == Raff + except NotImplementedError: + assert ( + scale(params.curve.prime, res[0], **params.curve.parameters)[0] == R + ) + elif issubclass(formula_type, DoublingFormula): + try: + assert res[0].to_affine() == P2aff + except NotImplementedError: + assert ( + scale(params.curve.prime, res[0], **params.curve.parameters)[0] + == P2 + ) + elif issubclass(formula_type, LadderFormula): + try: + assert res[0].to_affine() == Q2aff + assert res[1].to_affine() == QRaff + except NotImplementedError: + # print(scale(params.curve.prime, res[0], **params.curve.parameters)[0]) + # print(scale(params.curve.prime, res[1], **params.curve.parameters)[0]) + # print(P) + # print(Q) + # print(R) + # print(P2) + # print(Q2) + # print(R2) + # print(QR) + # print("------------------------------------") + assert ( + scale(params.curve.prime, res[1], **params.curve.parameters)[0] + == QR + ) + assert ( + scale(params.curve.prime, res[0], **params.curve.parameters)[0] + == Q2 + ) + + +def test_formula_correctness(library_formula_params): + formula, params = library_formula_params + do_test_formula(formula, params) + + +def test_formula_expand(add): + res = expand_formula_list([add]) + assert len(res) > 1 |