X-Git-Url: https://git.cryptolib.org/?a=blobdiff_plain;f=bigint%2Fbigint.c;h=3e2f0eb295241651d679faa9f04f3df723db01d1;hb=0ce5b31e9772c15cd1514e371a59f04e3a888111;hp=7dd841b22a867c79be8d47c0e2983163dcf5ffad;hpb=ca25e57ca6a74d6e26cad823d45fcc4604689fa1;p=avr-crypto-lib.git

diff --git a/bigint/bigint.c b/bigint/bigint.c
index 7dd841b..3e2f0eb 100644
--- a/bigint/bigint.c
+++ b/bigint/bigint.c
@@ -26,12 +26,16 @@
  */
  
 
+#define STRING2(x) #x
+#define STRING(x) STRING2(x)
+#define STR_LINE STRING(__LINE__)
+
 #include "bigint.h"
 #include <string.h>
-
-#include "bigint_io.h"
+/*
 #include "cli.h"
-
+#include "bigint_io.h"
+*/
 #ifndef MAX
  #define MAX(a,b) (((a)>(b))?(a):(b))
 #endif
@@ -73,15 +77,14 @@ void bigint_adjust(bigint_t* a){
 /******************************************************************************/
 
 void bigint_copy(bigint_t* dest, const bigint_t* src){
-	memcpy(dest->wordv, src->wordv, src->length_B);
 	dest->length_B = src->length_B;
 	dest->info = src->info;
+	memcpy(dest->wordv, src->wordv, src->length_B);
 }
 
 /******************************************************************************/
 
 /* this should be implemented in assembly */
-/*
 void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 	uint16_t t=0, i;
 	if(a->length_B < b->length_B){
@@ -101,7 +104,7 @@ void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 	dest->length_B = i;
 	bigint_adjust(dest);
 }
-*/
+
 /******************************************************************************/
 
 /* this should be implemented in assembly */
@@ -391,6 +394,10 @@ void bigint_set_zero(bigint_t* a){
 /* using the Karatsuba-Algorithm */
 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
 void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
+	if(a->length_B==0 || b->length_B==0){
+		bigint_set_zero(dest);
+		return;
+	}
 	if(dest==a || dest==b){
 		bigint_t d;
 		uint8_t d_b[a->length_B+b->length_B];
@@ -399,10 +406,6 @@ void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 		bigint_copy(dest, &d);
 		return;
 	}
-	if(a->length_B==0 || b->length_B==0){
-		bigint_set_zero(dest);
-		return;
-	}
 	if(a->length_B==1 || b->length_B==1){
 		if(a->length_B!=1){
 			XCHG_PTR(a,b);
@@ -559,7 +562,6 @@ void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
 	int16_t t;
 
 	if(a->length_B < b->length_B+byteshift){
-		cli_putstr_P(PSTR("\r\nERROR: bigint_sub_u_bitscale result negative"));
 		bigint_set_zero(a);
 		return;
 	}
@@ -579,8 +581,6 @@ void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
 	}
 	while(borrow){
 		if(i+1 > a->length_B){
-			cli_putstr_P(PSTR("\r\nERROR: bigint_sub_u_bitscale result negative (2) shift="));
-			cli_hexdump_rev(&bitscale, 2);
 			bigint_set_zero(a);
 			return;
 		}
@@ -596,30 +596,21 @@ void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
 /******************************************************************************/
 
 void bigint_reduce(bigint_t* a, const bigint_t* r){
+//	bigint_adjust(r);
 	uint8_t rfbs = GET_FBS(r);
-/*
-	cli_putstr_P(PSTR("\r\nreduce "));
-	bigint_print_hex(a);
-	cli_putstr_P(PSTR(" % "));
-	bigint_print_hex(r);
-	cli_putstr_P(PSTR("\r\n"));
-*/
 
-	if(r->length_B==0){
+	if(r->length_B==0 || a->length_B==0){
 		return;
 	}
 	while(a->length_B > r->length_B){
 		bigint_sub_u_bitscale(a, r, (a->length_B-r->length_B)*8+GET_FBS(a)-rfbs-1);
 	}
-
 	while((GET_FBS(a) > rfbs+1) && (a->length_B == r->length_B)){
 		bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1);
 	}
-
 	while(bigint_cmp_u(a,r)>=0){
 		bigint_sub_u(a,a,r);
 	}
-	bigint_adjust(a);
 }
 
 /******************************************************************************/
@@ -627,52 +618,48 @@ void bigint_reduce(bigint_t* a, const bigint_t* r){
 /* calculate dest = a**exp % r */
 /* using square&multiply */
 void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
-	bigint_t tmp, tmp2, x;
-	uint8_t x_b[MAX(r->length_B, a->length_B)], tmp_b[r->length_B*2], tmp2_b[r->length_B*2];
-	int16_t i;
-	uint8_t j;
-	x.wordv = x_b;
-	tmp.wordv = tmp_b;
-	tmp2.wordv = tmp2_b;
-	bigint_copy(&x, a);
-	bigint_reduce(&x, r);
-	bigint_copy(&tmp, &x);
-	if(a->length_B==0 || exp->length_B==0 || r->length_B==0){
+	if(a->length_B==0 || r->length_B==0){
 		return;
 	}
-	i=exp->length_B-1;
-	if(exp->wordv[i]!=1){
-		for(j=1<<(GET_FBS(exp)-1); j>0; j>>=1){
-	//		cli_putc('Q');
-			bigint_square(&tmp2, &tmp);
-			bigint_reduce(&tmp2, r);
-			if(exp->wordv[i]&j){
-	//			cli_putc('M');
-				bigint_mul_u(&tmp, &tmp2, &x);
-				bigint_reduce(&tmp, r);
-			}else{
-				bigint_copy(&tmp, &tmp2);
+
+	bigint_t res, base;
+	uint8_t base_b[MAX(a->length_B,r->length_B*2)], res_b[r->length_B*2];
+	uint16_t i;
+	uint8_t j, t;
+	res.wordv = res_b;
+	base.wordv = base_b;
+	bigint_copy(&base, a);
+	bigint_reduce(&base, r);
+	res.wordv[0]=1;
+	res.length_B=1;
+	res.info = 0;
+	bigint_adjust(&res);
+	for(i=0; i+1<exp->length_B; ++i){
+		t=exp->wordv[i];
+		for(j=0; j<8; ++j){
+			if(t&1){
+				bigint_mul_u(&res, &res, &base);
+				bigint_reduce(&res, r);
 			}
+			bigint_square(&base, &base);
+			bigint_reduce(&base, r);
+			t>>=1;
 		}
 	}
-	for(--i; i>=0; --i){
-		for(j=0x80; j>0; j>>=1){
-//			cli_putc('q');
-			bigint_square(&tmp2, &tmp);
-			bigint_reduce(&tmp2, r);
-			if(exp->wordv[i]&j){
-//				cli_putc('m');
-				bigint_mul_u(&tmp, &tmp2, &x);
-				bigint_reduce(&tmp, r);
-			}else{
-				bigint_copy(&tmp, &tmp2);
-			}
+	t=exp->wordv[i];
+	while(t){
+		if(t&1){
+			bigint_mul_u(&res, &res, &base);
+			bigint_reduce(&res, r);
 		}
+		bigint_square(&base, &base);
+		bigint_reduce(&base, r);
+		t>>=1;
 	}
-//	cli_putstr_P(PSTR("\r\n"));
-	bigint_copy(dest, &tmp);
+	SET_POS(&res);
+	bigint_copy(dest, &res);
 }
-#define DEBUG 0
+
 /******************************************************************************/
 /* gcd <-- gcd(x,y) a*x+b*y=gcd */
 void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){
@@ -704,31 +691,13 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 	 for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
 	 }
 
-#if DEBUG
-	 cli_putstr_P(PSTR("\r\nDBG: initshift = "));
-	 cli_hexdump_rev(&i, 2);
-#endif
 	 bigint_adjust(&x_);
 	 bigint_adjust(&y_);
 
 	 if(i){
 		 bigint_shiftleft(&g, i);
-#if DEBUG
-	 cli_putstr_P(PSTR("\r\nDBG: initshift (2) = "));
-	 cli_hexdump_rev(&i, 2);
-	 cli_putstr_P(PSTR("\r\n x' = "));
-		bigint_print_hex(&x_);
-		cli_putstr_P(PSTR("\r\n y' = "));
-		bigint_print_hex(&y_);
-#endif
-		bigint_shiftright(&x_, i);
-		bigint_shiftright(&y_, i);
-#if DEBUG
-		cli_putstr_P(PSTR("\r\n x' = "));
-		bigint_print_hex(&x_);
-		cli_putstr_P(PSTR("\r\n y' = "));
-		bigint_print_hex(&y_);
-#endif
+		 bigint_shiftright(&x_, i);
+		 bigint_shiftright(&y_, i);
 	 }
 	 u.wordv = u_b;
 	 v.wordv = v_b;
@@ -748,18 +717,6 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 	 bigint_set_zero(&b_);
 	 bigint_set_zero(&c_);
 	 do{
-#if DEBUG
-		 cli_putstr_P(PSTR("\r\n while u%2==0; u = "));
-		 bigint_print_hex(&u);
-		 cli_putstr_P(PSTR("\r\nDBG: (10) a = "));
-		 bigint_print_hex(&a_);
-		 cli_putstr_P(PSTR("\r\nDBG: (10) b = "));
-		 bigint_print_hex(&b_);
-		 cli_putstr_P(PSTR("\r\nDBG: (10) c = "));
-		 bigint_print_hex(&c_);
-		 cli_putstr_P(PSTR("\r\nDBG: (10) d = "));
-		 bigint_print_hex(&d_);
-#endif
 		 while((u.wordv[0]&1)==0){
 			 bigint_shiftright(&u, 1);
 			 if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
@@ -769,18 +726,6 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 			 bigint_shiftright(&a_, 1);
 			 bigint_shiftright(&b_, 1);
 		 }
-#if DEBUG
-		 cli_putstr_P(PSTR("\r\n while v%2==0; v = "));
-		 bigint_print_hex(&v);
-		 cli_putstr_P(PSTR("\r\nDBG: (20) a = "));
-		 bigint_print_hex(&a_);
-		 cli_putstr_P(PSTR("\r\nDBG: (20) b = "));
-		 bigint_print_hex(&b_);
-		 cli_putstr_P(PSTR("\r\nDBG: (20) c = "));
-		 bigint_print_hex(&c_);
-		 cli_putstr_P(PSTR("\r\nDBG: (20) d = "));
-		 bigint_print_hex(&d_);
-#endif
 		 while((v.wordv[0]&1)==0){
 			 bigint_shiftright(&v, 1);
 			 if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
@@ -791,17 +736,6 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 			 bigint_shiftright(&d_, 1);
 
 		 }
-#if DEBUG
-		 cli_putstr_P(PSTR("\r\n if u>=v ..."));
-		 cli_putstr_P(PSTR("\r\nDBG: (30) a = "));
-		 bigint_print_hex(&a_);
-		 cli_putstr_P(PSTR("\r\nDBG: (30) b = "));
-		 bigint_print_hex(&b_);
-		 cli_putstr_P(PSTR("\r\nDBG: (30) c = "));
-		 bigint_print_hex(&c_);
-		 cli_putstr_P(PSTR("\r\nDBG: (30) d = "));
-		 bigint_print_hex(&d_);
-#endif
 		 if(bigint_cmp_u(&u, &v)>=0){
 			bigint_sub_u(&u, &u, &v);
 			bigint_sub_s(&a_, &a_, &c_);
@@ -811,26 +745,6 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 			bigint_sub_s(&c_, &c_, &a_);
 			bigint_sub_s(&d_, &d_, &b_);
 		 }
-#if DEBUG
-		 if(GET_SIGN(&u)){
-			 cli_putstr_P(PSTR("\r\nDBG: u negative! u = "));
-			 bigint_print_hex(&u);
-		 }
-		 if(GET_SIGN(&v)){
-			 cli_putstr_P(PSTR("\r\nDBG: v negative! v = "));
-			 bigint_print_hex(&v);
-		 }
-#endif
-/*
-		 cli_putstr_P(PSTR("\r\nDBG: (2) a = "));
-		 bigint_print_hex(&a_);
-		 cli_putstr_P(PSTR("\r\nDBG: (2) b = "));
-		 bigint_print_hex(&b_);
-		 cli_putstr_P(PSTR("\r\nDBG: (2) c = "));
-		 bigint_print_hex(&c_);
-		 cli_putstr_P(PSTR("\r\nDBG: (2) d = "));
-		 bigint_print_hex(&d_);
-*/
 	 }while(u.length_B);
 	 if(gcd){
 		 bigint_mul_s(gcd, &v, &g);
@@ -845,14 +759,28 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 
 /******************************************************************************/
 
-void bigint_inverse(bigint_t* dest, bigint_t* a, bigint_t* m){
+void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
 	bigint_gcdext(NULL, dest, NULL, a, m);
 	while(dest->info&BIGINT_NEG_MASK){
 		bigint_add_s(dest, dest, m);
 	}
 }
 
+/******************************************************************************/
+
+void bigint_changeendianess(bigint_t* a){
+	uint8_t t, *p, *q;
+	p = a->wordv;
+	q = p+a->length_B-1;
+	while(p<q){
+		t = *p;
+		*p = *q;
+		*q = t;
+		++p; --q;
+	}
+}
 
+/******************************************************************************/