From cad492f2718fbdc1c2f24876add693726494f0cc Mon Sep 17 00:00:00 2001 From: J08nY Date: Fri, 29 Sep 2023 22:15:06 +0200 Subject: Add wNAF scalarmult, more options implemented for other scalarmults. --- test/test_impl.py | 140 ++++++++++++++++-------------------------------------- 1 file changed, 41 insertions(+), 99 deletions(-) (limited to 'test') diff --git a/test/test_impl.py b/test/test_impl.py index 6c58315..8197ec8 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -8,6 +8,9 @@ from pyecsca.ec.mult import ( RTLMultiplier, CoronMultiplier, BinaryNAFMultiplier, + WindowNAFMultiplier, + AccumulationOrder, + ProcessingDirection, ) from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult @@ -34,7 +37,7 @@ def do_basic_test( ] for additional in other_args: with runner.isolated_filesystem() as tmpdir: - runner.invoke( + res = runner.invoke( build_impl, [ "--platform", @@ -49,6 +52,7 @@ def do_basic_test( ".", ], ) + assert res.exit_code == 0 target = HostTarget( params.curve.model, params.curve.coordinate_model, @@ -118,29 +122,38 @@ def test_debug(cli_runner, secp128r1): ) -@pytest.mark.parametrize( - "mult_class,mult_name,formulas,mult_kwargs", - [ - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": True, "always": True}, - ), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), - (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {}), - ], -) +MULTIPLIERS = [ + (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), + (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": False, "always": True}, + ), + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": True, "always": True}, + ), + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": False, "accumulation_order": AccumulationOrder.PeqRP}, + ), + (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), + (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), + (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), + (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"direction": ProcessingDirection.LTR}), + (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"direction": ProcessingDirection.RTL}), + (WindowNAFMultiplier, "wnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"width": 3}), + (WindowNAFMultiplier, "wnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"width": 3, "precompute_negation": True}), +] + + +@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) def test_keygen(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): def callback(target, mult, params): for _ in range(10): @@ -161,35 +174,8 @@ def test_keygen(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp12 **mult_kwargs, ) - # def test_ladder(self): - # runner = CliRunner() - # self.do_keygen_test(runner, self.curve25519, LadderMultiplier, ["ladd-1987-m", "dbl-1987-m"], "ldr") - # # TODO: what about coords where generator is not affine? - - -@pytest.mark.parametrize( - "mult_class,mult_name,formulas,mult_kwargs", - [ - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": True, "always": True}, - ), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), - (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {}), - ], -) + +@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) def test_scalarmult( mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1 ): @@ -214,29 +200,7 @@ def test_scalarmult( ) -@pytest.mark.parametrize( - "mult_class,mult_name,formulas,mult_kwargs", - [ - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": True, "always": True}, - ), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), - (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {}), - ], -) +@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) def test_ecdh(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): other_privs = [15, 2355498743, 3253857901321912443757746] @@ -262,29 +226,7 @@ def test_ecdh(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r ) -@pytest.mark.parametrize( - "mult_class,mult_name,formulas,mult_kwargs", - [ - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": True, "always": True}, - ), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), - (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {}), - ], -) +@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) def test_ecdsa(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): data = b"something" -- cgit v1.3.1 From 549b6282fe9d4d06fc69d5d0b9103338d8d99363 Mon Sep 17 00:00:00 2001 From: J08nY Date: Sat, 30 Sep 2023 20:16:21 +0200 Subject: Better impl tests. --- test/test_impl.py | 425 +++++++++++++++++++++++++++--------------------------- 1 file changed, 211 insertions(+), 214 deletions(-) (limited to 'test') diff --git a/test/test_impl.py b/test/test_impl.py index 8197ec8..1082a28 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -1,8 +1,10 @@ from copy import copy from os.path import join import pytest +from click.testing import CliRunner from pyecsca.ec.key_agreement import ECDH_SHA1 +from pyecsca.ec.mod import Mod from pyecsca.ec.mult import ( LTRMultiplier, RTLMultiplier, @@ -11,250 +13,245 @@ from pyecsca.ec.mult import ( WindowNAFMultiplier, AccumulationOrder, ProcessingDirection, + ScalarMultiplier, ) from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult from pyecsca.codegen.builder import build_impl -from pyecsca.codegen.client import HostTarget +from pyecsca.codegen.client import HostTarget, ImplTarget -def do_basic_test( - callback, - runner, - params, - mult_class, - formulas, - mult_name, - ecdsa, - ecdh, - **mult_kwargs, -): - other_args = [ - ("--mul", "KARATSUBA", "--sqr", "KARATSUBA"), - ("--mul", "TOOM_COOK", "--sqr", "TOOM_COOK"), - ("--red", "BARRETT"), - ("--red", "MONTGOMERY"), - ] - for additional in other_args: - with runner.isolated_filesystem() as tmpdir: - res = runner.invoke( - build_impl, - [ - "--platform", - "HOST", - *additional, - "--ecdsa" if ecdsa else "--no-ecdsa", - "--ecdh" if ecdh else "--no-ecdh", - params.curve.model.shortname, - params.curve.coordinate_model.name, - *formulas, - f"{mult_name}({','.join(f'{key}={value}' for key, value in mult_kwargs.items())})", - ".", - ], - ) - assert res.exit_code == 0 - target = HostTarget( - params.curve.model, - params.curve.coordinate_model, - binary=join(tmpdir, "pyecsca-codegen-HOST.elf"), - ) - target.connect() - target.set_params(params) - formula_instances = [ - params.curve.coordinate_model.formulas[formula] for formula in formulas - ] - mult = mult_class(*formula_instances, **mult_kwargs) - mult.init(params, params.generator) - callback(target, mult, params) - target.disconnect() - - -def test_init(cli_runner, secp128r1): - def callback(target, mult, params): - target.init_prng(bytes([0x12, 0x34, 0x56, 0x78])) - - do_basic_test( - callback, - cli_runner, - secp128r1, - LTRMultiplier, - ["add-1998-cmo", "dbl-1998-cmo"], - "ltr", - False, - False, - ) - +@pytest.fixture( + scope="module", + params=[ + pytest.param(("--mul", "KARATSUBA", "--sqr", "KARATSUBA"), id="Karatsuba"), + pytest.param(("--mul", "TOOM_COOK", "--sqr", "TOOM_COOK"), id="ToomCook"), + pytest.param(("--red", "BARRETT"), id="Barrett"), + pytest.param(("--red", "MONTGOMERY"), id="Montgomery"), + ], +) +def additional(request): + return request.param + + +@pytest.fixture( + scope="module", + params=[ + pytest.param( + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": False}, + ), + id="LTR1", + ), + pytest.param( + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": True}, + ), + id="LTR2", + ), + pytest.param( + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": False, "always": True}, + ), + id="LTR3", + ), + pytest.param( + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": True, "always": True}, + ), + id="LTR4", + ), + pytest.param( + ( + LTRMultiplier, + "ltr", + ["add-1998-cmo", "dbl-1998-cmo"], + {"complete": False, "accumulation_order": AccumulationOrder.PeqRP}, + ), + id="LTR5", + ), + pytest.param( + (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), + id="RTL1", + ), + pytest.param( + (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), + id="RTL2", + ), + pytest.param( + (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), id="Coron" + ), + pytest.param( + ( + BinaryNAFMultiplier, + "bnaf", + ["add-1998-cmo", "dbl-1998-cmo", "neg"], + {"direction": ProcessingDirection.LTR}, + ), + id="BNAF1", + ), + pytest.param( + ( + BinaryNAFMultiplier, + "bnaf", + ["add-1998-cmo", "dbl-1998-cmo", "neg"], + {"direction": ProcessingDirection.RTL}, + ), + id="BNAF2", + ), + pytest.param( + ( + WindowNAFMultiplier, + "wnaf", + ["add-1998-cmo", "dbl-1998-cmo", "neg"], + {"width": 3}, + ), + id="WNAF1", + ), + pytest.param( + ( + WindowNAFMultiplier, + "wnaf", + ["add-1998-cmo", "dbl-1998-cmo", "neg"], + {"width": 3, "precompute_negation": True}, + ), + id="WNAF2", + ), + ], +) +def target(request, additional, secp128r1) -> ImplTarget: + mult_class, mult_name, formulas, mult_kwargs = request.param + runner = CliRunner() + with runner.isolated_filesystem() as tmpdir: + res = runner.invoke( + build_impl, + [ + "--platform", + "HOST", + *additional, + "--ecdsa", + "--ecdh", + secp128r1.curve.model.shortname, + secp128r1.curve.coordinate_model.name, + *formulas, + f"{mult_name}({','.join(f'{key}={value}' for key, value in mult_kwargs.items())})", + ".", + ], + ) + assert res.exit_code == 0 + target = HostTarget( + secp128r1.curve.model, + secp128r1.curve.coordinate_model, + binary=join(tmpdir, "pyecsca-codegen-HOST.elf"), + ) + formula_instances = [ + secp128r1.curve.coordinate_model.formulas[formula] for formula in formulas + ] + mult = mult_class(*formula_instances, **mult_kwargs) + target.mult = mult + yield target -def test_setup(cli_runner, secp128r1): - def callback(target, mult, params): - priv = 57 - pub = mult.multiply(priv).to_affine() - target.set_privkey(priv) - target.set_pubkey(pub) - do_basic_test( - callback, - cli_runner, - secp128r1, - LTRMultiplier, - ["add-1998-cmo", "dbl-1998-cmo"], - "ltr", - False, - False, - ) +@pytest.fixture(scope="module") +def mult(target) -> ScalarMultiplier: + return target.mult # noqa -def test_debug(cli_runner, secp128r1): - def callback(target, mult, params): - model, coords = target.debug() - assert model == params.curve.model.shortname - assert coords == params.curve.coordinate_model.name +def test_init(target): + target.connect() + target.init_prng(bytes([0x12, 0x34, 0x56, 0x78])) + target.disconnect() - do_basic_test( - callback, - cli_runner, - secp128r1, - LTRMultiplier, - ["add-1998-cmo", "dbl-1998-cmo"], - "ltr", - False, - False, - ) +def test_setup(target, mult, secp128r1): + priv = 57 + mult.init(secp128r1, secp128r1.generator) + pub = mult.multiply(priv).to_affine() + target.connect() + target.set_privkey(priv) + target.set_pubkey(pub) + target.disconnect() -MULTIPLIERS = [ - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": False}), - (LTRMultiplier, "ltr", ["add-1998-cmo", "dbl-1998-cmo"], {"complete": True}), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": True, "always": True}, - ), - ( - LTRMultiplier, - "ltr", - ["add-1998-cmo", "dbl-1998-cmo"], - {"complete": False, "accumulation_order": AccumulationOrder.PeqRP}, - ), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": False}), - (RTLMultiplier, "rtl", ["add-1998-cmo", "dbl-1998-cmo"], {"always": True}), - (CoronMultiplier, "coron", ["add-1998-cmo", "dbl-1998-cmo"], {}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"direction": ProcessingDirection.LTR}), - (BinaryNAFMultiplier, "bnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"direction": ProcessingDirection.RTL}), - (WindowNAFMultiplier, "wnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"width": 3}), - (WindowNAFMultiplier, "wnaf", ["add-1998-cmo", "dbl-1998-cmo", "neg"], {"width": 3, "precompute_negation": True}), -] +def test_debug(target, secp128r1): + target.connect() + model, coords = target.debug() + assert model == secp128r1.curve.model.shortname + assert coords == secp128r1.curve.coordinate_model.name + target.disconnect() -@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) -def test_keygen(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): - def callback(target, mult, params): - for _ in range(10): - priv, pub = target.generate() - assert params.curve.is_on_curve(pub) - expected = mult.multiply(priv).to_affine() - assert pub == expected - do_basic_test( - callback, - cli_runner, - secp128r1, - mult_class, - formulas, - mult_name, - False, - False, - **mult_kwargs, - ) +def test_keygen(target, mult, secp128r1): + target.connect() + target.set_params(secp128r1) + mult.init(secp128r1, secp128r1.generator) + for _ in range(10): + priv, pub = target.generate() + assert secp128r1.curve.is_on_curve(pub) + expected = mult.multiply(priv).to_affine() + assert pub == expected + target.disconnect() -@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) -def test_scalarmult( - mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1 -): +def test_scalarmult(target, mult, secp128r1): + target.connect() + target.set_params(secp128r1) + mult.init(secp128r1, secp128r1.generator) values = [15, 2355498743, 3253857901321912443757746] + for value in values: + result = target.scalar_mult(value, target.params.generator) + expected = mult.multiply(value) + assert result == expected + target.disconnect() - def callback(target, mult, params): - for value in values: - result = target.scalar_mult(value, params.generator) - expected = mult.multiply(value) - assert result == expected - - do_basic_test( - callback, - cli_runner, - secp128r1, - mult_class, - formulas, - mult_name, - False, - False, - **mult_kwargs, - ) - -@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) -def test_ecdh(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): +def test_ecdh(target, mult, secp128r1): + target.connect() + target.set_params(secp128r1) + mult.init(secp128r1, secp128r1.generator) other_privs = [15, 2355498743, 3253857901321912443757746] - - def callback(target, mult, params): - for other_priv in other_privs: - priv, pub = target.generate() - other_pub = mult.multiply(other_priv) - ecdh = ECDH_SHA1(copy(mult), params, other_pub, priv) - result = target.ecdh(other_pub) - expected = ecdh.perform() - assert result == expected - - do_basic_test( - callback, - cli_runner, - secp128r1, - mult_class, - formulas, - mult_name, - False, - True, - **mult_kwargs, - ) + for other_priv in other_privs: + priv, pub = target.generate() + other_pub = mult.multiply(other_priv) + ecdh = ECDH_SHA1(copy(mult), secp128r1, other_pub, Mod(priv, secp128r1.order)) + result = target.ecdh(other_pub) + expected = ecdh.perform() + assert result == expected + target.disconnect() -@pytest.mark.parametrize("mult_class,mult_name,formulas,mult_kwargs", MULTIPLIERS) -def test_ecdsa(mult_class, mult_name, mult_kwargs, formulas, cli_runner, secp128r1): - data = b"something" +def test_ecdsa(target, mult, secp128r1): + target.connect() + target.set_params(secp128r1) + mult.init(secp128r1, secp128r1.generator) - def callback(target, mult, params): + messages = [b"something", b"something quite a bit longer than the hash thing"] + for message in messages: priv, pub = target.generate() ecdsa = ECDSA_SHA1( copy(mult), - params, + secp128r1, mult.formulas["add"], - pub.to_model(params.curve.coordinate_model, params.curve), - priv, + pub.to_model(secp128r1.curve.coordinate_model, secp128r1.curve), + Mod(priv, secp128r1.order), ) - signature_data = target.ecdsa_sign(data) + signature_data = target.ecdsa_sign(message) result = SignatureResult.from_DER(signature_data) - assert ecdsa.verify_data(result, data) - - expected = ecdsa.sign_data(data).to_DER() - assert target.ecdsa_verify(data, expected) + assert ecdsa.verify_data(result, message) - do_basic_test( - callback, - cli_runner, - secp128r1, - mult_class, - formulas, - mult_name, - True, - False, - **mult_kwargs, - ) + expected = ecdsa.sign_data(message).to_DER() + assert target.ecdsa_verify(message, expected) + target.disconnect() \ No newline at end of file -- cgit v1.3.1 From 5e83141740737d832bb19c79ff9ea371977fdbe0 Mon Sep 17 00:00:00 2001 From: J08nY Date: Sun, 1 Oct 2023 22:22:38 +0200 Subject: Add sliding window recoding functions. --- pyecsca/codegen/bn/bn.c | 134 ++++++++++++++++++++++++++++++++++++++++++++++++ pyecsca/codegen/bn/bn.h | 10 ++++ test/Makefile | 3 ++ test/test_bn.c | 56 ++++++++++++++++++++ 4 files changed, 203 insertions(+) create mode 100644 test/Makefile create mode 100644 test/test_bn.c (limited to 'test') diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c index 53777db..77df5ab 100644 --- a/pyecsca/codegen/bn/bn.c +++ b/pyecsca/codegen/bn/bn.c @@ -71,6 +71,10 @@ size_t bn_to_bin_size(const bn_t *one) { return mp_ubin_size(one); } +unsigned int bn_to_int(const bn_t *one) { + return mp_get_mag_ul(one); +} + bn_err bn_rand_mod_sample(bn_t *out, const bn_t *mod) { int mod_len = bn_bit_length(mod); @@ -448,4 +452,134 @@ exit_full_width: wnaf_t *bn_bnaf(const bn_t *bn) { return bn_wnaf(bn, 2); +} + +wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w) { + if (w > 8 || w < 2) { + return NULL; + } + + wsliding_t *result = NULL; + + int blen = bn_bit_length(bn); + uint8_t arr[blen]; + + int b = blen - 1; + int u = 0; + int c = 0; + bn_t mask; + if (mp_init(&mask) != BN_OKAY) { + goto exit_mask; + } + + int i = 0; + while (b >= 0) { + if (!bn_get_bit(bn, b)) { + arr[i++] = 0; // result.append(0) + b--; // b -= 1 + } else { + u = 0; // u = 0 + for (int v = 1; v <= w; v++) { // for v in range(1, w + 1): + if (b + 1 < v) { // if b + 1 < v: + break; + } + bn_from_int((1 << v) - 1, &mask); // mask = ((2**v) - 1) << (b - v + 1) + bn_lsh(&mask, b - v + 1, &mask); + mp_and(&mask, bn, &mask); // mask = (i & mask) + bn_rsh(&mask, b - v + 1, &mask); // mask = mask >> (b - v + 1) + if (bn_get_bit(&mask, 0)) { // if c & 1: + u = (int) bn_to_int(&mask); // u = c + } + } + c = u; + while (u) { // k = u.bit_length() + arr[i++] = 0; // result.extend([0] * (k - 1)) + b--; // b -= k + u >>= 1; + } + arr[i - 1] = c; // result.append(u) + } + } + bn_clear(&mask); + + result = malloc(sizeof(wsliding_t)); + result->w = w; + result->length = 0; + result->data = NULL; + // Strip the repr and return. + for (int j = 0; j < i; j++) { + if (result->data == NULL) { + if (arr[j]) { + result->length = i - j; + result->data = calloc(result->length, sizeof(uint8_t)); + result->data[0] = arr[j]; + } + } else { + result->data[j - (i - result->length)] = arr[j]; + } + } +exit_mask: + return result; +} + +wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) { + if (w > 8 || w < 2) { + return NULL; + } + + wsliding_t *result = NULL; + + int blen = bn_bit_length(bn); + uint8_t arr[blen]; + + bn_t k; + if (mp_init(&k) != BN_OKAY) { + goto exit_k; + } + bn_copy(bn, &k); + + bn_t mask; + if (mp_init(&mask) != BN_OKAY) { + goto exit_mask; + } + + int u = 0; + int i = 0; + while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) { + if (!bn_get_bit(&k, 0)) { + arr[i++] = 0; + bn_rsh(&k, 1, &k); + } else { + bn_from_int((1 << w) - 1, &mask); // mask = ((2**w) - 1) + mp_and(&mask, &k, &mask); + arr[i++] = bn_to_int(&mask); + for (int j = 0; j < w - 1; j++) { + arr[i++] = 0; + } + bn_rsh(&k, w, &k); + } + } + bn_clear(&mask); + + result = malloc(sizeof(wsliding_t)); + result->w = w; + result->length = 0; + result->data = NULL; + // Revert, strip the repr and return. + for (int j = i - 1; j >= 0; j--) { + if (result->data == NULL) { + if (arr[j]) { + result->length = j + 1; + result->data = calloc(result->length, sizeof(uint8_t)); + result->data[0] = arr[j]; + } + } else { + result->data[result->length - j - 1] = arr[j]; + } + } + +exit_mask: + bn_clear(&k); +exit_k: + return result; } \ No newline at end of file diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h index ed29970..0732fb1 100644 --- a/pyecsca/codegen/bn/bn.h +++ b/pyecsca/codegen/bn/bn.h @@ -58,6 +58,12 @@ typedef struct { int w; } wnaf_t; +typedef struct { + uint8_t *data; + size_t length; + int w; +} wsliding_t; + void math_init(void); bn_err bn_init(bn_t *bn); @@ -73,6 +79,7 @@ bn_err bn_from_int(unsigned int value, bn_t *out); bn_err bn_to_binpad(const bn_t *one, uint8_t *data, size_t size); bn_err bn_to_bin(const bn_t *one, uint8_t *data); size_t bn_to_bin_size(const bn_t *one); +unsigned int bn_to_int(const bn_t *one); bn_err bn_rand_mod_sample(bn_t *out, const bn_t *mod); bn_err bn_rand_mod_reduce(bn_t *out, const bn_t *mod); @@ -115,4 +122,7 @@ int bn_bit_length(const bn_t *bn); wnaf_t *bn_wnaf(const bn_t *bn, int w); wnaf_t *bn_bnaf(const bn_t *bn); +wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w); +wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w); + #endif //BN_H_ \ No newline at end of file diff --git a/test/Makefile b/test/Makefile new file mode 100644 index 0000000..4b8fc78 --- /dev/null +++ b/test/Makefile @@ -0,0 +1,3 @@ + +test_bn: test_bn.c ../pyecsca/codegen/bn/bn.c + gcc -o $@ $^ -I ../pyecsca/codegen/ -I ../pyecsca/codegen/tommath/ -L ../pyecsca/codegen/tommath/ -l:libtommath-HOST.a \ No newline at end of file diff --git a/test/test_bn.c b/test/test_bn.c new file mode 100644 index 0000000..a77fe9a --- /dev/null +++ b/test/test_bn.c @@ -0,0 +1,56 @@ +#include +#include "bn/bn.h" + +int test_wsliding_ltr() { + printf("test_wsliding_ltr: "); + bn_t bn; + bn_init(&bn); + bn_from_int(181, &bn); + wsliding_t *ws = bn_wsliding_ltr(&bn, 3); + if (ws == NULL) { + printf("NULL\n"); + return 1; + } + if (ws->length != 6) { + printf("Bad length (%li instead of 6)\n", ws->length); + return 1; + } + uint8_t expected[6] = {5, 0, 0, 5, 0, 1}; + for (int i = 0; i < 6; i++) { + if (ws->data[i] != expected[i]) { + printf("Bad data (%i instead of %i)\n", ws->data[i], expected[i]); + return 1; + } + } + printf("OK\n"); + return 0; +} + +int test_wsliding_rtl() { + printf("test_wsliding_rtl: "); + bn_t bn; + bn_init(&bn); + bn_from_int(181, &bn); + wsliding_t *ws = bn_wsliding_rtl(&bn, 3); + if (ws == NULL) { + printf("NULL\n"); + return 1; + } + if (ws->length != 8) { + printf("Bad length (%li instead of 8)\n", ws->length); + return 1; + } + uint8_t expected[8] = {1, 0, 0, 3, 0, 0, 0, 5}; + for (int i = 0; i < 8; i++) { + if (ws->data[i] != expected[i]) { + printf("Bad data (%i instead of %i)\n", ws->data[i], expected[i]); + return 1; + } + } + printf("OK\n"); + return 0; +} + +int main(void) { + return test_wsliding_ltr() + test_wsliding_rtl(); +} \ No newline at end of file -- cgit v1.3.1 From 7889941ce0c198113509738c1f0e84bb7826080f Mon Sep 17 00:00:00 2001 From: J08nY Date: Sun, 1 Oct 2023 22:55:17 +0200 Subject: Add Sliding window multiplier. --- pyecsca/codegen/bn/bn.c | 1 - pyecsca/codegen/common.py | 18 ++++++++++--- pyecsca/codegen/templates/mult_sliding_w.c | 42 ++++++++++++++++++++++++++++++ test/test_impl.py | 21 ++++++++++++++- 4 files changed, 77 insertions(+), 5 deletions(-) create mode 100644 pyecsca/codegen/templates/mult_sliding_w.c (limited to 'test') diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c index 77df5ab..e0c4bcb 100644 --- a/pyecsca/codegen/bn/bn.c +++ b/pyecsca/codegen/bn/bn.c @@ -543,7 +543,6 @@ wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) { goto exit_mask; } - int u = 0; int i = 0; while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) { if (!bn_get_bit(&k, 0)) { diff --git a/pyecsca/codegen/common.py b/pyecsca/codegen/common.py index 56ca261..2f3dfbd 100644 --- a/pyecsca/codegen/common.py +++ b/pyecsca/codegen/common.py @@ -7,9 +7,17 @@ from pyecsca.ec.configuration import EnumDefine, Configuration from pyecsca.ec.coordinates import CoordinateModel from pyecsca.ec.model import (CurveModel, ShortWeierstrassModel, MontgomeryModel, EdwardsModel, TwistedEdwardsModel) -from pyecsca.ec.mult import (LTRMultiplier, RTLMultiplier, CoronMultiplier, - LadderMultiplier, SimpleLadderMultiplier, DifferentialLadderMultiplier, - WindowNAFMultiplier, BinaryNAFMultiplier) +from pyecsca.ec.mult import ( + LTRMultiplier, + RTLMultiplier, + CoronMultiplier, + LadderMultiplier, + SimpleLadderMultiplier, + DifferentialLadderMultiplier, + WindowNAFMultiplier, + BinaryNAFMultiplier, + SlidingWindowMultiplier, +) @public @@ -65,6 +73,10 @@ MULTIPLIERS = [ { "name": ("wnaf", "WindowNAFMultiplier"), "class": WindowNAFMultiplier + }, + { + "name": ("sliding", "SlidingWindowMultiplier"), + "class": SlidingWindowMultiplier } ] diff --git a/pyecsca/codegen/templates/mult_sliding_w.c b/pyecsca/codegen/templates/mult_sliding_w.c new file mode 100644 index 0000000..87135cc --- /dev/null +++ b/pyecsca/codegen/templates/mult_sliding_w.c @@ -0,0 +1,42 @@ +#include "mult.h" +#include "point.h" + +static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) { + point_t *q = point_copy(curve->neutral); + point_t *points[{{ 2 ** (scalarmult.width - 1) }}]; + + point_t *current = point_copy(point); + point_t *dbl = point_new(); + point_dbl(current, curve, dbl); + for (long i = 0; i < {{ 2 ** (scalarmult.width - 1) }}; i++) { + points[i] = point_copy(current); + point_add(current, dbl, curve, current); + } + point_free(current); + point_free(dbl); + + {% if scalarmult.recoding_direction == ProcessingDirection.LTR %} + wsliding_t *ws = bn_wsliding_ltr(scalar, {{ scalarmult.width }}); + {% elif scalarmult.recoding_direction == ProcessingDirection.RTL %} + wsliding_t *ws = bn_wsliding_rtl(scalar, {{ scalarmult.width }}); + {% endif %} + + for (long i = 0; i < ws->length; i++) { + point_dbl(q, curve, q); + uint8_t val = ws->data[i]; + if (val) { + point_accumulate(q, points[(val - 1) / 2], curve, q); + } + } + free(ws->data); + free(ws); + + {%- if "scl" in scalarmult.formulas %} + point_scl(q, curve, q); + {%- endif %} + point_set(q, out); + for (long i = 0; i < {{ 2 ** (scalarmult.width - 1) }}; i++) { + point_free(points[i]); + } + point_free(q); +} \ No newline at end of file diff --git a/test/test_impl.py b/test/test_impl.py index 1082a28..147792e 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -11,6 +11,7 @@ from pyecsca.ec.mult import ( CoronMultiplier, BinaryNAFMultiplier, WindowNAFMultiplier, + SlidingWindowMultiplier, AccumulationOrder, ProcessingDirection, ScalarMultiplier, @@ -129,6 +130,24 @@ def additional(request): ), id="WNAF2", ), + pytest.param( + ( + SlidingWindowMultiplier, + "sliding", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 3}, + ), + id="SLI1", + ), + pytest.param( + ( + SlidingWindowMultiplier, + "sliding", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 3, "recoding_direction": ProcessingDirection.RTL}, + ), + id="SLI2", + ), ], ) def target(request, additional, secp128r1) -> ImplTarget: @@ -254,4 +273,4 @@ def test_ecdsa(target, mult, secp128r1): expected = ecdsa.sign_data(message).to_DER() assert target.ecdsa_verify(message, expected) - target.disconnect() \ No newline at end of file + target.disconnect() -- cgit v1.3.1 From 07026a90ba04e164fadeb40dc2ba80e7743abf00 Mon Sep 17 00:00:00 2001 From: J08nY Date: Tue, 3 Oct 2023 23:29:18 +0200 Subject: Add fixed width scalarmult. --- pyecsca/codegen/bn/bn.c | 46 +++++++++++++++++++++-- pyecsca/codegen/bn/bn.h | 9 +++++ pyecsca/codegen/common.py | 5 +++ pyecsca/codegen/render.py | 3 +- pyecsca/codegen/templates/mult_fixed_w.c | 63 ++++++++++++++++++++++++++++++++ pyecsca/codegen/templates/point.c | 4 +- test/test_bn.c | 39 +++++++++++++++++++- test/test_impl.py | 19 ++++++++++ 8 files changed, 179 insertions(+), 9 deletions(-) create mode 100644 pyecsca/codegen/templates/mult_fixed_w.c (limited to 'test') diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c index e0c4bcb..13d7134 100644 --- a/pyecsca/codegen/bn/bn.c +++ b/pyecsca/codegen/bn/bn.c @@ -53,7 +53,7 @@ bn_err bn_from_int(unsigned int value, bn_t *out) { } else { mp_set_u32(out, value); } - return MP_OKAY; + return BN_OKAY; } bn_err bn_to_binpad(const bn_t *one, uint8_t *data, size_t size) { @@ -350,6 +350,10 @@ bn_err bn_rsh(const bn_t *one, int amount, bn_t *out) { return mp_div_2d(one, amount, out, NULL); } +bn_err bn_and(const bn_t *one, const bn_t *other, bn_t *out) { + return mp_and(one, other, out); +} + bool bn_eq(const bn_t *one, const bn_t *other) { return mp_cmp_mag(one, other) == MP_EQ; } @@ -485,7 +489,7 @@ wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w) { } bn_from_int((1 << v) - 1, &mask); // mask = ((2**v) - 1) << (b - v + 1) bn_lsh(&mask, b - v + 1, &mask); - mp_and(&mask, bn, &mask); // mask = (i & mask) + bn_and(&mask, bn, &mask); // mask = (i & mask) bn_rsh(&mask, b - v + 1, &mask); // mask = mask >> (b - v + 1) if (bn_get_bit(&mask, 0)) { // if c & 1: u = (int) bn_to_int(&mask); // u = c @@ -550,7 +554,7 @@ wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) { bn_rsh(&k, 1, &k); } else { bn_from_int((1 << w) - 1, &mask); // mask = ((2**w) - 1) - mp_and(&mask, &k, &mask); + bn_and(&mask, &k, &mask); arr[i++] = bn_to_int(&mask); for (int j = 0; j < w - 1; j++) { arr[i++] = 0; @@ -581,4 +585,40 @@ exit_mask: bn_clear(&k); exit_k: return result; +} + +base_t *bn_convert_base(const bn_t *bn, int m) { + base_t *result = NULL; + + bn_t k; + if (mp_init(&k) != BN_OKAY) { + goto exit_k; + } + bn_copy(bn, &k); + + int len = 0; + if (mp_log_n(&k, m, &len) != BN_OKAY) { + goto exit_len; + } + + result = malloc(sizeof(base_t)); + result->length = len + 1; + result->data = calloc(result->length, sizeof(uint8_t)); + result->m = m; + + int i = 0; + mp_digit val = 0; + while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) { + if (mp_div_d(&k, m, &k, &val) != BN_OKAY) { + free(result->data); + free(result); + goto exit_len; + } + result->data[i++] = (uint8_t) val; + } + +exit_len: + bn_clear(&k); +exit_k: + return result; } \ No newline at end of file diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h index 0732fb1..d5d1e0c 100644 --- a/pyecsca/codegen/bn/bn.h +++ b/pyecsca/codegen/bn/bn.h @@ -64,6 +64,12 @@ typedef struct { int w; } wsliding_t; +typedef struct { + uint8_t *data; + size_t length; + int m; +} base_t; + void math_init(void); bn_err bn_init(bn_t *bn); @@ -111,6 +117,7 @@ void bn_red_clear(red_t *out); bn_err bn_lsh(const bn_t *one, int amount, bn_t *out); bn_err bn_rsh(const bn_t *one, int amount, bn_t *out); +bn_err bn_and(const bn_t *one, const bn_t *other, bn_t *out); bool bn_eq(const bn_t *one, const bn_t *other); bool bn_is_0(const bn_t *one); @@ -125,4 +132,6 @@ wnaf_t *bn_bnaf(const bn_t *bn); wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w); wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w); +base_t *bn_convert_base(const bn_t *bn, int m); + #endif //BN_H_ \ No newline at end of file diff --git a/pyecsca/codegen/common.py b/pyecsca/codegen/common.py index 2f3dfbd..b970039 100644 --- a/pyecsca/codegen/common.py +++ b/pyecsca/codegen/common.py @@ -17,6 +17,7 @@ from pyecsca.ec.mult import ( WindowNAFMultiplier, BinaryNAFMultiplier, SlidingWindowMultiplier, + FixedWindowLTRMultiplier, ) @@ -77,6 +78,10 @@ MULTIPLIERS = [ { "name": ("sliding", "SlidingWindowMultiplier"), "class": SlidingWindowMultiplier + }, + { + "name": ("fixed", "FixedWindowLTRMultiplier"), + "class": FixedWindowLTRMultiplier } ] diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py index 0358472..ba06a72 100644 --- a/pyecsca/codegen/render.py +++ b/pyecsca/codegen/render.py @@ -37,6 +37,7 @@ env = Environment( ) env.globals["isinstance"] = isinstance +env.globals["bin"] = bin env.globals["AccumulationOrder"] = AccumulationOrder env.globals["ProcessingDirection"] = ProcessingDirection @@ -181,8 +182,6 @@ def render_coords_impl(coords: CoordinateModel, accumulation_order: Optional[Acc frees = namespace["frees"] namespace["frees"] = {} - accumulation_order = getattr(accumulation_order, "name", None) - return env.get_template("point.c").render(variables=coords.variables, **namespace, to_affine_rets=returns, to_affine_frees=frees, accumulation_order=accumulation_order) diff --git a/pyecsca/codegen/templates/mult_fixed_w.c b/pyecsca/codegen/templates/mult_fixed_w.c new file mode 100644 index 0000000..aa95ebd --- /dev/null +++ b/pyecsca/codegen/templates/mult_fixed_w.c @@ -0,0 +1,63 @@ +#include "mult.h" +#include "point.h" + +void scalar_mult_by_m_pow2(point_t *point, curve_t *curve) { + unsigned int m = {{ scalarmult.m }} >> 1; + while (m) { + point_dbl(point, curve, point); + m >>= 1; + } +} + +void scalar_mult_by_m_base(point_t *point, curve_t *curve) { + point_t *orig = point_copy(point); + point_dbl(orig, curve, point); + for (int i = 0; i < {{ scalarmult.m - 2}}; i++) { + point_add(point, orig, curve, point); + } + point_free(orig); +} + +static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) { + point_t *q = point_copy(curve->neutral); + point_t *points[{{ scalarmult.m }}]; + + point_t *current = point_copy(point); + point_t *dbl = point_new(); + point_dbl(current, curve, dbl); + points[0] = point_copy(current); + points[1] = point_copy(dbl); + point_set(dbl, current); + for (long i = 2; i < {{ scalarmult.m }}; i++) { + point_add(current, point, curve, current); + points[i] = point_copy(current); + } + point_free(current); + point_free(dbl); + + base_t *bs = bn_convert_base(scalar, {{ scalarmult.m }}); + + for (long i = bs->length - 1; i >= 0; i--) { + {%- if bin(scalarmult.m).count("1") == 1 %} + scalar_mult_by_m_pow2(q, curve); + {%- else %} + scalar_mult_by_m_base(q, curve); + {%- endif %} + + uint8_t val = bs->data[i]; + if (val) { + point_accumulate(q, points[val-1], curve, q); + } + } + free(bs->data); + free(bs); + + {%- if "scl" in scalarmult.formulas %} + point_scl(q, curve, q); + {%- endif %} + point_set(q, out); + for (long i = 0; i < {{ scalarmult.m }}; i++) { + point_free(points[i]); + } + point_free(q); +} \ No newline at end of file diff --git a/pyecsca/codegen/templates/point.c b/pyecsca/codegen/templates/point.c index b4d6e94..bad232a 100644 --- a/pyecsca/codegen/templates/point.c +++ b/pyecsca/codegen/templates/point.c @@ -139,9 +139,9 @@ void point_from_affine(bn_t *x, bn_t *y, const curve_t *curve, point_t *out) { } void point_accumulate(const point_t *one, const point_t *other, const curve_t *curve, point_t *out_one) { - {% if accumulation_order == "PeqPR" %} + {% if accumulation_order == AccumulationOrder.PeqPR %} point_add(one, other, curve, out_one); - {% elif accumulation_order == "PeqRP" %} + {% elif accumulation_order == AccumulationOrder.PeqRP %} point_add(other, one, curve, out_one); {% endif %} } \ No newline at end of file diff --git a/test/test_bn.c b/test/test_bn.c index a77fe9a..9e3fd6f 100644 --- a/test/test_bn.c +++ b/test/test_bn.c @@ -1,4 +1,5 @@ #include +#include #include "bn/bn.h" int test_wsliding_ltr() { @@ -23,6 +24,9 @@ int test_wsliding_ltr() { } } printf("OK\n"); + bn_clear(&bn); + free(ws->data); + free(ws); return 0; } @@ -48,9 +52,40 @@ int test_wsliding_rtl() { } } printf("OK\n"); + bn_clear(&bn); + free(ws->data); + free(ws); + return 0; +} + +int test_convert_base() { + printf("test_convert-base: "); + bn_t bn; + bn_init(&bn); + bn_from_int(5, &bn); + base_t *bs = bn_convert_base(&bn, 2); + if (bs == NULL) { + printf("NULL\n"); + return 1; + } + if (bs->length != 3) { + printf("Bad length (%li instead of 3)\n", bs->length); + return 1; + } + uint8_t expected[3] = {1, 0, 1}; + for (int i = 0; i < 3; i++) { + if (bs->data[i] != expected[i]) { + printf("Bad data (%i insead of %i)\n", bs->data[i], expected[i]); + return 1; + } + } + printf("OK\n"); + bn_clear(&bn); + free(bs->data); + free(bs); return 0; } int main(void) { - return test_wsliding_ltr() + test_wsliding_rtl(); -} \ No newline at end of file + return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base(); +} diff --git a/test/test_impl.py b/test/test_impl.py index 147792e..c125ce6 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -15,6 +15,7 @@ from pyecsca.ec.mult import ( AccumulationOrder, ProcessingDirection, ScalarMultiplier, + FixedWindowLTRMultiplier, ) from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult @@ -148,6 +149,24 @@ def additional(request): ), id="SLI2", ), + pytest.param( + ( + FixedWindowLTRMultiplier, + "fixed", + ["add-1998-cmo", "dbl-1998-cmo"], + {"m": 4}, + ), + id="FIX1", + ), + pytest.param( + ( + FixedWindowLTRMultiplier, + "fixed", + ["add-1998-cmo", "dbl-1998-cmo"], + {"m": 5}, + ), + id="FIX2", + ), ], ) def target(request, additional, secp128r1) -> ImplTarget: -- cgit v1.3.1 From 01f049138e1cfa8df1600f271299db8322957615 Mon Sep 17 00:00:00 2001 From: J08nY Date: Thu, 5 Oct 2023 13:59:04 +0200 Subject: Enable faster implementation in simulator tests. --- .gitignore | 1 + test/test_simulator.py | 8 +++++++- 2 files changed, 8 insertions(+), 1 deletion(-) (limited to 'test') diff --git a/.gitignore b/.gitignore index 58caf65..9e55abb 100644 --- a/.gitignore +++ b/.gitignore @@ -4,6 +4,7 @@ htmlcov/ /build/ __pycache__ +/test/test_bn pyecsca-codegen-*.elf pyecsca-codegen-*.hex \ No newline at end of file diff --git a/test/test_simulator.py b/test/test_simulator.py index e5a1c9d..104d57c 100644 --- a/test/test_simulator.py +++ b/test/test_simulator.py @@ -5,6 +5,7 @@ import pytest from pyecsca.ec.key_agreement import ECDH_SHA1 from pyecsca.ec.mult import LTRMultiplier, RTLMultiplier from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult +from rainbow import TraceConfig, HammingWeight from pyecsca.codegen.builder import build_impl from pyecsca.codegen.client import SimulatorTarget @@ -46,6 +47,10 @@ def do_basic_test( "STM32F3", "--ecdsa" if ecdsa else "--no-ecdsa", "--ecdh" if ecdh else "--no-ecdh", + "--red", + "MONTGOMERY", + "-D", + "BN_NON_CONST", params.curve.model.shortname, params.curve.coordinate_model.name, *formulas, @@ -53,7 +58,7 @@ def do_basic_test( ".", ], ) - target = SimulatorTarget(params.curve.model, params.curve.coordinate_model) + target = SimulatorTarget(params.curve.model, params.curve.coordinate_model, trace_config=TraceConfig(register=HammingWeight())) target.connect(binary=join(tmpdir, "pyecsca-codegen-CW308_STM32F3.elf")) target.set_params(params) formula_instances = [ @@ -126,6 +131,7 @@ def test_debug(cli_runner, curve32): def test_keygen(mult_name, mult_class, cli_runner, curve32): def callback(target, mult, params): priv, pub = target.generate() + print(len(target.trace)) assert params.curve.is_on_curve(pub) expected = mult.multiply(priv).to_affine() assert pub == expected -- cgit v1.3.1 From 30ad1d48422655001c64a6982f7f97208b802df3 Mon Sep 17 00:00:00 2001 From: J08nY Date: Thu, 5 Oct 2023 14:13:25 +0200 Subject: Dont trace in simulator tests. --- test/test_simulator.py | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'test') diff --git a/test/test_simulator.py b/test/test_simulator.py index 104d57c..8ce38e4 100644 --- a/test/test_simulator.py +++ b/test/test_simulator.py @@ -58,7 +58,7 @@ def do_basic_test( ".", ], ) - target = SimulatorTarget(params.curve.model, params.curve.coordinate_model, trace_config=TraceConfig(register=HammingWeight())) + target = SimulatorTarget(params.curve.model, params.curve.coordinate_model) target.connect(binary=join(tmpdir, "pyecsca-codegen-CW308_STM32F3.elf")) target.set_params(params) formula_instances = [ @@ -131,7 +131,6 @@ def test_debug(cli_runner, curve32): def test_keygen(mult_name, mult_class, cli_runner, curve32): def callback(target, mult, params): priv, pub = target.generate() - print(len(target.trace)) assert params.curve.is_on_curve(pub) expected = mult.multiply(priv).to_affine() assert pub == expected -- cgit v1.3.1 From 491c652b93056479edefea29c1a62af48aa7ba22 Mon Sep 17 00:00:00 2001 From: J08nY Date: Thu, 5 Oct 2023 15:55:34 +0200 Subject: Xfail simulator tests until #3 is resolved. --- test/test_simulator.py | 1 + 1 file changed, 1 insertion(+) (limited to 'test') diff --git a/test/test_simulator.py b/test/test_simulator.py index 8ce38e4..89819b1 100644 --- a/test/test_simulator.py +++ b/test/test_simulator.py @@ -198,6 +198,7 @@ def test_ecdh(mult_name, mult_class, cli_runner, curve32): ) +@pytest.mark.xfail(reason="Simulator bug #3") @pytest.mark.parametrize( "mult_name,mult_class", [("ltr", LTRMultiplier), ("rtl", RTLMultiplier)] ) -- cgit v1.3.1 From 71579306e7c63123426e5bda105e3ab850fbbb20 Mon Sep 17 00:00:00 2001 From: J08nY Date: Fri, 6 Oct 2023 15:26:06 +0200 Subject: Test under -fsanitize and fix Keccak issue. --- pyecsca/codegen/prng/KeccakP-200-compact.c | 4 +++- test/test_impl.py | 3 +++ 2 files changed, 6 insertions(+), 1 deletion(-) (limited to 'test') diff --git a/pyecsca/codegen/prng/KeccakP-200-compact.c b/pyecsca/codegen/prng/KeccakP-200-compact.c index 42c972b..f07bae9 100644 --- a/pyecsca/codegen/prng/KeccakP-200-compact.c +++ b/pyecsca/codegen/prng/KeccakP-200-compact.c @@ -169,7 +169,9 @@ void KeccakP200_Permute_18rounds(void *argState) void KeccakP200_ExtractBytes(const void *state, unsigned char *data, unsigned int offset, unsigned int length) { - memcpy(data, (UINT8*)state+offset, length); + if (length) { + memcpy(data, (UINT8*)state+offset, length); + } } /* ---------------------------------------------------------------- */ diff --git a/test/test_impl.py b/test/test_impl.py index c125ce6..cb5b583 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -187,6 +187,9 @@ def target(request, additional, secp128r1) -> ImplTarget: f"{mult_name}({','.join(f'{key}={value}' for key, value in mult_kwargs.items())})", ".", ], + env={ + "CFLAGS": "-fsanitize=address -fsanitize=undefined -fno-sanitize-recover=all" + } ) assert res.exit_code == 0 target = HostTarget( -- cgit v1.3.1 From 1c2e383d8e8df323b4cebb302869fc15599961a0 Mon Sep 17 00:00:00 2001 From: J08nY Date: Sun, 8 Oct 2023 20:57:24 +0200 Subject: Add fixed-base multipliers with precomputation. --- pyecsca/codegen/bn/bn.c | 48 +++++++++++++++-- pyecsca/codegen/bn/bn.h | 14 +++-- pyecsca/codegen/builder.py | 30 ++++++----- pyecsca/codegen/common.py | 56 ++++++-------------- pyecsca/codegen/render.py | 10 +++- pyecsca/codegen/templates/mult.c | 12 +++++ pyecsca/codegen/templates/mult_bgmw.c | 64 ++++++++++++++++++++++ pyecsca/codegen/templates/mult_comb.c | 77 +++++++++++++++++++++++++++ pyecsca/codegen/templates/mult_fixed_w.c | 4 +- pyecsca/codegen/templates/mult_precomp.c | 85 ++++++++++++++++++++++++++++++ pyecsca/codegen/templates/mult_sliding_w.c | 4 -- test/Makefile | 2 +- test/test_bn.c | 14 ++--- test/test_impl.py | 59 ++++++++++++++++++++- 14 files changed, 401 insertions(+), 78 deletions(-) create mode 100644 pyecsca/codegen/templates/mult_bgmw.c create mode 100644 pyecsca/codegen/templates/mult_comb.c create mode 100644 pyecsca/codegen/templates/mult_precomp.c (limited to 'test') diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c index c3f6d63..148403c 100644 --- a/pyecsca/codegen/bn/bn.c +++ b/pyecsca/codegen/bn/bn.c @@ -594,8 +594,8 @@ exit_k: return result; } -base_t *bn_convert_base(const bn_t *bn, int m) { - base_t *result = NULL; +small_base_t *bn_convert_base_small(const bn_t *bn, int m) { + small_base_t *result = NULL; bn_t k; if (mp_init(&k) != BN_OKAY) { @@ -608,9 +608,9 @@ base_t *bn_convert_base(const bn_t *bn, int m) { goto exit_len; } - result = malloc(sizeof(base_t)); + result = malloc(sizeof(small_base_t)); result->length = len + 1; - result->data = calloc(result->length, sizeof(uint8_t)); + result->data = calloc(result->length, sizeof(int)); result->m = m; int i = 0; @@ -621,7 +621,45 @@ base_t *bn_convert_base(const bn_t *bn, int m) { free(result); goto exit_len; } - result->data[i++] = (uint8_t) val; + result->data[i++] = val; + } + +exit_len: + bn_clear(&k); +exit_k: + return result; +} + +large_base_t *bn_convert_base_large(const bn_t *bn, const bn_t *m) { + large_base_t *result = NULL; + + bn_t k; + if (mp_init(&k) != BN_OKAY) { + goto exit_k; + } + bn_copy(bn, &k); + + int len = 0; + if (mp_log(&k, m, &len) != BN_OKAY) { + goto exit_len; + } + + result = malloc(sizeof(large_base_t)); + result->length = len + 1; + result->data = calloc(result->length, sizeof(bn_t)); + bn_init(&result->m); + bn_copy(m, &result->m); + + int i = 0; + while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) { + bn_init(&result->data[i]); + if (mp_div(&k, m, &k, &result->data[i]) != BN_OKAY) { + free(result->data); + bn_clear(&result->m); + free(result); + goto exit_len; + } + i++; } exit_len: diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h index d5d1e0c..7c25c22 100644 --- a/pyecsca/codegen/bn/bn.h +++ b/pyecsca/codegen/bn/bn.h @@ -65,10 +65,16 @@ typedef struct { } wsliding_t; typedef struct { - uint8_t *data; + int *data; size_t length; int m; -} base_t; +} small_base_t; + +typedef struct { + bn_t *data; + size_t length; + bn_t m; +} large_base_t; void math_init(void); @@ -126,12 +132,14 @@ bn_sign bn_get_sign(const bn_t *one); int bn_get_bit(const bn_t *bn, int which); int bn_bit_length(const bn_t *bn); + wnaf_t *bn_wnaf(const bn_t *bn, int w); wnaf_t *bn_bnaf(const bn_t *bn); wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w); wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w); -base_t *bn_convert_base(const bn_t *bn, int m); +small_base_t *bn_convert_base_small(const bn_t *bn, int m); +large_base_t *bn_convert_base_large(const bn_t *bn, const bn_t *m); #endif //BN_H_ \ No newline at end of file diff --git a/pyecsca/codegen/builder.py b/pyecsca/codegen/builder.py index c595f60..e9a9144 100644 --- a/pyecsca/codegen/builder.py +++ b/pyecsca/codegen/builder.py @@ -177,21 +177,25 @@ def build_impl(ctx, platform, hash, rand, mul, sqr, red, inv, keygen, ecdh, ecds click.echo("[*] Rendered.") click.echo("[ ] Building...") - subprocess.run(["make"], cwd=dir, capture_output=not verbose) - click.echo("[*] Built.") - - if strip: - subprocess.run(["make", "strip"], cwd=dir, capture_output=not verbose) - full_elf_path = path.join(dir, elf_file) - full_hex_path = path.join(dir, hex_file) - shutil.copy(full_elf_path, outdir) - shutil.copy(full_hex_path, outdir) - click.echo(elf_file) - click.echo(hex_file) - if remove: + result = subprocess.run(["make"], cwd=dir, capture_output=not verbose) + if result.returncode != 0: + click.echo("[x] Build failed.") shutil.rmtree(dir) else: - click.echo(dir) + click.echo("[*] Built.") + + if strip: + subprocess.run(["make", "strip"], cwd=dir, capture_output=not verbose) + full_elf_path = path.join(dir, elf_file) + full_hex_path = path.join(dir, hex_file) + shutil.copy(full_elf_path, outdir) + shutil.copy(full_hex_path, outdir) + click.echo(elf_file) + click.echo(hex_file) + if remove: + shutil.rmtree(dir) + else: + click.echo(dir) @main.command("list") diff --git a/pyecsca/codegen/common.py b/pyecsca/codegen/common.py index 6bffbdb..ffe4710 100644 --- a/pyecsca/codegen/common.py +++ b/pyecsca/codegen/common.py @@ -18,6 +18,9 @@ from pyecsca.ec.mult import ( BinaryNAFMultiplier, SlidingWindowMultiplier, FixedWindowLTRMultiplier, + FullPrecompMultiplier, + BGMWMultiplier, + CombMultiplier, ) @@ -49,46 +52,19 @@ class DeviceConfiguration(Configuration): MULTIPLIERS = [ - { - "name": ("ltr", "LTRMultiplier"), - "class": LTRMultiplier - }, - { - "name": ("rtl", "RTLMultiplier"), - "class": RTLMultiplier - }, - { - "name": ("coron", "CoronMultiplier"), - "class": CoronMultiplier - }, - { - "name": ("ldr", "LadderMultiplier"), - "class": LadderMultiplier - }, - { - "name": ("simple-ldr", "SimpleLadderMultiplier"), - "class": SimpleLadderMultiplier - }, - { - "name": ("diff-ldr", "DifferentialLadderMultiplier"), - "class": DifferentialLadderMultiplier - }, - { - "name": ("naf", "bnaf", "BinaryNAFMultiplier"), - "class": BinaryNAFMultiplier - }, - { - "name": ("wnaf", "WindowNAFMultiplier"), - "class": WindowNAFMultiplier - }, - { - "name": ("sliding", "SlidingWindowMultiplier"), - "class": SlidingWindowMultiplier - }, - { - "name": ("fixed", "FixedWindowLTRMultiplier"), - "class": FixedWindowLTRMultiplier - } + {"name": ("ltr", "LTRMultiplier"), "class": LTRMultiplier}, + {"name": ("rtl", "RTLMultiplier"), "class": RTLMultiplier}, + {"name": ("coron", "CoronMultiplier"), "class": CoronMultiplier}, + {"name": ("ldr", "LadderMultiplier"), "class": LadderMultiplier}, + {"name": ("simple-ldr", "SimpleLadderMultiplier"), "class": SimpleLadderMultiplier}, + {"name": ("diff-ldr", "DifferentialLadderMultiplier"), "class": DifferentialLadderMultiplier}, + {"name": ("naf", "bnaf", "BinaryNAFMultiplier"), "class": BinaryNAFMultiplier}, + {"name": ("wnaf", "WindowNAFMultiplier"), "class": WindowNAFMultiplier}, + {"name": ("sliding", "SlidingWindowMultiplier"), "class": SlidingWindowMultiplier}, + {"name": ("fixed", "FixedWindowLTRMultiplier"), "class": FixedWindowLTRMultiplier}, + {"name": ("precomp", "FullPrecompMultiplier"), "class": FullPrecompMultiplier}, + {"name": ("bgmw", "BGMWMultiplier"), "class": BGMWMultiplier}, + {"name": ("comb", "CombMultiplier"), "class": CombMultiplier}, ] diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py index ee07324..241ee6a 100644 --- a/pyecsca/codegen/render.py +++ b/pyecsca/codegen/render.py @@ -25,8 +25,11 @@ from pyecsca.ec.mult import ( WindowNAFMultiplier, SlidingWindowMultiplier, FixedWindowLTRMultiplier, + FullPrecompMultiplier, + BGMWMultiplier, + CombMultiplier, AccumulationOrder, - ProcessingDirection, + ProcessingDirection ) from pyecsca.ec.op import OpType, CodeOp @@ -224,7 +227,10 @@ def render_scalarmult_impl(scalarmult: ScalarMultiplier) -> str: BinaryNAFMultiplier=BinaryNAFMultiplier, WindowNAFMultiplier=WindowNAFMultiplier, SlidingWindowMultiplier=SlidingWindowMultiplier, - FixedWindowLTRMultiplier=FixedWindowLTRMultiplier) + FixedWindowLTRMultiplier=FixedWindowLTRMultiplier, + FullPrecompMultiplier=FullPrecompMultiplier, + BGMWMultiplier=BGMWMultiplier, + CombMultiplier=CombMultiplier) def render_action() -> str: diff --git a/pyecsca/codegen/templates/mult.c b/pyecsca/codegen/templates/mult.c index e580dfc..22a385d 100644 --- a/pyecsca/codegen/templates/mult.c +++ b/pyecsca/codegen/templates/mult.c @@ -39,6 +39,18 @@ {% include "mult_fixed_w.c" %} +{%- elif isinstance(scalarmult, FullPrecompMultiplier) -%} + + {% include "mult_precomp.c" %} + +{%- elif isinstance(scalarmult, BGMWMultiplier) -%} + + {% include "mult_bgmw.c" %} + +{%- elif isinstance(scalarmult, CombMultiplier) -%} + + {% include "mult_comb.c" %} + {%- endif %} diff --git a/pyecsca/codegen/templates/mult_bgmw.c b/pyecsca/codegen/templates/mult_bgmw.c new file mode 100644 index 0000000..5298fb1 --- /dev/null +++ b/pyecsca/codegen/templates/mult_bgmw.c @@ -0,0 +1,64 @@ +#include "mult.h" +#include "point.h" + + + +static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) { + point_t *a = point_copy(curve->neutral); + point_t *b = point_copy(curve->neutral); + + int order_blen = bn_bit_length(&curve->n); + int d = (order_blen + {{ scalarmult.width }} - 1) / {{ scalarmult.width }}; + + point_t **points = malloc(sizeof(point_t *) * d); + + point_t *current = point_copy(point); + for (int i = 0; i < d; i++) { + points[i] = point_copy(current); + if (i != d - 1) { + for (int j = 0; j < {{ scalarmult.width }}; j++) { + point_dbl(current, curve, current); + } + } + } + point_free(current); + + small_base_t *bs = bn_convert_base_small(scalar, {{ 2**scalarmult.width }}); + + for (int j = {{ 2**scalarmult.width }}; j > 0; j--) { + {%- if scalarmult.direction == ProcessingDirection.RTL %} + for (int i = 0; i < bs->length; i++) { + if (bs->data[i] == j) { + point_accumulate(b, points[i], curve, b); + } + } + {%- else %} + for (int i = bs->length - 1; i >= 0; i--) { + if (bs->data[i] == j) { + point_accumulate(b, points[i], curve, b); + } + } + {%- endif -%} + + {%- if scalarmult.short_circuit %} + if (point_equals(a, b)) { + point_dbl(b, curve, a); + continue; + } + {%- endif %} + point_accumulate(a, b, curve, a); + } + free(bs->data); + free(bs); + + {%- if "scl" in scalarmult.formulas %} + point_scl(a, curve, a); + {%- endif %} + point_set(a, out); + for (long i = 0; i < d; i++) { + point_free(points[i]); + } + free(points); + point_free(a); + point_free(b); +} \ No newline at end of file diff --git a/pyecsca/codegen/templates/mult_comb.c b/pyecsca/codegen/templates/mult_comb.c new file mode 100644 index 0000000..9df9796 --- /dev/null +++ b/pyecsca/codegen/templates/mult_comb.c @@ -0,0 +1,77 @@ +#include "mult.h" +#include "point.h" + +static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) { + point_t *q = point_copy(curve->neutral); + + int order_blen = bn_bit_length(&curve->n); + int d = (order_blen + {{ scalarmult.width }} - 1) / {{ scalarmult.width }}; + + point_t *base_points[{{ scalarmult.width }}]; + + point_t *current = point_copy(point); + for (int i = 0; i < {{ scalarmult.width }}; i++) { + base_points[i] = point_copy(current); + if (i != d - 1) { + for (int j = 0; j < d; j++) { + point_dbl(current, curve, current); + } + } + } + point_free(current); + + point_t *points[{{ 2**scalarmult.width }}]; + for (int j = 0; j < {{ 2**scalarmult.width }}; j++) { + point_t *alloc_point = NULL; + for (int i = 0; i < {{ scalarmult.width }}; i++) { + if (j & (1 << i)) { + if (alloc_point) { + point_accumulate(alloc_point, base_points[i], curve, alloc_point); + } else { + alloc_point = point_copy(base_points[i]); + } + } + } + points[j] = alloc_point; + } + + bn_t base; bn_init(&base); + bn_from_int(1, &base); + bn_lsh(&base, d, &base); + + large_base_t *bs = bn_convert_base_large(scalar, &base); + for (int i = d - 1; i >= 0; i--) { + point_dbl(q, curve, q); + int word = 0; + for (int j = 0; j < {{ scalarmult.width }}; j++) { + if (j < bs->length) { + word |= bn_get_bit(&bs->data[j], i) << j; + } + } + if (word) { + point_accumulate(q, points[word], curve, q); + } + } + for (int i = 0; i < bs->length; i++) { + bn_clear(&bs->data[i]); + } + free(bs->data); + bn_clear(&bs->m); + free(bs); + bn_clear(&base); + + + {%- if "scl" in scalarmult.formulas %} + point_scl(a, curve, a); + {%- endif %} + point_set(q, out); + for (int i = 0; i < {{ scalarmult.width }}; i++) { + point_free(base_points[i]); + } + for (int i = 0; i < {{ 2**scalarmult.width }}; i++) { + if (points[i]) { + point_free(points[i]); + } + } + point_free(q); +} \ No newline at end of file diff --git a/pyecsca/codegen/templates/mult_fixed_w.c b/pyecsca/codegen/templates/mult_fixed_w.c index aa95ebd..b0a4bb0 100644 --- a/pyecsca/codegen/templates/mult_fixed_w.c +++ b/pyecsca/codegen/templates/mult_fixed_w.c @@ -35,7 +35,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin point_free(current); point_free(dbl); - base_t *bs = bn_convert_base(scalar, {{ scalarmult.m }}); + small_base_t *bs = bn_convert_base_small(scalar, {{ scalarmult.m }}); for (long i = bs->length - 1; i >= 0; i--) { {%- if bin(scalarmult.m).count("1") == 1 %} @@ -44,7 +44,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin scalar_mult_by_m_base(q, curve); {%- endif %} - uint8_t val = bs->data[i]; + int val = bs->data[i]; if (val) { point_accumulate(q, points[val-1], curve, q); } diff --git a/pyecsca/codegen/templates/mult_precomp.c b/pyecsca/codegen/templates/mult_precomp.c new file mode 100644 index 0000000..cafa0a9 --- /dev/null +++ b/pyecsca/codegen/templates/mult_precomp.c @@ -0,0 +1,85 @@ +#include "mult.h" +#include "point.h" + +void scalar_mult_ltr(int order_blen, point_t **points, bn_t *scalar, point_t *point, curve_t *curve) { + {%- if scalarmult.complete %} + int nbits = order_blen - 1; + {%- else %} + int nbits = bn_bit_length(scalar) - 1; + {%- endif %} + + {%- if scalarmult.always %} + point_t *dummy = point_new(); + {%- endif %} + + for (int i = nbits; i >= 0; i--) { + if (bn_get_bit(scalar, i) == 1) { + point_accumulate(point, points[i], curve, point); + } else { + {%- if scalarmult.always %} + point_accumulate(point, points[i], curve, dummy); + {%- endif %} + } + } + + {%- if scalarmult.always %} + point_free(dummy); + {%- endif %} +} + +void scalar_mult_rtl(int order_blen, point_t **points, bn_t *scalar, point_t *point, curve_t *curve) { + {%- if scalarmult.complete %} + int nbits = order_blen; + {%- else %} + int nbits = bn_bit_length(scalar); + {%- endif %} + + {%- if scalarmult.always %} + point_t *dummy = point_new(); + {%- endif %} + + for (int i = 0; i < nbits; i++) { + if (bn_get_bit(scalar, i) == 1) { + point_accumulate(point, points[i], curve, point); + } else { + {%- if scalarmult.always %} + point_accumulate(point, points[i], curve, dummy); + {%- endif %} + } + } + + {%- if scalarmult.always %} + point_free(dummy); + {%- endif %} +} + +static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) { + point_t *q = point_copy(curve->neutral); + int order_blen = bn_bit_length(&curve->n); + point_t **points = malloc(sizeof(point_t *) * (order_blen + 1)); + + point_t *current = point_copy(point); + for (int i = 0; i < order_blen + 1; i++) { + points[i] = point_copy(current); + if (i != order_blen) { + point_dbl(current, curve, current); + } + } + point_free(current); + + {%- if scalarmult.direction == ProcessingDirection.LTR %} + scalar_mult_ltr(order_blen, points, scalar, q, curve); + {%- else %} + scalar_mult_rtl(order_blen, points, scalar, q, curve); + {%- endif %} + + {%- if "scl" in scalarmult.formulas %} + point_scl(q, curve, q); + {%- endif %} + point_set(q, out); + for (int i = 0; i < order_blen + 1; i++) { + point_free(points[i]); + } + free(points); + point_free(q); +} \ No newline at end of file diff --git a/pyecsca/codegen/templates/mult_sliding_w.c b/pyecsca/codegen/templates/mult_sliding_w.c index 5c9bb6c..1e80a84 100644 --- a/pyecsca/codegen/templates/mult_sliding_w.c +++ b/pyecsca/codegen/templates/mult_sliding_w.c @@ -20,15 +20,11 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin {% elif scalarmult.recoding_direction == ProcessingDirection.RTL %} wsliding_t *ws = bn_wsliding_rtl(scalar, {{ scalarmult.width }}); {% endif %} - //printf("ws %p\n", ws); - //printf("len = %li\n", ws->length); for (long i = 0; i < ws->length; i++) { point_dbl(q, curve, q); uint8_t val = ws->data[i]; - //printf("i = %li, val = %i\n", i, val); if (val) { - //printf("adding %i\n", (val - 1) / 2); point_accumulate(q, points[(val - 1) / 2], curve, q); } } diff --git a/test/Makefile b/test/Makefile index 4b8fc78..d13b487 100644 --- a/test/Makefile +++ b/test/Makefile @@ -1,3 +1,3 @@ test_bn: test_bn.c ../pyecsca/codegen/bn/bn.c - gcc -o $@ $^ -I ../pyecsca/codegen/ -I ../pyecsca/codegen/tommath/ -L ../pyecsca/codegen/tommath/ -l:libtommath-HOST.a \ No newline at end of file + gcc -o $@ $^ -fsanitize=address -fsanitize=undefined -I ../pyecsca/codegen/ -I ../pyecsca/codegen/tommath/ -L ../pyecsca/codegen/tommath/ -l:libtommath-HOST.a \ No newline at end of file diff --git a/test/test_bn.c b/test/test_bn.c index 9e3fd6f..66de22f 100644 --- a/test/test_bn.c +++ b/test/test_bn.c @@ -59,21 +59,21 @@ int test_wsliding_rtl() { } int test_convert_base() { - printf("test_convert-base: "); + printf("test_convert_base: "); bn_t bn; bn_init(&bn); - bn_from_int(5, &bn); - base_t *bs = bn_convert_base(&bn, 2); + bn_from_int(11, &bn); + small_base_t *bs = bn_convert_base_small(&bn, 2); if (bs == NULL) { printf("NULL\n"); return 1; } - if (bs->length != 3) { - printf("Bad length (%li instead of 3)\n", bs->length); + if (bs->length != 4) { + printf("Bad length (%li instead of 4)\n", bs->length); return 1; } - uint8_t expected[3] = {1, 0, 1}; - for (int i = 0; i < 3; i++) { + uint8_t expected[4] = {1, 1, 0, 1}; + for (int i = 0; i < 4; i++) { if (bs->data[i] != expected[i]) { printf("Bad data (%i insead of %i)\n", bs->data[i], expected[i]); return 1; diff --git a/test/test_impl.py b/test/test_impl.py index cb5b583..da42c33 100644 --- a/test/test_impl.py +++ b/test/test_impl.py @@ -16,6 +16,9 @@ from pyecsca.ec.mult import ( ProcessingDirection, ScalarMultiplier, FixedWindowLTRMultiplier, + FullPrecompMultiplier, + BGMWMultiplier, + CombMultiplier, ) from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult @@ -167,6 +170,60 @@ def additional(request): ), id="FIX2", ), + pytest.param( + ( + FullPrecompMultiplier, + "precomp", + ["add-1998-cmo", "dbl-1998-cmo"], + {"direction": ProcessingDirection.LTR}, + ), + id="PRE1", + ), + pytest.param( + ( + FullPrecompMultiplier, + "precomp", + ["add-1998-cmo", "dbl-1998-cmo"], + {"direction": ProcessingDirection.RTL}, + ), + id="PRE2", + ), + pytest.param( + ( + BGMWMultiplier, + "bgmw", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 3, "direction": ProcessingDirection.LTR}, + ), + id="BGMW1", + ), + pytest.param( + ( + BGMWMultiplier, + "bgmw", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 5, "direction": ProcessingDirection.RTL}, + ), + id="BGMW2", + ), + pytest.param( + ( + CombMultiplier, + "comb", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 3}, + ), + id="Comb1", + ), + pytest.param( + ( + CombMultiplier, + "comb", + ["add-1998-cmo", "dbl-1998-cmo"], + {"width": 5}, + ), + id="Comb2", + ), ], ) def target(request, additional, secp128r1) -> ImplTarget: @@ -189,7 +246,7 @@ def target(request, additional, secp128r1) -> ImplTarget: ], env={ "CFLAGS": "-fsanitize=address -fsanitize=undefined -fno-sanitize-recover=all" - } + }, ) assert res.exit_code == 0 target = HostTarget( -- cgit v1.3.1