Add wNAF scalarmult, more options implemented for other scalarmults.

7 files changed, 132 insertions, 24 deletions

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