Add reduction functions, add global trigger for whole cmd.

2 files changed, 202 insertions, 8 deletions

diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index 1247c5d..22e1d49 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -135,6 +135,174 @@ bn_err bn_mod(const bn_t *one, const bn_t *mod, bn_t *out) {
 	return mp_mod(one, mod, out);
 }
 
+bn_err bn_red_init(red_t *out) {
+	#if REDUCTION == RED_MONTGOMERY
+		return bn_init(&out->montgomery_renorm);
+	#elif REDUCTION == RED_BARRETT
+		return bn_init(&out->barret);
+	#endif
+		return BN_OKAY;
+}
+
+bn_err bn_red_setup(const bn_t *mod, red_t *out) {
+	#if REDUCTION == RED_MONTGOMERY
+		bn_err err;
+		if ((err = mp_montgomery_setup(mod, &out->montgomery_digit)) != BN_OKAY) {
+			return err;
+		}
+		if ((err = mp_montgomery_calc_normalization(&out->montgomery_renorm, mod)) != BN_OKAY) {
+			return err;
+		}
+		return mp_sqrmod(&out->montgomery_renorm, mod, &out->montgomery_renorm_sqr);
+	#elif REDUCTION == RED_BARRETT
+		return mp_reduce_setup(mod, &out->barret);
+	#endif
+		return BN_OKAY;
+}
+
+bn_err bn_red_encode(bn_t *one, const bn_t *mod, const red_t *red) {
+	#if REDUCTION == RED_MONTGOMERY
+		return mp_mulmod(one, &red->montgomery_renorm, mod, one);
+	#else
+		return BN_OKAY;
+	#endif
+}
+
+bn_err bn_red_decode(bn_t *one, const bn_t *mod, const red_t *red) {
+	#if REDUCTION == RED_MONTGOMERY
+		return mp_montgomery_reduce(one, mod, red->montgomery_digit);
+	#else
+		return BN_OKAY;
+	#endif
+}
+
+bn_err bn_red_add(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_add(one, other, out)) != BN_OKAY) {
+		return err;
+	}
+	if (mp_cmp(out, mod) == MP_GT) {
+		return mp_sub(out, mod, out);
+	} else {
+		return err;
+	}
+}
+
+bn_err bn_red_sub(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_sub(one, other, out)) != BN_OKAY) {
+		return err;
+	}
+	if (mp_cmp_d(out, 0) == MP_LT) {
+		return mp_add(out, mod, out);
+	}
+	if (mp_cmp(out, mod) == MP_GT) {
+		return mp_sub(out, mod, out);
+	}
+	return err;
+}
+
+bn_err bn_red_neg(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_neg(one, out)) != BN_OKAY) {
+		return err;
+	}
+	if (mp_cmp_d(out, 0) == MP_LT) {
+		return mp_add(out, mod, out);
+	}
+	return err;
+}
+
+bn_err bn_red_mul(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_mul(one, other, out)) != BN_OKAY) {
+		return err;
+	}
+	return bn_red_reduce(mod, red, out);
+}
+
+bn_err bn_red_sqr(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_sqr(one, out)) != BN_OKAY) {
+		return err;
+	}
+	return bn_red_reduce(mod, red, out);
+}
+
+bn_err bn_red_inv(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_err err;
+	if ((err = mp_invmod(one, mod, out)) != BN_OKAY) {
+		return err;
+	}
+	#if REDUCTION == RED_MONTGOMERY
+		return mp_mulmod(out, &red->montgomery_renorm_sqr, mod, out);
+	#else
+		return err;
+	#endif
+}
+
+bn_err bn_red_div(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out) {
+	bn_t inv;
+	bn_err err;
+	if ((err = mp_init(&inv)) != BN_OKAY) {
+		return err;
+	}
+	if ((err = mp_copy(other, &inv)) != BN_OKAY) {
+		goto out;
+	}
+	#if REDUCTION == RED_MONTGOMERY
+		if ((err = mp_montgomery_reduce(&inv, mod, red->montgomery_digit)) != BN_OKAY) {
+			goto out;
+		}
+	#endif
+	if ((err = mp_invmod(&inv, mod, &inv)) != BN_OKAY) {
+		goto out;
+	}
+	if ((err = mp_mulmod(one, &inv, mod, out)) != BN_OKAY) {
+		goto out;
+	}
+out:
+	mp_clear(&inv);
+	return err;
+}
+
+bn_err bn_red_pow(const bn_t *base, const bn_t *exp, const bn_t *mod, const red_t *red, bn_t *out) {
+	int blen = bn_bit_length(exp);
+	bn_t result;
+	bn_err err;
+	if ((err = bn_init(&result)) != BN_OKAY) {
+		return err;
+	}
+	if ((err = bn_copy(base, &result)) != BN_OKAY) {
+		bn_clear(&result);
+		return err;
+	}
+	for (int i = blen - 2; i > 0; --i) {
+		bn_red_sqr(&result, mod, red, &result);
+		if (bn_get_bit(exp, i)) {
+			bn_red_mul(&result, base, mod, red, &result);
+		}
+	}
+	return BN_OKAY;
+}
+
+bn_err bn_red_reduce(const bn_t *mod, const red_t *red, bn_t *what) {
+	#if REDUCTION == RED_MONTGOMERY
+		return mp_montgomery_reduce(what, mod, red->montgomery_digit);
+	#elif REDUCTION == RED_BARRETT
+		return mp_reduce(what, mod, red->barrett);
+	#endif
+		return mp_mod(what, mod, what);
+}
+
+void bn_red_clear(red_t *out) {
+	#if REDUCTION == RED_MONTGOMERY
+		bn_clear(&out->montgomery_renorm);
+	#elif REDUCTION == RED_BARRETT
+		bn_clear(&out->barret);
+	#endif
+}
+
 bn_err bn_lsh(const bn_t *one, int amount, bn_t *out) {
 	return mp_mul_2d(one, amount, out);
 }
diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index eb6e942..bf64890 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -4,6 +4,7 @@
 #include <tommath.h>
 
 #define bn_t mp_int
+#define bn_digit mp_digit
 #define bn_err mp_err
 #define bn_sign mp_sign
 
@@ -23,6 +24,16 @@
 #define BN_GT MP_GT /* greater than */
 
 typedef struct {
+	#if REDUCTION == RED_MONTGOMERY
+	bn_digit montgomery_digit;
+	bn_t montgomery_renorm;
+	bn_t montgomery_renorm_sqr;
+	#elif REDUCTION == RED_BARRETT
+	bn_t barret;
+	#endif
+} red_t;
+
+typedef struct {
 	char name;
 	bn_t value;
 } named_bn_t;
@@ -33,10 +44,10 @@ typedef struct {
 	int w;
 } wnaf_t;
 
-bn_err bn_init(bn_t *bn);
+bn_err  bn_init(bn_t *bn);
 #define bn_init_multi mp_init_multi
-bn_err bn_copy(const bn_t *from, bn_t *to);
-void bn_clear(bn_t *bn);
+bn_err  bn_copy(const bn_t *from, bn_t *to);
+void    bn_clear(bn_t *bn);
 #define bn_clear_multi mp_clear_multi
 
 bn_err bn_from_bin(const uint8_t *data, size_t size, bn_t *out);
@@ -60,16 +71,31 @@ bn_err bn_mod_inv(const bn_t *one, const bn_t *mod, bn_t *out);
 bn_err bn_mod_pow(const bn_t *one, const bn_t *exp, const bn_t *mod, bn_t *out);
 bn_err bn_mod(const bn_t *one, const bn_t *mod, bn_t *out);
 
+bn_err bn_red_init(red_t *out);
+bn_err bn_red_setup(const bn_t *mod, red_t *out);
+bn_err bn_red_encode(bn_t *one, const bn_t *mod, const red_t *red);
+bn_err bn_red_decode(bn_t *one, const bn_t *mod, const red_t *red);
+bn_err bn_red_add(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_sub(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_neg(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_mul(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_sqr(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_inv(const bn_t *one, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_div(const bn_t *one, const bn_t *other, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_pow(const bn_t *base, const bn_t *exp, const bn_t *mod, const red_t *red, bn_t *out);
+bn_err bn_red_reduce(const bn_t *mod, const red_t *red, bn_t *what);
+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);
 
-bool bn_eq(const bn_t *one, const bn_t *other);
-bool bn_is_0(const bn_t *one);
-bool bn_is_1(const bn_t *one);
+bool    bn_eq(const bn_t *one, const bn_t *other);
+bool    bn_is_0(const bn_t *one);
+bool    bn_is_1(const bn_t *one);
 bn_sign bn_get_sign(const bn_t *one);
 
-int bn_get_bit(const bn_t *bn, int which);
-int bn_bit_length(const bn_t *bn);
+int     bn_get_bit(const bn_t *bn, int which);
+int     bn_bit_length(const bn_t *bn);
 wnaf_t *bn_wnaf(const bn_t *bn, int w);
 wnaf_t *bn_bnaf(const bn_t *bn);