Implement multipliers.

18 files changed, 286 insertions, 8 deletions

diff --git a/pyecsca/codegen/templates/Makefile b/pyecsca/codegen/templates/Makefile
index 27402e4..9526640 100644
--- a/pyecsca/codegen/templates/Makefile
+++ b/pyecsca/codegen/templates/Makefile
@@ -1,14 +1,14 @@
 TARGET = pyecsca-codegen
 
-SRC += main.c bn/bn.c asn1/asn1.c hash/hash.c mult/mult.c prng/prng.c gen/point.c gen/curve.c
+SRC += main.c bn/bn.c asn1/asn1.c hash/hash.c prng/prng.c gen/point.c gen/curve.c gen/mult.c
 
 PLATFORM = {{ platform }}
 
-CDEFS += -DHASH={{ hash_type }} -DMULT={{ mult_algo }} -DMOD_RAND={{ mod_rand }}
+CDEFS += -DHASH={{ hash_type }} -DMOD_RAND={{ mod_rand }}
 
-MKDIR_LIST += hash prng mult asn1 bn gen
+MKDIR_LIST += hash prng asn1 bn gen
 
-EXTRAINCDIRS += hash prng mult asn1 bn gen tommath
+EXTRAINCDIRS += hash prng asn1 bn gen tommath
 
 LDFLAGS += tommath/libtommath-{{ platform }}.a
 
diff --git a/pyecsca/codegen/templates/formula_add.c b/pyecsca/codegen/templates/formula_add.c
index 971dd0a..05fd541 100644
--- a/pyecsca/codegen/templates/formula_add.c
+++ b/pyecsca/codegen/templates/formula_add.c
@@ -1,3 +1,13 @@
 void point_add(const point_t *one, const point_t *other, const curve_t *curve, point_t *out_one) {
+	{%- if short_circuit %}
+		if (point_equals(one, curve->neutral)) {
+			point_set(other, out_one);
+			return;
+		}
+		if (point_equals(other, curve->neutral)) {
+			point_set(one, out_one);
+			return;
+		}
+	{%- endif %}
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_dadd.c b/pyecsca/codegen/templates/formula_dadd.c
index 5d3bd05..7f4d2e5 100644
--- a/pyecsca/codegen/templates/formula_dadd.c
+++ b/pyecsca/codegen/templates/formula_dadd.c
@@ -1,3 +1,4 @@
 void point_dadd(const point_t *one, const point_t *other, const point_t *diff, const curve_t *curve, point_t *out_one) {
+	// TODO: short-circuits
 	{%- include "ops.c" %}
 }
diff --git a/pyecsca/codegen/templates/formula_dbl.c b/pyecsca/codegen/templates/formula_dbl.c
index 89543a1..bf91efb 100644
--- a/pyecsca/codegen/templates/formula_dbl.c
+++ b/pyecsca/codegen/templates/formula_dbl.c
@@ -1,3 +1,9 @@
 void point_dbl(const point_t *one, const curve_t *curve, point_t *out_one) {
+	{%- if short_circuit %}
+		if (point_equals(one, curve->neutral)) {
+			point_set(one, out_one);
+			return;
+		}
+	{%- endif %}
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_ladd.c b/pyecsca/codegen/templates/formula_ladd.c
index 73f2325..81bcf73 100644
--- a/pyecsca/codegen/templates/formula_ladd.c
+++ b/pyecsca/codegen/templates/formula_ladd.c
@@ -1,3 +1,4 @@
 void point_ladd(const point_t *one, const point_t *other, const point_t *diff, const curve_t *curve, point_t *out_one, point_t *out_other) {
+	// TODO: short-circuits
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_neg.c b/pyecsca/codegen/templates/formula_neg.c
index 156053c..fc790de 100644
--- a/pyecsca/codegen/templates/formula_neg.c
+++ b/pyecsca/codegen/templates/formula_neg.c
@@ -1,3 +1,9 @@
 void point_neg(const point_t *one, const curve_t *curve, point_t *out_one) {
+	{%- if short_circuit %}
+		if (point_equals(one, curve->neutral)) {
+			point_set(one, out_one);
+			return;
+		}
+	{%- endif %}
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_scl.c b/pyecsca/codegen/templates/formula_scl.c
index a9595eb..b5db4d7 100644
--- a/pyecsca/codegen/templates/formula_scl.c
+++ b/pyecsca/codegen/templates/formula_scl.c
@@ -1,3 +1,9 @@
 void point_scl(const point_t *one, const curve_t *curve, point_t *out_one) {
+	{%- if short_circuit %}
+		if (point_equals(one, curve->neutral)) {
+			point_set(one, out_one);
+			return;
+		}
+	{%- endif %}
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_tpl.c b/pyecsca/codegen/templates/formula_tpl.c
index debfd37..9b5df25 100644
--- a/pyecsca/codegen/templates/formula_tpl.c
+++ b/pyecsca/codegen/templates/formula_tpl.c
@@ -1,3 +1,9 @@
 void point_tpl(const point_t *one, const curve_t *curve, point_t *out_one) {
+	{%- if short_circuit %}
+		if (point_equals(one, curve->neutral)) {
+			point_set(one, out_one);
+			return;
+		}
+	{%- endif %}
 	{%- include "ops.c" %}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/main.c b/pyecsca/codegen/templates/main.c
index 14a4e58..1c9491b 100644
--- a/pyecsca/codegen/templates/main.c
+++ b/pyecsca/codegen/templates/main.c
@@ -2,10 +2,10 @@
 #include "simpleserial/simpleserial.h"
 #include "asn1/asn1.h"
 #include "hash/hash.h"
-#include "mult/mult.h"
 #include "bn/bn.h"
 #include "prng/prng.h"
 #include "gen/defs.h"
+#include "mult.h"
 #include "point.h"
 #include "curve.h"
 #include "fat.h"
@@ -97,7 +97,7 @@ static uint8_t cmd_generate(uint8_t *data, uint16_t len) {
 	{%- for variable in curve_variables %}
 	bn_to_binpad(&pubkey->{{ variable }}, pub + coord_size * {{ loop.index0 }}, coord_size);
 	{%- endfor %}
-	simpleserial_put('w', coord_size * {{ curve_parameters | length }}, pub);
+	simpleserial_put('w', coord_size * {{ curve_variables | length }}, pub);
 	return 0;
 }
 
@@ -138,7 +138,7 @@ static void parse_scalar_mult(const char *path, const uint8_t *data, size_t len,
 }
 
 static uint8_t cmd_scalar_mult(uint8_t *data, uint16_t len) {
-	// perform base point scalar mult with supplied scalar, return affine point.
+	// perform base point scalar mult with supplied scalar.
 	bn_t scalar; bn_init(&scalar);
 	parse_data(data, len, "", parse_scalar_mult, (void *) &scalar);
 	size_t coord_size = bn_to_bin_size(&curve->p);
@@ -151,7 +151,7 @@ static uint8_t cmd_scalar_mult(uint8_t *data, uint16_t len) {
 	{%- for variable in curve_variables %}
 	bn_to_binpad(&result->{{ variable }}, res + coord_size * {{ loop.index0 }}, coord_size);
 	{%- endfor %}
-	simpleserial_put('w', coord_size * {{ curve_parameters | length }}, res);
+	simpleserial_put('w', coord_size * {{ curve_variables | length }}, res);
 	bn_clear(&scalar);
 	point_free(result);
 	return 0;
diff --git a/pyecsca/codegen/templates/mult.c b/pyecsca/codegen/templates/mult.c
new file mode 100644
index 0000000..61ec825
--- /dev/null
+++ b/pyecsca/codegen/templates/mult.c
@@ -0,0 +1,18 @@
+
+#include "mult.h"
+
+{%- if isinstance(scalarmult, LTRMultiplier) -%}
+{%- include "mult_ltr.c" %}
+{%- elif isinstance(scalarmult, RTLMultiplier) -%}
+{%- include "mult_rtl.c" %}
+{%- elif isinstance(scalarmult, CoronMultiplier) -%}
+{%- include "mult_coron.c" %}
+{%- elif isinstance(scalarmult, LadderMultiplier) -%}
+{%- include "mult_ldr.c" %}
+{%- elif isinstance(scalarmult, SimpleLadderMultiplier) -%}
+{%- include "mult_simple_ldr.c" %}
+{%- elif isinstance(scalarmult, DifferentialLadderMultiplier) -%}
+{%- include "mult_diff_ldr.c" %}
+{%- elif isinstance(scalarmult, BinaryNAFMultiplier) -%}
+{%- include "mult_bnaf.c" %}
+{%- endif -%}
diff --git a/pyecsca/codegen/templates/mult_bnaf.c b/pyecsca/codegen/templates/mult_bnaf.c
new file mode 100644
index 0000000..0b9c4de
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_bnaf.c
@@ -0,0 +1,28 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(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);
+
+	for (size_t i = naf->length; i >= 0; i--) {
+		point_dbl(q, curve, q);
+		if (naf->data[i] == 1) {
+			point_add(q, point, curve, q);
+		} else if (naf->data[i] == -1) {
+			point_add(q, neg, curve, q);
+		}
+	}
+	free(naf->data);
+	free(naf);
+
+    {%- if "scl" in scalarmult.formulas %}
+    	point_scl(q, curve, q);
+    {%- endif %}
+    point_set(q, out);
+	point_free(neg);
+	point_free(q);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_coron.c b/pyecsca/codegen/templates/mult_coron.c
new file mode 100644
index 0000000..d8e8a0d
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_coron.c
@@ -0,0 +1,22 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	point_t *p0 = point_copy(point);
+	point_t *p1 = point_new();
+
+	int nbits = bn_bit_length(scalar);
+	for (int i = nbits - 2; i >= 0; i--) {
+	  point_dbl(p0, curve, p0);
+	  point_add(p0, point, curve, p1);
+	  if (bn_get_bit(scalar, i) != 0) {
+		 point_set(p1, p0);
+	  }
+	}
+	{%- if "scl" in scalarmult.formulas %}
+		point_scl(p0, curve, p0);
+	{%- endif %}
+	point_set(p0, out);
+	point_free(p0);
+	point_free(p1);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_diff_ldr.c b/pyecsca/codegen/templates/mult_diff_ldr.c
new file mode 100644
index 0000000..2683116
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_diff_ldr.c
@@ -0,0 +1,29 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	point_t *p0 = point_copy(&curve->neutral);
+	point_t *p1 = point_copy(point);
+	{%- if scalarmult.complete %}
+		int nbits = bn_bit_length(&curve->n) - 1;
+	{%- else %}
+		int nbits = bn_bit_length(scalar) - 1;
+	{%- endif %}
+
+	for (int i = nbits; i >= 0; i--) {
+		if (bn_get_bit(scalar, i) == 0) {
+			point_dadd(point, p0, p1, curve, p1);
+			point_dbl(p0, curve, p0);
+		} else {
+			point_dadd(point, p0, p1, curve, p0);
+			point_dbl(p1, curve, p1);
+		}
+	}
+
+	{%- if "scl" in scalarmult.formulas %}
+    	point_scl(p0, curve, p0);
+    {%- endif %}
+	point_set(p0, out);
+	point_free(p0);
+	point_free(p1);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_ldr.c b/pyecsca/codegen/templates/mult_ldr.c
new file mode 100644
index 0000000..cabab0b
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_ldr.c
@@ -0,0 +1,30 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	{%- if scalarmult.complete %}
+		point_t *p0 = point_copy(&curve->neutral);
+		point_t *p1 = point_copy(point);
+		int nbits = bn_bit_length(&curve->n) - 1;
+	{%- else %}
+		point_t *p0 = point_copy(point);
+		point_t *p1 = point_new();
+		point_dbl(point, curve, p1);
+		int nbits = bn_bit_length(scalar) - 2;
+	{%- endif %}
+
+	for (int i = nbits; i >= 0; i--) {
+		if (bn_get_bit(scalar, i) == 0) {
+			point_ladd(p0, p1, curve, p0, p1);
+		} else {
+			point_ladd(p1, p0, curve, p1, p0);
+		}
+	}
+
+	{%- if "scl" in scalarmult.formulas %}
+    	point_scl(p0, curve, p0);
+    {%- endif %}
+	point_set(p0, out);
+	point_free(p0);
+	point_free(p1);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_ltr.c b/pyecsca/codegen/templates/mult_ltr.c
new file mode 100644
index 0000000..9b7d87e
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_ltr.c
@@ -0,0 +1,40 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	{%- if scalarmult.complete %}
+		point_t *q = point_copy(point);
+		point_t *r = point_copy(curve->neutral);
+		int nbits = bn_bit_length(&curve->n) - 1;
+	{%- else %}
+		point_t *q = point_new();
+		point_dbl(point, curve, q);
+		point_t *r = point_copy(point);
+		int nbits = bn_bit_length(scalar) - 2;
+	{%- endif %}
+
+	{%- if scalarmult.always %}
+		point_t *dummy = point_new();
+	{%- endif %}
+
+    for (int i = nbits; i >= 0; i--) {
+        point_dbl(r, curve, r);
+        if (bn_get_bit(scalar, i) == 1) {
+            point_add(q, r, curve, r);
+        } else {
+        	{%- if scalarmult.always %}
+			point_add(q, r, curve, dummy);
+			{%- endif %}
+        }
+    }
+    {%- if "scl" in scalarmult.formulas %}
+    	point_scl(r, curve, r);
+    {%- endif %}
+
+    point_set(r, out);
+    point_free(q);
+    point_free(r);
+	{%- if scalarmult.always %}
+		point_free(dummy);
+	{%- endif %}
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_rtl.c b/pyecsca/codegen/templates/mult_rtl.c
new file mode 100644
index 0000000..af437e0
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_rtl.c
@@ -0,0 +1,37 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	point_t *q = point_copy(point);
+	point_t *r = point_copy(curve->neutral);
+
+	{%- if scalarmult.always %}
+		point_t *dummy = point_new();
+	{%- endif %}
+	bn_t copy;
+	bn_init(&copy);
+	bn_copy(scalar, &copy);
+
+    while (!bn_is_0(&copy)) {
+        if (bn_get_bit(&copy, i) == 1) {
+            point_add(q, r, curve, r);
+        } else {
+        	{%- if scalarmult.always %}
+			point_add(q, r, curve, dummy);
+			{%- endif %}
+        }
+        point_dbl(q, curve, q);
+        bn_rsh(&copy, 1, &copy);
+    }
+    {%- if "scl" in scalarmult.formulas %}
+    	point_scl(r, curve, r);
+    {%- endif %}
+
+    point_set(r, out);
+    point_free(q);
+    point_free(r);
+    bn_clear(&copy);
+	{%- if scalarmult.always %}
+		point_free(dummy);
+	{%- endif %}
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_simple_ldr.c b/pyecsca/codegen/templates/mult_simple_ldr.c
new file mode 100644
index 0000000..438a44b
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_simple_ldr.c
@@ -0,0 +1,29 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+	point_t *p0 = point_copy(&curve->neutral);
+	point_t *p1 = point_copy(point);
+	{%- if scalarmult.complete %}
+		int nbits = bn_bit_length(&curve->n) - 1;
+	{%- else %}
+		int nbits = bn_bit_length(scalar) - 1;
+	{%- endif %}
+
+	for (int i = nbits; i >= 0; i--) {
+		if (bn_get_bit(scalar, i) == 1) {
+			point_add(p0, p1, curve, p1);
+			point_dbl(p0, curve, p0);
+		} else {
+			point_add(p0, p1, curve, p0);
+			point_dbl(p1, curve, p1);
+		}
+	}
+
+	{%- if "scl" in scalarmult.formulas %}
+    	point_scl(p0, curve, p0);
+    {%- endif %}
+	point_set(p0, out);
+	point_free(p0);
+	point_free(p1);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/point.c b/pyecsca/codegen/templates/point.c
index 973fc42..689d598 100644
--- a/pyecsca/codegen/templates/point.c
+++ b/pyecsca/codegen/templates/point.c
@@ -29,6 +29,15 @@ void point_free(point_t *point) {
 	free(point);
 }
 
+bool point_equals(const point_t *one, const point_t *other) {
+	{%- for variable in variables %}
+	if (!bn_eq(&one->{{ variable }}, &other->{{ variable }})) {
+		return false;
+	}
+	{%- endfor %}
+	return true;
+}
+
 void point_to_affine(point_t *point, curve_t *curve, bn_t *out_x, bn_t *out_y) {
 	{%- include "ops.c" %}
 	{%- if "x" in allocations %}