+void bigint_mul_word_u(bigint_t *a, bigint_word_t b){
+ bigint_wordplus_t c0 = 0, c1 = 0;
+ bigint_length_t i;
+
+ if(b == 0){
+ bigint_set_zero(a);
+ return;
+ }
+
+ for(i = 0; i < a->length_W; ++i){
+ c1 = ((bigint_wordplus_t)(a->wordv[i])) * ((bigint_wordplus_t)b);
+ c1 += c0;
+ a->wordv[i] = (bigint_word_t)c1;
+ c0 = c1 >> BIGINT_WORD_SIZE;
+ }
+ if(c0){
+ a->wordv[a->length_W] = (bigint_word_t)c0;
+ a->length_W += 1;
+ }
+ bigint_adjust(a);
+}
+
+/******************************************************************************/
+
+void bigint_clip(bigint_t *dest, bigint_length_t length_W){
+ if(dest->length_W > length_W){
+ dest->length_W = length_W;
+ }
+ bigint_adjust(dest);
+}
+
+/******************************************************************************/
+/*
+ * m_ = m * m'[0]
+ * dest = (a * b) % m (?)
+ */
+
+void bigint_mont_mul(bigint_t *dest, const bigint_t *a, const bigint_t *b, const bigint_t *m, const bigint_t *m_){
+ const bigint_length_t s = MAX(MAX(a->length_W, b->length_W), m->length_W);
+ bigint_t u, t;
+
+ bigint_length_t i;
+
+ if (a->length_W == 0 || b->length_W == 0) {
+ bigint_set_zero(dest);
+ return;
+ }
+ ALLOC_BIGINT_WORDS(u_w, s + 2);
+ ALLOC_BIGINT_WORDS(t_w, s + 2);
+ u.wordv = u_w;
+ u.info = 0;
+ u.length_W = 0;
+ t.wordv = t_w;
+ for (i = 0; i < a->length_W; ++i) {
+ bigint_copy(&t, b);
+ bigint_mul_word_u(&t, a->wordv[i]);
+ bigint_add_u(&u, &u, &t);
+ bigint_copy(&t, m_);
+ if (u.length_W != 0) {
+ bigint_mul_word_u(&t, u.wordv[0]);
+ bigint_add_u(&u, &u, &t);
+ }
+ bigint_shiftright_1word(&u);
+ }
+ for (; i < s; ++i) {
+ bigint_copy(&t, m_);
+ if (u.length_W != 0) {
+ bigint_mul_word_u(&t, u.wordv[0]);
+ bigint_add_u(&u, &u, &t);
+ }
+ bigint_shiftright_1word(&u);
+ }
+ bigint_reduce(&u, m);
+ bigint_copy(dest, &u);
+ FREE(t_w);
+ FREE(u_w);
+}
+
+/******************************************************************************/
+
+void bigint_mont_red(bigint_t *dest, const bigint_t *a, const bigint_t *m, const bigint_t *m_){
+ bigint_t u, t;
+ bigint_length_t i, s = MAX(a->length_W, MAX(m->length_W, m_->length_W));
+
+ if (a->length_W == 0) {
+ bigint_set_zero(dest);
+ return;
+ }
+
+ ALLOC_BIGINT_WORDS(u_w, s + 2);
+ ALLOC_BIGINT_WORDS(t_w, s + 2);
+ t.wordv = t_w;
+ u.wordv = u_w;
+ bigint_copy(&u, a);
+ for (i = 0; i < m->length_W; ++i) {
+ bigint_copy(&t, m_);
+ if (u.length_W != 0) {
+ bigint_mul_word_u(&t, u.wordv[0]);
+ bigint_add_u(&u, &u, &t);
+ }
+ bigint_shiftright_1word(&u);
+ }
+ bigint_reduce(&u, m);
+ bigint_copy(dest, &u);
+ FREE(t_w);
+ FREE(u_w);
+}
+
+/******************************************************************************/
+/*
+ * m_ = m * (- m0^-1 (mod 2^W))
+ */
+void bigint_mont_gen_m_(bigint_t* dest, const bigint_t* m){
+ bigint_word_t x_w[2], m_w_0[1];
+ bigint_t x, m_0;
+ if (m->length_W == 0) {
+ bigint_set_zero(dest);
+ return;
+ }
+ if ((m->wordv[0] & 1) == 0) {
+#if DEBUG
+ printf_P(PSTR("ERROR: m must not be even, m = "));
+ bigint_print_hex(m);
+ putchar('\n');
+ uart0_flush();
+#endif
+ return;
+ }
+ x.wordv = x_w;
+ x.info = 0;
+ x.length_W = 2;
+ x_w[0] = 0;
+ x_w[1] = 1;
+ m_0.wordv = m_w_0;
+ m_0.info = 0;
+ m_0.length_W = 1;
+ m_0.wordv[0] = m->wordv[0];
+ bigint_adjust(&x);
+ bigint_adjust(&m_0);
+ bigint_inverse(dest, &m_0, &x);
+ bigint_sub_s(&x, &x, dest);
+ bigint_copy(dest, m);
+ bigint_mul_word_u(dest, x.wordv[0]);
+
+}
+
+/******************************************************************************/
+
+/*
+ * dest = a * R mod m
+ */
+void bigint_mont_trans(bigint_t *dest, const bigint_t *a, const bigint_t *m){
+ bigint_t t;
+
+ ALLOC_BIGINT_WORDS(t_w, a->length_W + m->length_W);
+ t.wordv = t_w;
+ memset(t_w, 0, m->length_W * sizeof(bigint_word_t));
+ memcpy(&t_w[m->length_W], a->wordv, a->length_W * sizeof(bigint_word_t));
+ t.info = a->info;
+ t.length_W = a->length_W + m->length_W;
+ bigint_reduce(&t, m);
+ bigint_copy(dest, &t);
+ FREE(t_w);
+}
+
+/******************************************************************************/
+
+/* calculate dest = a**exp % r */
+/* using square&multiply */
+void bigint_expmod_u_mont_accel(bigint_t *dest, const bigint_t *a, const bigint_t *exp, const bigint_t *r, const bigint_t *m_){
+ if(r->length_W == 0) {
+ return;
+ }
+
+ bigint_t res, ax;
+ bigint_word_t t;
+ bigint_length_t i;
+ uint8_t j;
+
+ if (exp->length_W == 0) {
+ dest->length_W = 1;
+ dest->info = 0;
+ dest->wordv[0] = 1;
+ return;
+ }
+
+ ALLOC_BIGINT_WORDS(res_w, r->length_W * 2);
+ ALLOC_BIGINT_WORDS(ax_w, MAX(r->length_W, a->length_W));
+
+ res.wordv = res_w;
+ ax.wordv = ax_w;
+
+ res.wordv[0] = 1;
+ res.length_W = 1;
+ res.info = 0;
+
+ bigint_copy(&ax, a);
+ bigint_reduce(&ax, r);
+
+ bigint_mont_trans(&ax, &ax, r);
+ bigint_mont_trans(&res, &res, r);
+
+ uint8_t flag = 0;
+ t = exp->wordv[exp->length_W - 1];
+ for (i = exp->length_W; i > 0; --i) {
+ t = exp->wordv[i - 1];
+ for(j = BIGINT_WORD_SIZE; j > 0; --j){
+ if (!flag) {
+ if(t & (((bigint_word_t)1) << (BIGINT_WORD_SIZE - 1))){
+ flag = 1;
+ }
+ }
+ if (flag) {
+ bigint_square(&res, &res);
+ bigint_mont_red(&res, &res, r, m_);
+ if (t & (((bigint_word_t)1) << (BIGINT_WORD_SIZE - 1))) {
+ bigint_mont_mul(&res, &res, &ax, r, m_);
+ }
+ }
+ t <<= 1;
+ }
+ }
+ SET_POS(&res);
+ bigint_mont_red(dest, &res, r, m_);
+ FREE(ax_w);
+ FREE(res_w);
+}