X-Git-Url: https://git.cryptolib.org/?a=blobdiff_plain;f=bigint%2Fbigint.c;h=0ff6338031c7100f8b6ca8880eb152a514876821;hb=62d7d4d281af70bc2f56fb3baa86a6915e126240;hp=f57d285fc0ae7f2d65cf60f3115a73ff74fced57;hpb=96e930bbd293d62d8a9d2b011eb958aee6840c42;p=avr-crypto-lib.git diff --git a/bigint/bigint.c b/bigint/bigint.c index f57d285..0ff6338 100644 --- a/bigint/bigint.c +++ b/bigint/bigint.c @@ -26,9 +26,16 @@ */ +#define STRING2(x) #x +#define STRING(x) STRING2(x) +#define STR_LINE STRING(__LINE__) + #include "bigint.h" #include - +/* +#include "cli.h" +#include "bigint_io.h" +*/ #ifndef MAX #define MAX(a,b) (((a)>(b))?(a):(b)) #endif @@ -78,7 +85,6 @@ void bigint_copy(bigint_t* dest, const bigint_t* src){ /******************************************************************************/ /* 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){ @@ -98,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 */ @@ -388,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]; @@ -396,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); @@ -575,7 +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_hexdump_rev(&bitscale, 2); bigint_set_zero(a); return; } @@ -591,19 +596,18 @@ 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); - 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); } @@ -615,45 +619,46 @@ 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){ - bigint_square(&tmp2, &tmp); - bigint_reduce(&tmp2, r); - if(exp->wordv[i]&j){ - 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+1length_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){ - bigint_square(&tmp2, &tmp); - bigint_reduce(&tmp2, r); - if(exp->wordv[i]&j){ - 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; } - bigint_copy(dest, &tmp); + SET_POS(&res); + bigint_copy(dest, &res); } /******************************************************************************/ @@ -755,14 +760,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