Add fixed-base multipliers with precomputation.

11 files changed, 335 insertions, 69 deletions

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);
         }
 	}