Merge pull request #10 from J08nY/feat/equivalence-tests

Equivalence tests

15 files changed, 207 insertions, 48 deletions

diff --git a/pyecsca/codegen/templates/formula_add.c b/pyecsca/codegen/templates/formula_add.c
index 6026601..48bab07 100644
--- a/pyecsca/codegen/templates/formula_add.c
+++ b/pyecsca/codegen/templates/formula_add.c
@@ -16,16 +16,17 @@ __attribute__((noinline)) void point_add(const point_t *one, const point_t *othe
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(other, out_one);
-			return;
+			goto end;
 		}
 		if (point_equals(other, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("add") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_dbl.c b/pyecsca/codegen/templates/formula_dbl.c
index 451b0ee..e1cfa15 100644
--- a/pyecsca/codegen/templates/formula_dbl.c
+++ b/pyecsca/codegen/templates/formula_dbl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_dbl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("dbl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_neg.c b/pyecsca/codegen/templates/formula_neg.c
index 93fbe20..fa96c63 100644
--- a/pyecsca/codegen/templates/formula_neg.c
+++ b/pyecsca/codegen/templates/formula_neg.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_neg(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("neg") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_scl.c b/pyecsca/codegen/templates/formula_scl.c
index 48ac52e..f1471a2 100644
--- a/pyecsca/codegen/templates/formula_scl.c
+++ b/pyecsca/codegen/templates/formula_scl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_scl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("scl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_tpl.c b/pyecsca/codegen/templates/formula_tpl.c
index d280bad..0b4cd64 100644
--- a/pyecsca/codegen/templates/formula_tpl.c
+++ b/pyecsca/codegen/templates/formula_tpl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_tpl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("tpl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult.c b/pyecsca/codegen/templates/mult.c
index 0144e36..4070952 100644
--- a/pyecsca/codegen/templates/mult.c
+++ b/pyecsca/codegen/templates/mult.c
@@ -31,6 +31,10 @@
 
     {% include "mult_wnaf.c" %}
 
+{%- elif isinstance(scalarmult, WindowBoothMultiplier) -%}
+
+    {% include "mult_booth.c" %}
+
 {%- elif isinstance(scalarmult, SlidingWindowMultiplier) -%}
 
     {% include "mult_sliding_w.c" %}
diff --git a/pyecsca/codegen/templates/mult_bgmw.c b/pyecsca/codegen/templates/mult_bgmw.c
index 5298fb1..e2e8c72 100644
--- a/pyecsca/codegen/templates/mult_bgmw.c
+++ b/pyecsca/codegen/templates/mult_bgmw.c
@@ -48,8 +48,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
         {%- endif %}
         point_accumulate(a, b, curve, a);
 	}
-	free(bs->data);
-	free(bs);
+	bn_small_base_clear(bs);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(a, curve, a);
diff --git a/pyecsca/codegen/templates/mult_bnaf.c b/pyecsca/codegen/templates/mult_bnaf.c
index 68d1569..9c760af 100644
--- a/pyecsca/codegen/templates/mult_bnaf.c
+++ b/pyecsca/codegen/templates/mult_bnaf.c
@@ -1,51 +1,109 @@
 #include "mult.h"
 #include "point.h"
 
-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_t *scalar_mult_ltr(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf, size_t bits) {
+    point_t *q;
+    long i;
+    {% if scalarmult.complete %}
+	    bn_naf_pad_left(naf, 0, (bits + 1) - naf->length);
+	    q = point_copy(curve->neutral);
+	    i = 0;
+	{% else %}
+	    bn_naf_strip_left(naf, 0);
+	    int8_t val = naf->data[0];
+	    if (val == 1) {
+            q = point_copy(point);
+	    } else if (val == -1) {
+            q = point_copy(neg);
+        }
+        i = 1;
+	{% endif %}
+
+    {% if scalarmult.always %}
+        point_t *q_copy = point_new();
+    {% endif %}
+	for (; i < naf->length; i++) {
 		point_dbl(q, curve, q);
+
+		{% if scalarmult.always %}
+            point_set(q, q_copy);
+        {% endif %}
+
 		if (naf->data[i] == 1) {
 			point_accumulate(q, point, curve, q);
+			{% if scalarmult.always %}
+                point_accumulate(q_copy, neg, curve, q_copy);
+            {% endif %}
 		} else if (naf->data[i] == -1) {
 			point_accumulate(q, neg, curve, q);
+			{% if scalarmult.always %}
+                point_accumulate(q_copy, point, curve, q_copy);
+            {% endif %}
 		}
 	}
+	{% if scalarmult.always %}
+        point_free(q_copy);
+    {% endif %}
     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();
+point_t* scalar_mult_rtl(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf, size_t bits) {
+    {% if scalarmult.always %}
+        point_t *r_copy = point_new();
+    {% endif %}
+
+    {% if scalarmult.complete %}
+	    bn_naf_pad_left(naf, 0, (bits + 1) - naf->length);
+	{% endif %}
+
+	bn_naf_reverse(naf);
+
+    point_t *q = point_copy(point);
+    point_t *r = point_copy(curve->neutral);
+    point_t *q_neg = point_new();
     for (long i = 0; i < naf->length; i++) {
+        {% if scalarmult.always %}
+            point_set(r, r_copy);
+        {% endif %}
+
         if (naf->data[i] == 1) {
-            point_accumulate(q, r, curve, q);
+            point_accumulate(r, q, curve, r);
+            {% if scalarmult.always %}
+                point_neg(q, curve, q_neg);
+                point_accumulate(r_copy, q_neg, curve, r_copy);
+            {% endif %}
         } else if (naf->data[i] == -1) {
-            point_neg(r, curve, r_neg);
-            point_accumulate(q, r_neg, curve, q);
+            point_neg(q, curve, q_neg);
+            point_accumulate(r, q_neg, curve, r);
+            {% if scalarmult.always %}
+                point_accumulate(r_copy, q, curve, r_copy);
+            {% endif %}
         }
-        point_dbl(r, curve, r);
+        point_dbl(q, curve, q);
     }
-    point_free(r_neg);
-    point_free(r);
+    point_free(q_neg);
+    point_free(q);
 
-    return q;
+    {% if scalarmult.always %}
+        point_free(r_copy);
+    {% endif %}
+    return r;
 }
 
 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);
+	size_t bits = bn_bit_length(&curve->n);
 
     {% if scalarmult.direction == ProcessingDirection.LTR %}
-        point_t *q = scalar_mult_ltr(point, neg, curve, naf);
+        point_t *q = scalar_mult_ltr(point, neg, curve, naf, bits);
     {% elif scalarmult.direction == ProcessingDirection.RTL %}
-        point_t *q = scalar_mult_rtl(point, neg, curve, naf);
+        point_t *q = scalar_mult_rtl(point, neg, curve, naf, bits);
     {% endif %}
 
-    free(naf->data);
-	free(naf);
+    bn_naf_clear(naf);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);
diff --git a/pyecsca/codegen/templates/mult_booth.c b/pyecsca/codegen/templates/mult_booth.c
new file mode 100644
index 0000000..4c1ba40
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_booth.c
@@ -0,0 +1,78 @@
+#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 *points[{{ 2 ** (scalarmult.width - 1) }}];
+    {% if scalarmult.precompute_negation %}
+        point_t *points_neg[{{ 2 ** (scalarmult.width - 1) }}];
+    {% endif %}
+
+    point_t *current = point_copy(point);
+    point_t *dbl = point_new();
+    point_dbl(current, curve, dbl);
+    points[0] = point_copy(current);
+    {% if scalarmult.precompute_negation %}
+        points_neg[0] = point_new();
+        point_neg(points[0], curve, points_neg[0]);
+    {% endif %}
+    {% if scalarmult.width > 1 %}
+        points[1] = point_copy(dbl);
+        {% if scalarmult.precompute_negation %}
+            points_neg[1] = point_new();
+            point_neg(points[1], curve, points_neg[1]);
+        {% endif %}
+    {% endif %}
+
+    point_set(dbl, current);
+    {% if scalarmult.width > 2 %}
+        for (long i = 2; i < {{ 2 ** (scalarmult.width - 1) }}; i++) {
+            point_add(current, point, curve, current);
+            points[i] = point_copy(current);
+            {% if scalarmult.precompute_negation %}
+                points_neg[i] = point_new();
+                point_neg(points[i], curve, points_neg[i]);
+            {% endif %}
+        }
+    {% endif %}
+    point_free(current);
+    point_free(dbl);
+
+    size_t bits = bn_bit_length(&curve->n);
+
+    booth_t *bs = bn_booth(scalar, {{ scalarmult.width }}, bits);
+
+    point_t *q = point_copy(curve->neutral);
+    point_t *neg = point_new();
+    for (long i = 0; i < bs->length; i++) {
+        for (long j = 0; j < {{ scalarmult.width }}; j++) {
+            point_dbl(q, curve, q);
+        }
+        int32_t val = bs->data[i];
+        if (val > 0) {
+            point_accumulate(q, points[val - 1], curve, q);
+        } else if (val < 0) {
+            {% if scalarmult.precompute_negation %}
+                point_accumulate(q, points_neg[-val - 1], curve, q);
+            {% else %}
+                point_neg(points[-val - 1], curve, neg);
+                point_accumulate(q, neg, curve, q);
+            {% endif %}
+        }
+    }
+    bn_booth_clear(bs);
+    point_free(neg);
+
+    {%- 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]);
+        {% if scalarmult.precompute_negation %}
+            point_free(points_neg[i]);
+        {% endif %}
+    }
+    point_free(q);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_comb.c b/pyecsca/codegen/templates/mult_comb.c
index 9df9796..1fbb5a3 100644
--- a/pyecsca/codegen/templates/mult_comb.c
+++ b/pyecsca/codegen/templates/mult_comb.c
@@ -39,6 +39,10 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 	bn_from_int(1, &base);
     bn_lsh(&base, d, &base);
 
+    {% if scalarmult.always %}
+        point_t *dummy = point_new();
+    {% endif %}
+
 	large_base_t *bs = bn_convert_base_large(scalar, &base);
 	for (int i = d - 1; i >= 0; i--) {
         point_dbl(q, curve, q);
@@ -50,14 +54,18 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
         }
         if (word) {
             point_accumulate(q, points[word], curve, q);
+        } else {
+            {% if scalarmult.always %}
+                int j = i % {{ 2**scalarmult.width }};
+                if (j == 0) {
+                    point_accumulate(q, point, curve, dummy);
+                } else {
+                    point_accumulate(q, points[j], curve, dummy);
+                }
+            {% endif %}
         }
 	}
-	for (int i = 0; i < bs->length; i++) {
-	    bn_clear(&bs->data[i]);
-	}
-	free(bs->data);
-	bn_clear(&bs->m);
-	free(bs);
+	bn_large_base_clear(bs);
 	bn_clear(&base);
 
 
diff --git a/pyecsca/codegen/templates/mult_fixed_w.c b/pyecsca/codegen/templates/mult_fixed_w.c
index b0a4bb0..6a079b3 100644
--- a/pyecsca/codegen/templates/mult_fixed_w.c
+++ b/pyecsca/codegen/templates/mult_fixed_w.c
@@ -20,18 +20,22 @@ void scalar_mult_by_m_base(point_t *point, curve_t *curve) {
 
 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 *points[{{ scalarmult.m - 1 }}];
 
     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);
+    {% if scalarmult.m > 2 %}
+        points[1] = point_copy(dbl);
+    {% endif %}
     point_set(dbl, current);
-    for (long i = 2; i < {{ scalarmult.m }}; i++) {
-        point_add(current, point, curve, current);
-        points[i] = point_copy(current);
-    }
+    {% if scalarmult.m > 3 %}
+        for (long i = 2; i < {{ scalarmult.m - 1 }}; i++) {
+            point_add(current, point, curve, current);
+            points[i] = point_copy(current);
+        }
+    {% endif %}
     point_free(current);
     point_free(dbl);
 
@@ -49,14 +53,13 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 			point_accumulate(q, points[val-1], curve, q);
         }
 	}
-	free(bs->data);
-	free(bs);
+	bn_small_base_clear(bs);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);
     {%- endif %}
     point_set(q, out);
-    for (long i = 0; i < {{ scalarmult.m }}; i++) {
+    for (long i = 0; i < {{ scalarmult.m - 1 }}; i++) {
         point_free(points[i]);
     }
 	point_free(q);
diff --git a/pyecsca/codegen/templates/mult_rtl.c b/pyecsca/codegen/templates/mult_rtl.c
index 71949b4..119ee7e 100644
--- a/pyecsca/codegen/templates/mult_rtl.c
+++ b/pyecsca/codegen/templates/mult_rtl.c
@@ -5,6 +5,12 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	point_t *q = point_copy(point);
 	point_t *r = point_copy(curve->neutral);
 
+    {% if scalarmult.complete %}
+	    size_t bits = bn_bit_length(&curve->n);
+	{% else %}
+        size_t bits = bn_bit_length(scalar);
+    {% endif %}
+
 	{%- if scalarmult.always %}
 		point_t *dummy = point_new();
 	{%- endif %}
@@ -12,7 +18,7 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	bn_init(&copy);
 	bn_copy(scalar, &copy);
 
-    while (!bn_is_0(&copy)) {
+    for (int i = 0; i < bits; i++) {
         if (bn_get_bit(&copy, 0) == 1) {
             point_accumulate(r, q, curve, r);
         } else {
diff --git a/pyecsca/codegen/templates/mult_simple_ldr.c b/pyecsca/codegen/templates/mult_simple_ldr.c
index ceb257a..33bfcd9 100644
--- a/pyecsca/codegen/templates/mult_simple_ldr.c
+++ b/pyecsca/codegen/templates/mult_simple_ldr.c
@@ -11,7 +11,7 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	{%- endif %}
 
 	for (int i = nbits; i >= 0; i--) {
-		if (bn_get_bit(scalar, i) == 1) {
+		if (bn_get_bit(scalar, i) == 0) {
 			point_add(p0, p1, curve, p1);
 			point_dbl(p0, curve, p0);
 		} else {
diff --git a/pyecsca/codegen/templates/mult_sliding_w.c b/pyecsca/codegen/templates/mult_sliding_w.c
index 1e80a84..347c313 100644
--- a/pyecsca/codegen/templates/mult_sliding_w.c
+++ b/pyecsca/codegen/templates/mult_sliding_w.c
@@ -34,8 +34,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
     {%- endif %}
     point_set(q, out);
 
-    free(ws->data);
-	free(ws);
+    bn_wsliding_clear(ws);
     for (long i = 0; i < {{ 2 ** (scalarmult.width - 1) }}; i++) {
         point_free(points[i]);
     }
diff --git a/pyecsca/codegen/templates/mult_wnaf.c b/pyecsca/codegen/templates/mult_wnaf.c
index 3c5f2b2..569e78b 100644
--- a/pyecsca/codegen/templates/mult_wnaf.c
+++ b/pyecsca/codegen/templates/mult_wnaf.c
@@ -26,7 +26,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 
 	wnaf_t *naf = bn_wnaf(scalar, {{ scalarmult.width }});
 
-	for (long i = naf->length - 1; i >= 0; i--) {
+	for (long i = 0; i < naf->length; i++) {
 		point_dbl(q, curve, q);
 		int8_t val = naf->data[i];
 		if (val > 0) {
@@ -40,8 +40,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 		    {%- endif %}
 		}
 	}
-	free(naf->data);
-	free(naf);
+	bn_naf_clear(naf);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);