X-Git-Url: https://git.cryptolib.org/?a=blobdiff_plain;f=bigint%2Fbigint.c;h=307b1e403b29ed53c1a4312563f2c5923dfc3d8a;hb=6095187b080b960d111a54f18a3b2da788d2d59d;hp=c133faae826a538325d101f25d6fcdabd3f0e02d;hpb=8fa939d627fb6230610a38e6468cbc55d006216d;p=arm-crypto-lib.git diff --git a/bigint/bigint.c b/bigint/bigint.c index c133faa..307b1e4 100644 --- a/bigint/bigint.c +++ b/bigint/bigint.c @@ -1,6 +1,6 @@ /* bigint.c */ /* - This file is part of the AVR-Crypto-Lib. + This file is part of the ARM-Crypto-Lib. Copyright (C) 2008 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -81,6 +81,53 @@ void bigint_adjust(bigint_t* a){ /******************************************************************************/ +uint16_t bigint_length_b(bigint_t* a){ + if(!a->length_B || a->length_B==0){ + return 0; + } + return (a->length_B-1) * BIGINT_WORD_SIZE + GET_FBS(a); +} + +/******************************************************************************/ + +uint16_t bigint_length_B(bigint_t* a){ + return a->length_B * sizeof(bigint_word_t); +} + +/******************************************************************************/ + +uint32_t bigint_get_first_set_bit(bigint_t* a){ + if(a->length_B==0){ + return (uint32_t)(-1); + } + return (a->length_B-1)*sizeof(bigint_word_t)*8+GET_FBS(a); +} + + +/******************************************************************************/ + +uint32_t bigint_get_last_set_bit(bigint_t* a){ + uint32_t r=0; + uint8_t b=0; + bigint_word_t x=1; + if(a->length_B==0){ + return (uint32_t)(-1); + } + while(a->wordv[r]==0 && rlength_B){ + ++r; + } + if(a->wordv[r] == 0){ + return (uint32_t)(-1); + } + while((x&a->wordv[r])==0){ + ++b; + x <<= 1; + } + return r*BIGINT_WORD_SIZE+b; +} + +/******************************************************************************/ + void bigint_copy(bigint_t* dest, const bigint_t* src){ memcpy(dest->wordv, src->wordv, src->length_B*sizeof(bigint_word_t)); dest->length_B = src->length_B; @@ -381,7 +428,7 @@ void bigint_shiftright(bigint_t* a, uint16_t shift){ t |= ((bigint_wordplus_t)(a->wordv[0]))<<(BIGINT_WORD_SIZE-bitshift); a->wordv[0] = (bigint_word_t)(t>>BIGINT_WORD_SIZE); } - a->length_B -= ((shift/8)+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); + a->length_B -= ((shift/8)+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); bigint_adjust(a); } @@ -574,12 +621,6 @@ void bigint_square(bigint_t* dest, const bigint_t* a){ } /******************************************************************************/ - -#define cli_putstr(a) -#define bigint_print_hex(a) -#define cli_hexdump_rev(a,b) -#define uart_flush(a) - void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){ bigint_t tmp; bigint_word_t tmp_b[b->length_B+4]; @@ -595,7 +636,7 @@ void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){ tmp.wordv = tmp_b; bigint_copy(&tmp, b); bigint_shiftleft(&tmp, bitscale&(BIGINT_WORD_SIZE-1)); - cli_putstr("\r\nDBG(sub_ub.0) tmp_shift = "); bigint_print_hex(&tmp); +// cli_putstr("\r\nDBG(sub_ub.0) tmp_shift = "); bigint_print_hex(&tmp); for(j=0,i=word_shift; iwordv[i]; t -= tmp.wordv[j]; @@ -609,12 +650,18 @@ 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("\r\nDBG: *boom*\r\n"); + // char str[16]; + cli_putstr("\r\nDBG: *boom* a->length_B = "); + cli_hexdump_rev(&a->length_B, 2); + cli_putstr(" b->length_B = "); + cli_hexdump_rev(&b->length_B, 2); + cli_putstr(" bitscale = "); + cli_hexdump_rev(&bitscale, 2); bigint_set_zero(a); return; } a->wordv[i] -= borrow; - if(a->wordv[i]!=0xff){ + if(a->wordv[i] != (1LL<length_B,r->length_B*2)], res_b[r->length_B*2]; uint16_t i; uint8_t j; +// uint16_t *xaddr = &i; +// cli_putstr("\r\npre-alloc ("); +// cli_hexdump_rev(&xaddr, 4); +// cli_putstr(") ..."); res.wordv = res_b; base.wordv = base_b; bigint_copy(&base, a); +// cli_putstr("\r\npost-copy"); bigint_reduce(&base, r); res.wordv[0]=1; res.length_B=1; res.info = 0; +// cli_putstr("\r\nadjust "); bigint_adjust(&res); +// cli_putstr("\r\nexpmod "); for(i=0; i+1length_B; ++i){ t=exp->wordv[i]; for(j=0; jwordv[i]; + +// cli_putc('+'); while(t){ if(t&1){ bigint_mul_u(&res, &res, &base); @@ -713,13 +781,48 @@ void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, con } /******************************************************************************/ + +#define cli_putstr(a) +#define bigint_print_hex(a) +#define cli_hexdump_rev(a,b) +#define uart_flush(a) + /* 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){ bigint_t g, x_, y_, u, v, a_, b_, c_, d_; - volatile uint16_t i=0; + uint16_t i=0; if(x->length_B==0 || y->length_B==0){ return; } + if(x->length_B==1 && x->wordv[0]==1){ + gcd->length_B = 1; + gcd->wordv[0] = 1; + if(a){ + a->length_B = 1; + a->wordv[0] = 1; + SET_POS(a); + bigint_adjust(a); + } + if(b){ + bigint_set_zero(b); + } + return; + } + if(y->length_B==1 && y->wordv[0]==1){ + gcd->length_B = 1; + gcd->wordv[0] = 1; + if(b){ + b->length_B = 1; + b->wordv[0] = 1; + SET_POS(b); + bigint_adjust(b); + } + if(a){ + bigint_set_zero(a); + } + return; + } + while(x->wordv[i]==0 && y->wordv[i]==0){ ++i; } @@ -731,7 +834,7 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c g.wordv = g_b; x_.wordv = x_b; y_.wordv = y_b; - memset(g_b, 0, i); + memset(g_b, 0, i*sizeof(bigint_word_t)); g_b[i]=1; g.length_B = i+1; g.info=0; @@ -751,6 +854,7 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c bigint_shiftright(&x_, i); bigint_shiftright(&y_, i); } + u.wordv = u_b; v.wordv = v_b; a_.wordv = a_b; @@ -769,7 +873,9 @@ 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{ + cli_putstr("\r\nDBG (gcdext) 0"); while((u.wordv[0]&1)==0){ + cli_putstr("\r\nDBG (gcdext) 0.1"); bigint_shiftright(&u, 1); if((a_.wordv[0]&1) || (b_.wordv[0]&1)){ bigint_add_s(&a_, &a_, &y_); @@ -779,6 +885,7 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c bigint_shiftright(&b_, 1); } while((v.wordv[0]&1)==0){ + cli_putstr("\r\nDBG (gcdext) 0.2"); bigint_shiftright(&v, 1); if((c_.wordv[0]&1) || (d_.wordv[0]&1)){ bigint_add_s(&c_, &c_, &y_);