Add wNAF scalarmult, more options implemented for other scalarmults.

10 files changed, 168 insertions, 35 deletions

diff --git a/pyecsca/codegen/builder.py b/pyecsca/codegen/builder.py
index 2cd572b..d0ec648 100644
--- a/pyecsca/codegen/builder.py
+++ b/pyecsca/codegen/builder.py
@@ -13,7 +13,7 @@ from pyecsca.ec.configuration import (Multiplication, Squaring, Reduction, HashT
 from pyecsca.ec.coordinates import CoordinateModel
 from pyecsca.ec.formula import Formula, AdditionFormula
 from pyecsca.ec.model import CurveModel
-from pyecsca.ec.mult import ScalarMultiplier
+from pyecsca.ec.mult import ScalarMultiplier, AccumulationOrder, ProcessingDirection
 
 from .render import render
 from .common import Platform, DeviceConfiguration, MULTIPLIERS, wrap_enum, get_model, get_coords
@@ -40,7 +40,7 @@ def get_multiplier(ctx: click.Context, param, value: Optional[str]) -> Optional[
     if value is None:
         return None
     res = re.match(
-            "(?P<name>[a-zA-Z\-]+)\((?P<args>([a-zA-Z_]+ *= *[a-zA-Z0-9]+, ?)*?([a-zA-Z_]+ *= *[a-zA-Z0-9]+)*)\)",
+            "(?P<name>[a-zA-Z\-]+)\((?P<args>([a-zA-Z_]+ *= *[a-zA-Z0-9.]+, ?)*?([a-zA-Z_]+ *= *[a-zA-Z0-9.]+)*)\)",
             value)
     if not res:
         raise click.BadParameter("Couldn't parse multiplier spec: {}.".format(value))
@@ -61,7 +61,10 @@ def get_multiplier(ctx: click.Context, param, value: Optional[str]) -> Optional[
         raise click.BadParameter(
                 "Multiplier {} requires formulas: {}, got {}.".format(mult_class.__name__,
                                                                       mult_class.requires, classes))
-    kwargs = eval("dict(" + args + ")")
+    globs = dict(globals())
+    globs["AccumulationOrder"] = AccumulationOrder
+    globs["ProcessingDirection"] = ProcessingDirection
+    kwargs = eval("dict(" + args + ")", globs)
     required = set(
             filter(lambda formula: any(isinstance(formula, cls) for cls in mult_class.requires),
                    formulas))
diff --git a/pyecsca/codegen/point.h b/pyecsca/codegen/point.h
index 01dd4b4..fd3736e 100644
--- a/pyecsca/codegen/point.h
+++ b/pyecsca/codegen/point.h
@@ -51,4 +51,6 @@ void point_ladd(const point_t *one, const point_t *other, const point_t *diff, c
 bool point_ladd_init(void);
 void point_ladd_clear(void);
 
+void point_accumulate(const point_t *one, const point_t *other, const curve_t *curve, point_t *out_one);
+
 #endif //POINT_H_
\ No newline at end of file
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",
diff --git a/pyecsca/codegen/templates/main.c b/pyecsca/codegen/templates/main.c
index 4d50cc2..8aed65a 100644
--- a/pyecsca/codegen/templates/main.c
+++ b/pyecsca/codegen/templates/main.c
@@ -562,15 +562,6 @@ static uint8_t cmd_set_trigger(uint8_t *data, uint16_t len) {
 	return 0;
 }
 
-__attribute__((noinline)) void init(void) {
-	// Initalize the platform, UART, triggers.
-	platform_init();
-    init_uart();
-    trigger_setup();
-
-	init_implementation();
-}
-
 __attribute__((noinline)) void init_implementation(void) {
     // Initialize some components that preallocate stuff.
     prng_init();
@@ -583,6 +574,15 @@ __attribute__((noinline)) void init_implementation(void) {
     bn_init(&privkey);
 }
 
+__attribute__((noinline)) void init(void) {
+	// Initalize the platform, UART, triggers.
+	platform_init();
+    init_uart();
+    trigger_setup();
+
+	init_implementation();
+}
+
 __attribute__((noinline)) void deinit(void) {
 	// Clear up allocated stuff.
     bn_clear(&privkey);
@@ -616,7 +616,7 @@ int main(void) {
 
     // Execute commands while SimpleSerial is alive.
 	//led_ok(1);
-    while(simpleserial_get());
+    while(simpleserial_get()) {}
     //led_ok(0);
 
 	deinit();
diff --git a/pyecsca/codegen/templates/mult.c b/pyecsca/codegen/templates/mult.c
index 0603bc0..f7169e6 100644
--- a/pyecsca/codegen/templates/mult.c
+++ b/pyecsca/codegen/templates/mult.c
@@ -27,6 +27,18 @@
 
 	{% include "mult_bnaf.c" %}
 
+{%- elif isinstance(scalarmult, WindowNAFMultiplier) -%}
+
+    {% include "mult_wnaf.c" %}
+
+{%- elif isinstance(scalarmult, SlidingWindowMultiplier) -%}
+
+    {% include "mult_sliding_w.c" %} {# TODO #}
+
+{%- elif isinstance(scalarmult, FixedWindowLTRMultiplier) -%}
+
+    {% include "mult_fixed_w.c" %} {# TODO #}
+
 {%- endif %}
 
 
diff --git a/pyecsca/codegen/templates/mult_bnaf.c b/pyecsca/codegen/templates/mult_bnaf.c
index 33e7302..68d1569 100644
--- a/pyecsca/codegen/templates/mult_bnaf.c
+++ b/pyecsca/codegen/templates/mult_bnaf.c
@@ -1,22 +1,50 @@
 #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 *neg = point_new();
-	point_neg(point, curve, neg);
-	point_t *q = point_copy(curve->neutral);
-
-	wnaf_t *naf = bn_bnaf(scalar);
-
+point_t *scalar_mult_ltr(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf) {
+    point_t *q = point_copy(curve->neutral);
 	for (long i = naf->length - 1; i >= 0; i--) {
 		point_dbl(q, curve, q);
 		if (naf->data[i] == 1) {
-			point_add(q, point, curve, q);
+			point_accumulate(q, point, curve, q);
 		} else if (naf->data[i] == -1) {
-			point_add(q, neg, curve, q);
+			point_accumulate(q, neg, curve, q);
 		}
 	}
-	free(naf->data);
+    return q;
+}
+
+point_t* scalar_mult_rtl(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf) {
+    point_t *r = point_copy(point);
+    point_t *q = point_copy(curve->neutral);
+    point_t *r_neg = point_new();
+    for (long i = 0; i < naf->length; i++) {
+        if (naf->data[i] == 1) {
+            point_accumulate(q, r, curve, q);
+        } else if (naf->data[i] == -1) {
+            point_neg(r, curve, r_neg);
+            point_accumulate(q, r_neg, curve, q);
+        }
+        point_dbl(r, curve, r);
+    }
+    point_free(r_neg);
+    point_free(r);
+
+    return q;
+}
+
+static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	point_t *neg = point_new();
+	point_neg(point, curve, neg);
+	wnaf_t *naf = bn_bnaf(scalar);
+
+    {% if scalarmult.direction == ProcessingDirection.LTR %}
+        point_t *q = scalar_mult_ltr(point, neg, curve, naf);
+    {% elif scalarmult.direction == ProcessingDirection.RTL %}
+        point_t *q = scalar_mult_rtl(point, neg, curve, naf);
+    {% endif %}
+
+    free(naf->data);
 	free(naf);
 
     {%- if "scl" in scalarmult.formulas %}
diff --git a/pyecsca/codegen/templates/mult_ltr.c b/pyecsca/codegen/templates/mult_ltr.c
index f8bee19..d4aaf10 100644
--- a/pyecsca/codegen/templates/mult_ltr.c
+++ b/pyecsca/codegen/templates/mult_ltr.c
@@ -19,10 +19,10 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
     for (int i = nbits; i >= 0; i--) {
         point_dbl(r, curve, r);
         if (bn_get_bit(scalar, i) == 1) {
-            point_add(r, q, curve, r);
+            point_accumulate(r, q, curve, r);
         } else {
         	{%- if scalarmult.always %}
-			point_add(r, q, curve, dummy);
+			point_accumulate(r, q, curve, dummy);
 			{%- endif %}
         }
     }
diff --git a/pyecsca/codegen/templates/mult_rtl.c b/pyecsca/codegen/templates/mult_rtl.c
index 9db12fb..71949b4 100644
--- a/pyecsca/codegen/templates/mult_rtl.c
+++ b/pyecsca/codegen/templates/mult_rtl.c
@@ -14,10 +14,10 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 
     while (!bn_is_0(&copy)) {
         if (bn_get_bit(&copy, 0) == 1) {
-            point_add(r, q, curve, r);
+            point_accumulate(r, q, curve, r);
         } else {
         	{%- if scalarmult.always %}
-			point_add(r, q, curve, dummy);
+			point_accumulate(r, q, curve, dummy);
 			{%- endif %}
         }
         point_dbl(q, curve, q);
diff --git a/pyecsca/codegen/templates/mult_wnaf.c b/pyecsca/codegen/templates/mult_wnaf.c
new file mode 100644
index 0000000..3c5f2b2
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_wnaf.c
@@ -0,0 +1,60 @@
+#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 - 2) }}];
+    {%- if scalarmult.precompute_negation %}
+        point_t *points_neg[{{ 2 ** (scalarmult.width - 2) }}];
+    {%- else %}
+        point_t *neg = point_new();
+    {%- endif %}
+
+    point_t *current = point_copy(point);
+    point_t *dbl = point_new();
+    point_dbl(current, curve, dbl);
+    for (long i = 0; i < {{ 2 ** (scalarmult.width - 2) }}; i++) {
+        points[i] = point_copy(current);
+        {%- if scalarmult.precompute_negation %}
+            points_neg[i] = point_copy(current);
+            point_neg(points_neg[i], curve, points_neg[i]);
+        {%- endif %}
+        point_add(current, dbl, curve, current);
+    }
+    point_free(current);
+    point_free(dbl);
+
+	wnaf_t *naf = bn_wnaf(scalar, {{ scalarmult.width }});
+
+	for (long i = naf->length - 1; i >= 0; i--) {
+		point_dbl(q, curve, q);
+		int8_t val = naf->data[i];
+		if (val > 0) {
+			point_accumulate(q, points[(val - 1) / 2], curve, q);
+		} else if (val < 0) {
+		    {%- if scalarmult.precompute_negation %}
+		        point_accumulate(q, points_neg[(-val - 1) / 2], curve, q);
+		    {%- else %}
+		        point_neg(points[(-val - 1) / 2], curve, neg);
+                point_accumulate(q, neg, curve, q);
+		    {%- endif %}
+		}
+	}
+	free(naf->data);
+	free(naf);
+
+    {%- if "scl" in scalarmult.formulas %}
+    	point_scl(q, curve, q);
+    {%- endif %}
+    point_set(q, out);
+    for (long i = 0; i < {{ 2 ** (scalarmult.width - 2) }}; i++) {
+        point_free(points[i]);
+        {%- if scalarmult.precompute_negation %}
+            point_free(points_neg[i]);
+        {%- endif %}
+    }
+    {%- if not scalarmult.precompute_negation %}
+    point_free(neg);
+    {%- endif %}
+	point_free(q);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/point.c b/pyecsca/codegen/templates/point.c
index e87ae36..b4d6e94 100644
--- a/pyecsca/codegen/templates/point.c
+++ b/pyecsca/codegen/templates/point.c
@@ -137,3 +137,11 @@ void point_from_affine(bn_t *x, bn_t *y, const curve_t *curve, point_t *out) {
 	{%- endfor %}
 	{{ end_action("coord_map") }}
 }
+
+void point_accumulate(const point_t *one, const point_t *other, const curve_t *curve, point_t *out_one) {
+    {% if accumulation_order == "PeqPR" %}
+        point_add(one, other, curve, out_one);
+    {% elif accumulation_order == "PeqRP" %}
+        point_add(other, one, curve, out_one);
+    {% endif %}
+}
\ No newline at end of file