Add fixed width scalarmult.

8 files changed, 179 insertions, 9 deletions

diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index e0c4bcb..13d7134 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -53,7 +53,7 @@ bn_err bn_from_int(unsigned int value, bn_t *out) {
 	} else {
 		mp_set_u32(out, value);
 	}
-	return MP_OKAY;
+	return BN_OKAY;
 }
 
 bn_err bn_to_binpad(const bn_t *one, uint8_t *data, size_t size) {
@@ -350,6 +350,10 @@ bn_err bn_rsh(const bn_t *one, int amount, bn_t *out) {
 	return mp_div_2d(one, amount, out, NULL);
 }
 
+bn_err bn_and(const bn_t *one, const bn_t *other, bn_t *out) {
+    return mp_and(one, other, out);
+}
+
 bool bn_eq(const bn_t *one, const bn_t *other) {
 	return mp_cmp_mag(one, other) == MP_EQ;
 }
@@ -485,7 +489,7 @@ wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w) {
                 }
                 bn_from_int((1 << v) - 1, &mask);  // mask = ((2**v) - 1) << (b - v + 1)
                 bn_lsh(&mask, b - v + 1, &mask);
-                mp_and(&mask, bn, &mask);  // mask = (i & mask)
+                bn_and(&mask, bn, &mask);  // mask = (i & mask)
                 bn_rsh(&mask, b - v + 1, &mask);  // mask = mask >> (b - v + 1)
                 if (bn_get_bit(&mask, 0)) {  // if c & 1:
                     u = (int) bn_to_int(&mask);    // u = c
@@ -550,7 +554,7 @@ wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) {
             bn_rsh(&k, 1, &k);
         } else {
             bn_from_int((1 << w) - 1, &mask);  // mask = ((2**w) - 1)
-            mp_and(&mask, &k, &mask);
+            bn_and(&mask, &k, &mask);
             arr[i++] = bn_to_int(&mask);
             for (int j = 0; j < w - 1; j++) {
                 arr[i++] = 0;
@@ -581,4 +585,40 @@ exit_mask:
     bn_clear(&k);
 exit_k:
 	return result;
+}
+
+base_t *bn_convert_base(const bn_t *bn, int m) {
+    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_n(&k, m, &len) != BN_OKAY) {
+        goto exit_len;
+    }
+
+    result = malloc(sizeof(base_t));
+    result->length = len + 1;
+    result->data = calloc(result->length, sizeof(uint8_t));
+    result->m = m;
+
+    int i = 0;
+    mp_digit val = 0;
+    while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) {
+        if (mp_div_d(&k, m, &k, &val) != BN_OKAY) {
+            free(result->data);
+            free(result);
+            goto exit_len;
+        }
+        result->data[i++] = (uint8_t) val;
+    }
+
+exit_len:
+    bn_clear(&k);
+exit_k:
+    return result;
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index 0732fb1..d5d1e0c 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -64,6 +64,12 @@ typedef struct {
     int w;
 } wsliding_t;
 
+typedef struct {
+    uint8_t *data;
+    size_t length;
+    int m;
+} base_t;
+
 void math_init(void);
 
 bn_err  bn_init(bn_t *bn);
@@ -111,6 +117,7 @@ void   bn_red_clear(red_t *out);
 
 bn_err bn_lsh(const bn_t *one, int amount, bn_t *out);
 bn_err bn_rsh(const bn_t *one, int amount, bn_t *out);
+bn_err bn_and(const bn_t *one, const bn_t *other, bn_t *out);
 
 bool    bn_eq(const bn_t *one, const bn_t *other);
 bool    bn_is_0(const bn_t *one);
@@ -125,4 +132,6 @@ 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);
+
 #endif //BN_H_
\ No newline at end of file
diff --git a/pyecsca/codegen/common.py b/pyecsca/codegen/common.py
index 2f3dfbd..b970039 100644
--- a/pyecsca/codegen/common.py
+++ b/pyecsca/codegen/common.py
@@ -17,6 +17,7 @@ from pyecsca.ec.mult import (
     WindowNAFMultiplier,
     BinaryNAFMultiplier,
     SlidingWindowMultiplier,
+    FixedWindowLTRMultiplier,
 )
 
 
@@ -77,6 +78,10 @@ MULTIPLIERS = [
     {
         "name": ("sliding", "SlidingWindowMultiplier"),
         "class": SlidingWindowMultiplier
+    },
+    {
+        "name": ("fixed", "FixedWindowLTRMultiplier"),
+        "class": FixedWindowLTRMultiplier
     }
 ]
 
diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py
index 0358472..ba06a72 100644
--- a/pyecsca/codegen/render.py
+++ b/pyecsca/codegen/render.py
@@ -37,6 +37,7 @@ env = Environment(
 )
 
 env.globals["isinstance"] = isinstance
+env.globals["bin"] = bin
 env.globals["AccumulationOrder"] = AccumulationOrder
 env.globals["ProcessingDirection"] = ProcessingDirection
 
@@ -181,8 +182,6 @@ def render_coords_impl(coords: CoordinateModel, accumulation_order: Optional[Acc
     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,
                                               accumulation_order=accumulation_order)
diff --git a/pyecsca/codegen/templates/mult_fixed_w.c b/pyecsca/codegen/templates/mult_fixed_w.c
new file mode 100644
index 0000000..aa95ebd
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_fixed_w.c
@@ -0,0 +1,63 @@
+#include "mult.h"
+#include "point.h"
+
+void scalar_mult_by_m_pow2(point_t *point, curve_t *curve) {
+    unsigned int m = {{ scalarmult.m }} >> 1;
+    while (m) {
+        point_dbl(point, curve, point);
+        m >>= 1;
+    }
+}
+
+void scalar_mult_by_m_base(point_t *point, curve_t *curve) {
+    point_t *orig = point_copy(point);
+    point_dbl(orig, curve, point);
+    for (int i = 0; i < {{ scalarmult.m - 2}}; i++) {
+        point_add(point, orig, curve, point);
+    }
+    point_free(orig);
+}
+
+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 *current = point_copy(point);
+    point_t *dbl = point_new();
+    point_dbl(current, curve, dbl);
+    points[0] = point_copy(current);
+    points[1] = point_copy(dbl);
+    point_set(dbl, current);
+    for (long i = 2; i < {{ scalarmult.m }}; i++) {
+        point_add(current, point, curve, current);
+        points[i] = point_copy(current);
+    }
+    point_free(current);
+    point_free(dbl);
+
+    base_t *bs = bn_convert_base(scalar, {{ scalarmult.m }});
+
+	for (long i = bs->length - 1; i >= 0; i--) {
+	    {%- if bin(scalarmult.m).count("1") == 1 %}
+	        scalar_mult_by_m_pow2(q, curve);
+	    {%- else %}
+	        scalar_mult_by_m_base(q, curve);
+	    {%- endif %}
+
+		uint8_t val = bs->data[i];
+		if (val) {
+			point_accumulate(q, points[val-1], curve, q);
+        }
+	}
+	free(bs->data);
+	free(bs);
+
+    {%- if "scl" in scalarmult.formulas %}
+    	point_scl(q, curve, q);
+    {%- endif %}
+    point_set(q, out);
+    for (long i = 0; i < {{ scalarmult.m }}; i++) {
+        point_free(points[i]);
+    }
+	point_free(q);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/point.c b/pyecsca/codegen/templates/point.c
index b4d6e94..bad232a 100644
--- a/pyecsca/codegen/templates/point.c
+++ b/pyecsca/codegen/templates/point.c
@@ -139,9 +139,9 @@ void point_from_affine(bn_t *x, bn_t *y, const curve_t *curve, point_t *out) {
 }
 
 void point_accumulate(const point_t *one, const point_t *other, const curve_t *curve, point_t *out_one) {
-    {% if accumulation_order == "PeqPR" %}
+    {% if accumulation_order == AccumulationOrder.PeqPR %}
         point_add(one, other, curve, out_one);
-    {% elif accumulation_order == "PeqRP" %}
+    {% elif accumulation_order == AccumulationOrder.PeqRP %}
         point_add(other, one, curve, out_one);
     {% endif %}
 }
\ No newline at end of file
diff --git a/test/test_bn.c b/test/test_bn.c
index a77fe9a..9e3fd6f 100644
--- a/test/test_bn.c
+++ b/test/test_bn.c
@@ -1,4 +1,5 @@
 #include <stdio.h>
+#include <stdlib.h>
 #include "bn/bn.h"
 
 int test_wsliding_ltr() {
@@ -23,6 +24,9 @@ int test_wsliding_ltr() {
         }
     }
     printf("OK\n");
+    bn_clear(&bn);
+    free(ws->data);
+    free(ws);
     return 0;
 }
 
@@ -48,9 +52,40 @@ int test_wsliding_rtl() {
         }
     }
     printf("OK\n");
+    bn_clear(&bn);
+    free(ws->data);
+    free(ws);
+    return 0;
+}
+
+int test_convert_base() {
+    printf("test_convert-base: ");
+    bn_t bn;
+    bn_init(&bn);
+    bn_from_int(5, &bn);
+    base_t *bs = bn_convert_base(&bn, 2);
+    if (bs == NULL) {
+        printf("NULL\n");
+        return 1;
+    }
+    if (bs->length != 3) {
+        printf("Bad length (%li instead of 3)\n", bs->length);
+        return 1;
+    }
+    uint8_t expected[3] = {1, 0, 1};
+    for (int i = 0; i < 3; i++) {
+        if (bs->data[i] != expected[i]) {
+            printf("Bad data (%i insead of %i)\n", bs->data[i], expected[i]);
+            return 1;
+        }
+    }
+    printf("OK\n");
+    bn_clear(&bn);
+    free(bs->data);
+    free(bs);
     return 0;
 }
 
 int main(void) {
-    return test_wsliding_ltr() + test_wsliding_rtl();
-}
\ No newline at end of file
+    return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base();
+}
diff --git a/test/test_impl.py b/test/test_impl.py
index 147792e..c125ce6 100644
--- a/test/test_impl.py
+++ b/test/test_impl.py
@@ -15,6 +15,7 @@ from pyecsca.ec.mult import (
     AccumulationOrder,
     ProcessingDirection,
     ScalarMultiplier,
+    FixedWindowLTRMultiplier,
 )
 from pyecsca.ec.signature import ECDSA_SHA1, SignatureResult
 
@@ -148,6 +149,24 @@ def additional(request):
             ),
             id="SLI2",
         ),
+        pytest.param(
+            (
+                FixedWindowLTRMultiplier,
+                "fixed",
+                ["add-1998-cmo", "dbl-1998-cmo"],
+                {"m": 4},
+            ),
+            id="FIX1",
+        ),
+        pytest.param(
+            (
+                FixedWindowLTRMultiplier,
+                "fixed",
+                ["add-1998-cmo", "dbl-1998-cmo"],
+                {"m": 5},
+            ),
+            id="FIX2",
+        ),
     ],
 )
 def target(request, additional, secp128r1) -> ImplTarget: