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. --- pyecsca/codegen/render.py | 36 ++++++++++++++++++++++++++++-------- 1 file changed, 28 insertions(+), 8 deletions(-) (limited to 'pyecsca/codegen/render.py') diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py index 7202e86..0358472 100644 --- a/pyecsca/codegen/render.py +++ b/pyecsca/codegen/render.py @@ -7,15 +7,27 @@ from os import makedirs from typing import Optional, List, Set, Mapping, MutableMapping, Any, Tuple from jinja2 import Environment, PackageLoader -from importlib_resources import files, as_file +from importlib_resources import files from public import public from pyecsca.ec.configuration import HashType, RandomMod, Reduction, Multiplication, Squaring from pyecsca.ec.coordinates import CoordinateModel from pyecsca.ec.formula import Formula from pyecsca.ec.model import CurveModel -from pyecsca.ec.mult import (ScalarMultiplier, LTRMultiplier, RTLMultiplier, CoronMultiplier, - LadderMultiplier, SimpleLadderMultiplier, DifferentialLadderMultiplier, - BinaryNAFMultiplier) +from pyecsca.ec.mult import ( + ScalarMultiplier, + LTRMultiplier, + RTLMultiplier, + CoronMultiplier, + LadderMultiplier, + SimpleLadderMultiplier, + DifferentialLadderMultiplier, + BinaryNAFMultiplier, + WindowNAFMultiplier, + SlidingWindowMultiplier, + FixedWindowLTRMultiplier, + AccumulationOrder, + ProcessingDirection, +) from pyecsca.ec.op import OpType, CodeOp from pyecsca.codegen.common import Platform, DeviceConfiguration @@ -25,6 +37,8 @@ env = Environment( ) env.globals["isinstance"] = isinstance +env.globals["AccumulationOrder"] = AccumulationOrder +env.globals["ProcessingDirection"] = ProcessingDirection def render_op(op: OpType, result: str, left: str, right: str, mod: str, red: str) -> Optional[str]: @@ -148,7 +162,7 @@ def transform_ops(ops: List[CodeOp], parameters: List[str], outputs: Set[str], frees=frees, returns=returns) -def render_coords_impl(coords: CoordinateModel) -> str: +def render_coords_impl(coords: CoordinateModel, accumulation_order: Optional[AccumulationOrder]) -> str: ops = [] for s in coords.satisfying: try: @@ -167,8 +181,11 @@ def render_coords_impl(coords: CoordinateModel) -> str: 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) + to_affine_rets=returns, to_affine_frees=frees, + accumulation_order=accumulation_order) def render_formulas_impl(formulas: Set[Formula]) -> str: @@ -205,7 +222,10 @@ def render_scalarmult_impl(scalarmult: ScalarMultiplier) -> str: LadderMultiplier=LadderMultiplier, SimpleLadderMultiplier=SimpleLadderMultiplier, DifferentialLadderMultiplier=DifferentialLadderMultiplier, - BinaryNAFMultiplier=BinaryNAFMultiplier) + BinaryNAFMultiplier=BinaryNAFMultiplier, + WindowNAFMultiplier=WindowNAFMultiplier, + SlidingWindowMultiplier=SlidingWindowMultiplier, + FixedWindowLTRMultiplier=FixedWindowLTRMultiplier) def render_action() -> str: @@ -257,7 +277,7 @@ def render(config: DeviceConfiguration) -> Tuple[str, str, str]: save_render(temp, "main.c", render_main(config.model, config.coords, config.keygen, config.ecdh, config.ecdsa)) save_render(gen_dir, "defs.h", render_defs(config.model, config.coords)) - save_render(gen_dir, "point.c", render_coords_impl(config.coords)) + save_render(gen_dir, "point.c", render_coords_impl(config.coords, getattr(config.scalarmult, "accumulation_order", None))) save_render(gen_dir, "formulas.c", render_formulas_impl(config.formulas)) for formula in config.formulas: save_render(gen_dir, f"formula_{formula.shortname}.c", -- cgit v1.3 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 'pyecsca/codegen/render.py') 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 From 17c03a2bc34598a91cd897012270ad0cc875f23a Mon Sep 17 00:00:00 2001 From: J08nY Date: Thu, 5 Oct 2023 13:01:06 +0200 Subject: Add option to pass C defines to compiler. --- pyecsca/codegen/builder.py | 22 +++++++++++++++++++--- pyecsca/codegen/common.py | 8 +++++++- pyecsca/codegen/render.py | 6 +++--- pyecsca/codegen/templates/Makefile | 4 ++++ 4 files changed, 33 insertions(+), 7 deletions(-) (limited to 'pyecsca/codegen/render.py') diff --git a/pyecsca/codegen/builder.py b/pyecsca/codegen/builder.py index d0ec648..c595f60 100644 --- a/pyecsca/codegen/builder.py +++ b/pyecsca/codegen/builder.py @@ -4,7 +4,7 @@ import shutil import subprocess from copy import copy from os import path -from typing import List, Optional, Tuple, Type, MutableMapping +from typing import List, Optional, Tuple, Type, MutableMapping, Any import click from public import public @@ -77,6 +77,20 @@ def get_multiplier(ctx: click.Context, param, value: Optional[str]) -> Optional[ return mult +def get_define(ctx: click.Context, param, values: Optional[List[str]]) -> Optional[MutableMapping[str, Any]]: + if values is None: + return None + res = {} + for val in values: + try: + k, v = val.split("=") + except: + k = val + v = 1 + res[k] = v + return res + + @click.group(context_settings={"help_option_names": ["-h", "--help"]}) @click.version_option() @public @@ -122,6 +136,8 @@ def main(): show_default=True) @click.option("--ecdsa/--no-ecdsa", help="Whether to enable ECDSA.", is_flag=True, default=True, show_default=True) +@click.option("-D", "--define", help="Set a custom C define.", multiple=True, + type=str, callback=get_define) @click.option("--strip", help="Whether to strip the binary or not.", is_flag=True) @click.option("--remove/--no-remove", help="Whether to remove the dir.", is_flag=True, default=True, show_default=True) @@ -138,7 +154,7 @@ def main(): @click.argument("outdir") @click.pass_context @public -def build_impl(ctx, platform, hash, rand, mul, sqr, red, inv, keygen, ecdh, ecdsa, strip, remove, +def build_impl(ctx, platform, hash, rand, mul, sqr, red, inv, keygen, ecdh, ecdsa, define, strip, remove, verbose, model, coords, formulas, scalarmult, outdir): """This command builds an ECC implementation. @@ -156,7 +172,7 @@ def build_impl(ctx, platform, hash, rand, mul, sqr, red, inv, keygen, ecdh, ecds click.echo("[ ] Rendering...") config = DeviceConfiguration(model, coords, formulas, scalarmult, hash, rand, mul, sqr, red, - inv, platform, keygen, ecdh, ecdsa) + inv, platform, keygen, ecdh, ecdsa, define) dir, elf_file, hex_file = render(config) click.echo("[*] Rendered.") diff --git a/pyecsca/codegen/common.py b/pyecsca/codegen/common.py index b970039..6bffbdb 100644 --- a/pyecsca/codegen/common.py +++ b/pyecsca/codegen/common.py @@ -1,5 +1,5 @@ from dataclasses import dataclass -from typing import Type, Optional +from typing import Type, Optional, MutableMapping, Any import click from public import public @@ -37,9 +37,15 @@ class DeviceConfiguration(Configuration): """A device configuration that includes the platform and choices specific to the pyecsca-codegened implementations.""" platform: Platform + """The platform to build for.""" keygen: bool + """Whether the key-generation command is present.""" ecdh: bool + """Whether the ECDH command is present.""" ecdsa: bool + """Whether the ECDSA command is present.""" + defines: Optional[MutableMapping[str, Any]] = None + """Optional defines passed to the compilation.""" MULTIPLIERS = [ diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py index ba06a72..ee07324 100644 --- a/pyecsca/codegen/render.py +++ b/pyecsca/codegen/render.py @@ -244,10 +244,10 @@ def render_main(model: CurveModel, coords: CoordinateModel, keygen: bool, ecdh: def render_makefile(platform: Platform, hash_type: HashType, mod_rand: RandomMod, - reduction: Reduction, mul: Multiplication, sqr: Squaring) -> str: + reduction: Reduction, mul: Multiplication, sqr: Squaring, defines: Optional[MutableMapping[str, Any]]) -> str: return env.get_template("Makefile").render(platform=str(platform), hash_type=str(hash_type), mod_rand=str(mod_rand), reduction=str(reduction), - mul=str(mul), sqr=str(sqr)) + mul=str(mul), sqr=str(sqr), defines=defines) def save_render(dir: str, fname: str, rendered: str): @@ -272,7 +272,7 @@ def render(config: DeviceConfiguration) -> Tuple[str, str, str]: makedirs(gen_dir, exist_ok=True) save_render(temp, "Makefile", - render_makefile(config.platform, config.hash_type, config.mod_rand, config.red, config.mult, config.sqr)) + render_makefile(config.platform, config.hash_type, config.mod_rand, config.red, config.mult, config.sqr, config.defines)) save_render(temp, "main.c", render_main(config.model, config.coords, config.keygen, config.ecdh, config.ecdsa)) save_render(gen_dir, "defs.h", render_defs(config.model, config.coords)) diff --git a/pyecsca/codegen/templates/Makefile b/pyecsca/codegen/templates/Makefile index 79e5c20..1b6922c 100644 --- a/pyecsca/codegen/templates/Makefile +++ b/pyecsca/codegen/templates/Makefile @@ -6,6 +6,10 @@ PLATFORM = {{ platform }} CDEFS += -DHASH={{ hash_type }} -DMOD_RAND={{ mod_rand }} -DREDUCTION={{ reduction }} -DMUL={{ mul }} -DSQR={{ sqr }} +{%- if defines %} +CDEFS += {%- for def, value in defines.items() -%}-D{{def}}={{value}} {%- endfor -%} +{%- endif %} + MKDIR_LIST += hash prng asn1 bn gen EXTRAINCDIRS += hash prng asn1 bn gen tommath -- cgit v1.3 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 'pyecsca/codegen/render.py') 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