X-Git-Url: https://git.cryptolib.org/?a=blobdiff_plain;f=bigint%2Fbigint.c;h=a7a2b597feadeebadb5979efd76d38bea279717d;hb=73f474e8fea34667e788ff4ec24de552e9d1d9e8;hp=c133faae826a538325d101f25d6fcdabd3f0e02d;hpb=8fa939d627fb6230610a38e6468cbc55d006216d;p=arm-crypto-lib.git diff --git a/bigint/bigint.c b/bigint/bigint.c index c133faa..a7a2b59 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 @@ -33,11 +33,10 @@ #include "bigint.h" #include -#define DEBUG 1 +#define DEBUG 0 #if DEBUG #include "cli.h" -#include "uart_lowlevel.h" #include "bigint_io.h" #endif @@ -54,9 +53,9 @@ #define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK #define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK #define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0) -#define XCHG_PTR(a,b) do{ a = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b))); \ - b = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b))); \ - a = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b)));}while(0) +#define XCHG_PTR(a,b) do{ a = (void*)(((bigint_ptr_int_t)(a)) ^ ((bigint_ptr_int_t)(b))); \ + b = (void*)(((bigint_ptr_int_t)(a)) ^ ((bigint_ptr_int_t)(b))); \ + a = (void*)(((bigint_ptr_int_t)(a)) ^ ((bigint_ptr_int_t)(b)));}while(0) #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK) @@ -72,7 +71,7 @@ void bigint_adjust(bigint_t* a){ bigint_word_t t; uint8_t i = BIGINT_WORD_SIZE-1; t = a->wordv[a->length_B-1]; - while((t&(1<<(BIGINT_WORD_SIZE-1)))==0 && i){ + while((t&(1L<<(BIGINT_WORD_SIZE-1)))==0 && i){ t<<=1; i--; } @@ -81,6 +80,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; @@ -108,7 +154,9 @@ void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ dest->wordv[i] = (bigint_word_t)t; t>>=BIGINT_WORD_SIZE; } - dest->wordv[i++] = (bigint_word_t)t; + if(t){ + dest->wordv[i++] = (bigint_word_t)t; + } dest->length_B = i; bigint_adjust(dest); } @@ -117,9 +165,56 @@ void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ /* this should be implemented in assembly */ void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){ - uint16_t i,j=0; + if(a->length_B == 0){ + return; + } + if(scale == 0){ + bigint_add_u(dest, dest, a); + return; + } + bigint_t x; +#if BIGINT_WORD_SIZE == 8 + memset(dest->wordv + dest->length_B, 0, MAX(dest->length_B, a->length_B + scale) - dest->length_B); + x.wordv = dest->wordv + scale; + x.length_B = dest->length_B - scale; + if((int16_t)x.length_B < 0){ + x.length_B = 0; + x.info = 0; + } else { + x.info = dest->info; + } + bigint_add_u(&x, &x, a); + dest->length_B = x.length_B + scale; + dest->info = 0; + bigint_adjust(dest); +#else + bigint_t s; + uint16_t word_shift = scale / sizeof(bigint_word_t), byte_shift = scale % sizeof(bigint_word_t); + bigint_word_t bv[a->length_B + 1]; + s.wordv = bv; + bv[0] = bv[a->length_B] = 0; + memcpy((uint8_t*)bv + byte_shift, a->wordv, a->length_B * sizeof(bigint_word_t)); + s.length_B = a->length_B + 1; + bigint_adjust(&s); + memset(dest->wordv + dest->length_B, 0, (MAX(dest->length_B, s.length_B + word_shift) - dest->length_B) * sizeof(bigint_word_t)); + x.wordv = dest->wordv + word_shift; + x.length_B = dest->length_B - word_shift; + if((int16_t)x.length_B < 0){ + x.length_B = 0; + x.info = 0; + }else{ + x.info = dest->info; + } + bigint_add_u(&x, &x, &s); + dest->length_B = x.length_B + word_shift; + dest->info = 0; + bigint_adjust(dest); +#endif + + +/* uint16_t i,j=0; uint16_t scale_w; - uint32_t *dst; + bigint_word_t *dst; bigint_wordplus_t t=0; scale_w = (scale+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); if(scale>dest->length_B*sizeof(bigint_word_t)){ @@ -147,6 +242,7 @@ void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){ dest->length_B = i; } bigint_adjust(dest); + */ } /******************************************************************************/ @@ -177,34 +273,24 @@ void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ if(r<0){ bigint_sub_u(dest, b, a); SET_NEG(dest); - }else{ - for(i=0; iwordv[i]; + return; + } + for(i=0; iwordv[i]; + if(iwordv[i]; - t -= borrow; - if(t<0){ - borrow = 1; - dest->wordv[i]=(bigint_word_t)t; - }else{ - borrow = 0; - dest->wordv[i]=(bigint_word_t)t; - } } - for(;iwordv[i] - borrow; - if(t<0){ - borrow = 1; - dest->wordv[i]=(bigint_word_t)t; - }else{ - borrow = 0; - dest->wordv[i]=(bigint_word_t)t; - } - + t -= borrow; + dest->wordv[i]=(bigint_word_t)t; + if(t<0){ + borrow = 1; + }else{ + borrow = 0; } - SET_POS(dest); - dest->length_B = i; - bigint_adjust(dest); } + SET_POS(dest); + dest->length_B = i; + bigint_adjust(dest); } /******************************************************************************/ @@ -222,8 +308,8 @@ int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){ uint16_t i; i = a->length_B-1; do{ - if(a->wordv[i]!=b->wordv[i]){ - if(a->wordv[i]>b->wordv[i]){ + if(a->wordv[i] != b->wordv[i]){ + if(a->wordv[i] > b->wordv[i]){ return 1; }else{ return -1; @@ -381,7 +467,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); } @@ -422,78 +508,80 @@ void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ if(a->length_B!=1){ XCHG_PTR(a,b); } - bigint_wordplus_t i, t=0; + bigint_wordplus_t t=0; + uint16_t i; bigint_word_t x = a->wordv[0]; - for(i=0; ilength_B; ++i){ + for(i=0; i < b->length_B; ++i){ t += ((bigint_wordplus_t)b->wordv[i])*((bigint_wordplus_t)x); dest->wordv[i] = (bigint_word_t)t; t>>=BIGINT_WORD_SIZE; } dest->wordv[i] = (bigint_word_t)t; - dest->length_B=i+1; + dest->length_B = i+1; + dest->info = 0; bigint_adjust(dest); return; } - if(a->length_B<=4/sizeof(bigint_word_t) && b->length_B<=4/sizeof(bigint_word_t)){ + if(a->length_B * sizeof(bigint_word_t) <= 4 && b->length_B * sizeof(bigint_word_t) <= 4){ uint32_t p=0, q=0; uint64_t r; memcpy(&p, a->wordv, a->length_B*sizeof(bigint_word_t)); memcpy(&q, b->wordv, b->length_B*sizeof(bigint_word_t)); - r = (uint64_t)p*(uint64_t)q; - memcpy(dest->wordv, &r, (a->length_B+b->length_B)*sizeof(bigint_word_t)); - dest->length_B = a->length_B+b->length_B; + r = (uint64_t)p * (uint64_t)q; + memcpy(dest->wordv, &r, (dest->length_B = a->length_B + b->length_B)*sizeof(bigint_word_t)); bigint_adjust(dest); return; } bigint_set_zero(dest); /* split a in xh & xl; split b in yh & yl */ - uint16_t n; - n=(MAX(a->length_B, b->length_B)+1)/2; + const uint16_t n = (MAX(a->length_B, b->length_B)+1)/2; bigint_t xl, xh, yl, yh; xl.wordv = a->wordv; yl.wordv = b->wordv; if(a->length_B<=n){ - xh.info=0; - xh.length_B = 0; + bigint_set_zero(&xh); xl.length_B = a->length_B; - xl.info = 0; + xl.info = a->info; }else{ xl.length_B=n; xl.info = 0; bigint_adjust(&xl); - xh.wordv = a->wordv+n; + xh.wordv = &(a->wordv[n]); xh.length_B = a->length_B-n; - xh.info = 0; + xh.info = a->info; } if(b->length_B<=n){ - yh.info=0; - yh.length_B = 0; + bigint_set_zero(&yh); yl.length_B = b->length_B; yl.info = b->info; }else{ yl.length_B=n; yl.info = 0; bigint_adjust(&yl); - yh.wordv = b->wordv+n; + yh.wordv = &(b->wordv[n]); yh.length_B = b->length_B-n; - yh.info = 0; + yh.info = b->info; } /* now we have split up a and b */ + /* remember we want to do: + * x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl + * 5 9 2 4 3 7 5 6 1 8 1 + */ bigint_word_t tmp_b[2*n+2], m_b[2*(n+1)]; bigint_t tmp, tmp2, m; tmp.wordv = tmp_b; - tmp2.wordv = tmp_b+n+1; + tmp2.wordv = &(tmp_b[n+1]); m.wordv = m_b; - bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */ - bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */ - bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */ - bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp2*tmp */ - bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */ - bigint_sub_u(&m, &m, dest); /* m <= m-dest */ - bigint_sub_u(&m, &m, &tmp); /* m <= m-h */ - bigint_add_scale_u(dest, &m, n*sizeof(bigint_word_t)); - bigint_add_scale_u(dest, &tmp, 2*n*sizeof(bigint_word_t)); + bigint_mul_u(dest, &xl, &yl); /* 1: dest <= xl*yl */ + bigint_add_u(&tmp2, &xh, &xl); /* 2: tmp2 <= xh+xl */ + bigint_add_u(&tmp, &yh, &yl); /* 3: tmp <= yh+yl */ + bigint_mul_u(&m, &tmp2, &tmp); /* 4: m <= tmp2*tmp */ + bigint_mul_u(&tmp, &xh, &yh); /* 5: h <= xh*yh */ + bigint_sub_u(&m, &m, dest); /* 6: m <= m-dest */ + bigint_sub_u(&m, &m, &tmp); /* 7: m <= m-h */ + bigint_add_scale_u(dest, &m, n*sizeof(bigint_word_t)); /* 8: dest <= dest+m**n*/ + bigint_add_scale_u(dest, &tmp, 2*n*sizeof(bigint_word_t)); /* 9: dest <= dest+tmp**(2*n) */ } /******************************************************************************/ @@ -553,9 +641,15 @@ void bigint_square(bigint_t* dest, const bigint_t* a){ bigint_word_t buffer[2*n+1]; xl.wordv = a->wordv; xl.length_B = n; + xl.info = 0; xh.wordv = &(a->wordv[n]); xh.length_B = a->length_B-n; + xh.info = 0; + bigint_adjust(&xl); + bigint_adjust(&xh); tmp.wordv = buffer; +/* (xh * b**n + xl)**2 = xh**2 * b**2n + 2 * xh * xl * b**n + xl**2 */ + // cli_putstr("\r\nDBG (a): xl: "); bigint_print_hex(&xl); // cli_putstr("\r\nDBG (b): xh: "); bigint_print_hex(&xh); bigint_square(dest, &xl); @@ -574,61 +668,39 @@ 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]; - uint16_t i,j,word_shift=bitscale/(8*sizeof(bigint_word_t)); - uint8_t borrow=0; - bigint_wordplus_signed_t t; + bigint_t tmp, x; + bigint_word_t tmp_b[b->length_B + 1]; + const uint16_t word_shift = bitscale / BIGINT_WORD_SIZE; - if(a->length_B < b->length_B+word_shift){ + if(a->length_B < b->length_B + word_shift){ +#if DEBUG cli_putstr("\r\nDBG: *bang*\r\n"); +#endif bigint_set_zero(a); return; } 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); - for(j=0,i=word_shift; iwordv[i]; - t -= tmp.wordv[j]; - t -= borrow; - a->wordv[i] = (bigint_word_t)t; - if(t<0){ - borrow = 1; - }else{ - borrow = 0; - } - } - while(borrow){ - if(i+1 > a->length_B){ - cli_putstr("\r\nDBG: *boom*\r\n"); - bigint_set_zero(a); - return; - } - a->wordv[i] -= borrow; - if(a->wordv[i]!=0xff){ - borrow=0; - } - ++i; - } + bigint_shiftleft(&tmp, bitscale % BIGINT_WORD_SIZE); + + x.info = a->info; + x.wordv = &(a->wordv[word_shift]); + x.length_B = a->length_B - word_shift; + + bigint_sub_u(&x, &x, &tmp); bigint_adjust(a); + return; } /******************************************************************************/ void bigint_reduce(bigint_t* a, const bigint_t* r){ -// bigint_adjust(r); +// bigint_adjust((bigint_t*)r); uint8_t rfbs = GET_FBS(r); - +#if DEBUG cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a); +#endif if(r->length_B==0 || a->length_B==0){ return; } @@ -639,30 +711,42 @@ void bigint_reduce(bigint_t* a, const bigint_t* r){ p %= q; memcpy(a->wordv, &p, a->length_B*sizeof(bigint_word_t)); bigint_adjust(a); - cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a); +// cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a); return; } uint16_t shift; while(a->length_B > r->length_B){ - shift = (a->length_B-r->length_B)*8*sizeof(bigint_word_t)+GET_FBS(a)-rfbs-1; - cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 2); - uart_flush(0); + shift = (a->length_B - r->length_B) * 8 * sizeof(bigint_word_t) + GET_FBS(a) - rfbs - 1; + /* + if((a->wordv[a->length_B-1] & ((1LL< r->wordv[r->length_B-1]){ + // cli_putc('~'); + cli_putstr("\r\n ~ [a] = "); + cli_hexdump_rev(&a->wordv[a->length_B-1], 4); + cli_putstr(" [r] = "); + cli_hexdump_rev(&r->wordv[r->length_B-1], 4); + shift += 1; + } + */ +// cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 2); +// cli_putstr(" a_len = "); cli_hexdump_rev(&a->length_B, 2); +// cli_putstr(" r_len = "); cli_hexdump_rev(&r->length_B, 2); +// uart_flush(0); bigint_sub_u_bitscale(a, r, shift); - cli_putstr("\r\nDBG: (1) = "); bigint_print_hex(a); +// cli_putstr("\r\nDBG: (1) = "); bigint_print_hex(a); } - while((GET_FBS(a) > rfbs+1) && (a->length_B == r->length_B)){ + while((GET_FBS(a) > rfbs) && (a->length_B == r->length_B)){ shift = GET_FBS(a)-rfbs-1; - cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2); - bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1); - cli_putstr("\r\nDBG: (2) = "); bigint_print_hex(a); +// cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2); + bigint_sub_u_bitscale(a, r, shift); +// cli_putstr("\r\nDBG: (2) = "); bigint_print_hex(a); } while(bigint_cmp_u(a,r)>=0){ bigint_sub_u(a,a,r); - cli_putstr("\r\nDBG: (3) = "); bigint_print_hex(a); +// cli_putstr("\r\nDBG: (3) = "); bigint_print_hex(a); } bigint_adjust(a); - cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a); - cli_putstr("\r\n"); +// cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a); +// cli_putstr("\r\n"); } /******************************************************************************/ @@ -675,51 +759,96 @@ void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, con } bigint_t res, base; - bigint_word_t t, base_b[MAX(a->length_B,r->length_B*2)], res_b[r->length_B*2]; + bigint_word_t t, base_b[MAX(a->length_B,r->length_B)], 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; bigint_adjust(&res); - for(i=0; i+1length_B; ++i){ - t=exp->wordv[i]; - for(j=0; jlength_B == 0){ + bigint_copy(dest, &res); + return; + } + uint8_t flag = 0; + t=exp->wordv[exp->length_B - 1]; + for(i=exp->length_B; i > 0; --i){ + t = exp->wordv[i - 1]; + for(j=BIGINT_WORD_SIZE; j > 0; --j){ + if(!flag){ + if(t & (1<<(BIGINT_WORD_SIZE-1))){ + flag = 1; + } + } + if(flag){ + bigint_square(&res, &res); bigint_reduce(&res, r); + if(t & (1<<(BIGINT_WORD_SIZE-1))){ + bigint_mul_u(&res, &res, &base); + bigint_reduce(&res, r); + } } - bigint_square(&base, &base); - bigint_reduce(&base, r); - t>>=1; - } - } - t=exp->wordv[i]; - while(t){ - if(t&1){ - bigint_mul_u(&res, &res, &base); - bigint_reduce(&res, r); + t<<=1; } - bigint_square(&base, &base); - bigint_reduce(&base, r); - t>>=1; } + +// cli_putc('+'); SET_POS(&res); bigint_copy(dest, &res); } /******************************************************************************/ + +#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 +860,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 +880,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 +899,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 +911,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_);