Add base functions for modular reduction.

7 files changed, 50 insertions, 6 deletions

diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index bf64890..f1a3483 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -3,6 +3,10 @@
 
 #include <tommath.h>
 
+#define RED_MONTGOMERY   1
+#define RED_BARRET 2
+#define RED_BASE 3
+
 #define bn_t mp_int
 #define bn_digit mp_digit
 #define bn_err mp_err
diff --git a/pyecsca/codegen/point.h b/pyecsca/codegen/point.h
index 739078c..01dd4b4 100644
--- a/pyecsca/codegen/point.h
+++ b/pyecsca/codegen/point.h
@@ -15,6 +15,10 @@ bool point_equals(const point_t *one, const point_t *other);
 
 bool point_equals_affine(const point_t *one, const point_t *other, const curve_t *curve);
 
+void point_red_encode(point_t *point, const curve_t *curve);
+
+void point_red_decode(point_t *point, const curve_t *curve);
+
 void point_to_affine(const point_t *point, const curve_t *curve, bn_t *out_x, bn_t *out_y);
 
 void point_from_affine(bn_t *x, bn_t *y, const curve_t *curve, point_t *out);
diff --git a/pyecsca/codegen/rand.h b/pyecsca/codegen/rand.h
index 9305af8..b04293d 100644
--- a/pyecsca/codegen/rand.h
+++ b/pyecsca/codegen/rand.h
@@ -3,6 +3,9 @@
 
 #include "bn/bn.h"
 
+#define MOD_RAND_SAMPLE 1
+#define MOD_RAND_REDUCE 2
+
 bn_err bn_rand_mod(bn_t *out, const bn_t *mod);
 
 #endif //RAND_H_
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/curve.c b/pyecsca/codegen/templates/curve.c
index f99b8d4..4fef683 100644
--- a/pyecsca/codegen/templates/curve.c
+++ b/pyecsca/codegen/templates/curve.c
@@ -8,7 +8,6 @@ curve_t* curve_new(void) {
 	bn_init(&result->{{ param }});
 	{%- endfor %}
 	bn_red_init(&result->p_red);
-	bn_red_init(&result->n_red);
 	result->generator = point_new();
 	result->neutral = point_new();
 
@@ -20,7 +19,6 @@ void curve_free(curve_t *curve) {
 	bn_clear(&curve->{{ param }});
 	{%- endfor %}
 	bn_red_clear(&curve->p_red);
-	bn_red_clear(&curve->n_red);
 	if (curve->generator) {
 		point_free(curve->generator);
 	}
@@ -34,7 +32,7 @@ void curve_set_param(curve_t *curve, char name, const bn_t *value) {
 	switch (name) {
 	{%- for param in params + ["p", "n", "h"] %}
 		case '{{ param }}': bn_copy(value, &curve->{{ param }});
-		{% if param in ("p", "n") %}
+		{% if param == "p" %}
 							bn_red_setup(value, &curve->{{ param }}_red);
 		{%- endif %}
 							break;
diff --git a/pyecsca/codegen/templates/main.c b/pyecsca/codegen/templates/main.c
index 9ca0c7b..d987ab9 100644
--- a/pyecsca/codegen/templates/main.c
+++ b/pyecsca/codegen/templates/main.c
@@ -96,11 +96,17 @@ static uint8_t cmd_set_params(uint8_t *data, uint16_t len) {
 	// need p, [params], n, h, g[xy], i[variables]
 	fat_t affine[2] = {fat_empty, fat_empty};
 	parse_data(data, len, "", parse_set_params, (void *) affine);
+	if (!curve->neutral->infinity) {
+		point_red_encode(curve->neutral, curve);
+	}
+
 	bn_t x; bn_init(&x);
 	bn_t y; bn_init(&y);
 	bn_from_bin(affine[0].value, affine[0].len, &x);
 	bn_from_bin(affine[1].value, affine[1].len, &y);
 
+	bn_red_encode(&x, &curve->p, &curve->p_red);
+	bn_red_encode(&y, &curve->p, &curve->p_red);
 	point_from_affine(&x, &y, curve, curve->generator);
 	bn_clear(&x);
 	bn_clear(&y);
@@ -125,6 +131,8 @@ static uint8_t cmd_generate(uint8_t *data, uint16_t len) {
 	bn_t y; bn_init(&y);
 
 	point_to_affine(pubkey, curve, &x, &y);
+	bn_red_decode(&x, &curve->p, &curve->p_red);
+	bn_red_decode(&y, &curve->p, &curve->p_red);
 
 	uint8_t pub[coord_size * 2];
 	bn_to_binpad(&x, pub, coord_size);
@@ -176,6 +184,8 @@ static uint8_t cmd_set_pubkey(uint8_t *data, uint16_t len) {
 	bn_from_bin(affine[0].value, affine[0].len, &x);
 	bn_from_bin(affine[1].value, affine[1].len, &y);
 
+	bn_red_encode(&x, &curve->p, &curve->p_red);
+	bn_red_encode(&y, &curve->p, &curve->p_red);
 	point_from_affine(&x, &y, curve, pubkey);
 	bn_clear(&x);
 	bn_clear(&y);
@@ -201,6 +211,7 @@ static uint8_t cmd_scalar_mult(uint8_t *data, uint16_t len) {
 	point_t *result = point_new();
 
 	scalar_mult(&scalar, curve->generator, curve, result);
+	//point_red_decode(result, curve);
 
 	uint8_t res[coord_size * {{ curve_variables | length }}];
 	{%- for variable in curve_variables %}
@@ -240,6 +251,8 @@ static uint8_t cmd_ecdh(uint8_t *data, uint16_t len) {
 	bn_from_bin(affine[0].value, affine[0].len, &ox);
 	bn_from_bin(affine[1].value, affine[1].len, &oy);
 
+	bn_red_encode(&ox, &curve->p, &curve->p_red);
+	bn_red_encode(&oy, &curve->p, &curve->p_red);
 	point_from_affine(&ox, &oy, curve, other);
 	bn_clear(&ox);
 	bn_clear(&oy);
@@ -254,6 +267,8 @@ static uint8_t cmd_ecdh(uint8_t *data, uint16_t len) {
 	bn_t y; bn_init(&y);
 
 	point_to_affine(result, curve, &x, &y);
+	bn_red_decode(&x, &curve->p, &curve->p_red);
+	bn_red_decode(&y, &curve->p, &curve->p_red);
 
 	size_t size = bn_to_bin_size(&curve->p);
 
@@ -328,6 +343,8 @@ static uint8_t cmd_ecdsa_sign(uint8_t *data, uint16_t len) {
 
 	bn_t r; bn_init(&r);
 	point_to_affine(p, curve, &r, NULL);
+	bn_red_decode(&r, &curve->p, &curve->p_red);
+
 	bn_mod(&r, &curve->n, &r);
 	// r = ([k]G).x mod n
 
@@ -399,12 +416,14 @@ static uint8_t cmd_ecdsa_verify(uint8_t *data, uint16_t len) {
 
 	point_t *p1 = point_new();
 	point_t *p2 = point_new();
+
 	scalar_mult(&h, curve->generator, curve, p1);
 	scalar_mult(&r, pubkey, curve, p2);
 
 	point_add(p1, p2, curve, p1);
 	bn_t x; bn_init(&x);
 	point_to_affine(p1, curve, &x, NULL);
+	bn_red_decode(&x, &curve->p, &curve->p_red);
 	bn_mod(&x, &curve->n, &x);
 
 	bool result = bn_eq(&orig_r, &x);
diff --git a/pyecsca/codegen/templates/point.c b/pyecsca/codegen/templates/point.c
index 0096516..1ea116f 100644
--- a/pyecsca/codegen/templates/point.c
+++ b/pyecsca/codegen/templates/point.c
@@ -76,6 +76,22 @@ bool point_equals_affine(const point_t *one, const point_t *other, const curve_t
 	return result;
 }
 
+void point_red_encode(point_t *point, const curve_t *curve) {
+	#if REDUCTION == RED_MONTGOMERY
+		{%- for variable in variables %}
+		bn_red_encode(&point->{{ variable }}, &curve->p, &curve->p_red);
+		{%- endfor %}
+	#endif
+}
+
+void point_red_decode(point_t *point, const curve_t *curve) {
+	#if REDUCTION == RED_MONTGOMERY
+		{%- for variable in variables %}
+		bn_red_decode(&point->{{ variable }}, &curve->p, &curve->p_red);
+		{%- endfor %}
+	#endif
+}
+
 void point_to_affine(const point_t *point, const curve_t *curve, bn_t *out_x, bn_t *out_y) {
 	{{ start_action("coord_map") }}
 	{{ ops.render_all(allocations, initializations, operations, returns, frees, "err") }}
diff --git a/pyecsca/codegen/templates/rand.c b/pyecsca/codegen/templates/rand.c
index e39c829..f29238a 100644
--- a/pyecsca/codegen/templates/rand.c
+++ b/pyecsca/codegen/templates/rand.c
@@ -1,4 +1,4 @@
-#include "bn/bn.h"
+#include "rand.h"
 #include "action.h"
 {% from "action.c" import start_action, end_action %}
 
@@ -6,9 +6,9 @@ bn_err bn_rand_mod(bn_t *out, const bn_t *mod) {
 	{{ start_action("random_mod") }}
 
 	#if MOD_RAND == MOD_RAND_SAMPLE
-	bn_err err = bn_rand_mod_sample(out, mod);
+		bn_err err = bn_rand_mod_sample(out, mod);
 	#elif MOD_RAND == MOD_RAND_REDUCE
-	bn_err err = bn_rand_mod_reduce(out, mod);
+		bn_err err = bn_rand_mod_reduce(out, mod);
 	#endif
 
 	{{ end_action("random_mod") }}