3 This file is part of the ARM-Crypto-Lib.
4 Copyright (C) 2008 Daniel Otte (daniel.otte@rub.de)
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
24 * \license GPLv3 or later
30 #define STRING(x) STRING2(x)
31 #define STR_LINE STRING(__LINE__)
40 #include "bigint_io.h"
44 #define MAX(a,b) (((a)>(b))?(a):(b))
48 #define MIN(a,b) (((a)<(b))?(a):(b))
51 #define SET_FBS(a, v) do{(a)->info &=~BIGINT_FBS_MASK; (a)->info |= (v);}while(0)
52 #define GET_FBS(a) ((a)->info&BIGINT_FBS_MASK)
53 #define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK
54 #define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK
55 #define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0)
56 #define XCHG_PTR(a,b) do{ a = (void*)(((intptr_t)(a)) ^ ((intptr_t)(b))); \
57 b = (void*)(((intptr_t)(a)) ^ ((intptr_t)(b))); \
58 a = (void*)(((intptr_t)(a)) ^ ((intptr_t)(b)));}while(0)
60 #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK)
62 /******************************************************************************/
63 void bigint_adjust(bigint_t* a){
64 while(a->length_W!=0 && a->wordv[a->length_W-1]==0){
72 uint8_t i = BIGINT_WORD_SIZE-1;
73 t = a->wordv[a->length_W-1];
74 while((t&(1L<<(BIGINT_WORD_SIZE-1)))==0 && i){
81 /******************************************************************************/
83 uint16_t bigint_length_b(const bigint_t* a){
84 if(!a->length_W || a->length_W==0){
87 return (a->length_W-1) * BIGINT_WORD_SIZE + GET_FBS(a);
90 /******************************************************************************/
92 uint16_t bigint_length_B(const bigint_t* a){
93 return a->length_W * sizeof(bigint_word_t);
96 /******************************************************************************/
98 uint32_t bigint_get_first_set_bit(const bigint_t* a){
100 return (uint32_t)(-1);
102 return (a->length_W-1)*sizeof(bigint_word_t)*8+GET_FBS(a);
106 /******************************************************************************/
108 uint32_t bigint_get_last_set_bit(const bigint_t* a){
113 return (uint32_t)(-1);
115 while(a->wordv[r]==0 && r<a->length_W){
118 if(a->wordv[r] == 0){
119 return (uint32_t)(-1);
121 while((x&a->wordv[r])==0){
125 return r*BIGINT_WORD_SIZE+b;
128 /******************************************************************************/
130 void bigint_copy(bigint_t* dest, const bigint_t* src){
131 memcpy(dest->wordv, src->wordv, src->length_W*sizeof(bigint_word_t));
132 dest->length_W = src->length_W;
133 dest->info = src->info;
136 /******************************************************************************/
138 /* this should be implemented in assembly */
139 void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
141 bigint_wordplus_t t = 0LL;
142 if(a->length_W < b->length_W){
145 for(i = 0; i < b->length_W; ++i){
148 dest->wordv[i] = (bigint_word_t)t;
149 t >>= BIGINT_WORD_SIZE;
151 for(; i < a->length_W; ++i){
153 dest->wordv[i] = (bigint_word_t)t;
154 t >>= BIGINT_WORD_SIZE;
157 dest->wordv[i++] = (bigint_word_t)t;
163 /******************************************************************************/
165 /* this should be implemented in assembly */
166 void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){
167 if(a->length_W == 0){
171 bigint_add_u(dest, dest, a);
175 cli_putstr_P(PSTR("\r\nDBG: bigint_add_scale("));
176 bigint_print_hex(dest);
178 bigint_print_hex(dest);
180 cli_hexdump_rev(&scale, 2);
183 #if BIGINT_WORD_SIZE == 8
184 if(scale >= dest->length_W){
186 cli_putstr_P(PSTR("\r\n\tpath one"));
188 memset(dest->wordv + dest->length_W, 0, scale - dest->length_W);
189 memcpy(dest->wordv + scale, a->wordv, a->length_W);
190 dest->info = a->info;
191 dest->length_W = a->length_W + scale;
196 cli_putstr_P(PSTR("\r\n\tpath two"));
198 x.length_W = dest->length_W - scale;
200 x.wordv = dest->wordv + scale;
201 bigint_add_u(&x, &x, a);
202 dest->length_W = x.length_W + scale;
207 uint16_t word_shift = scale / sizeof(bigint_word_t), byte_shift = scale % sizeof(bigint_word_t);
208 bigint_word_t bv[a->length_W + 1];
210 bv[0] = bv[a->length_W] = 0;
211 memcpy((uint8_t*)bv + byte_shift, a->wordv, a->length_W * sizeof(bigint_word_t));
212 s.length_W = a->length_W + 1;
214 memset(dest->wordv + dest->length_W, 0, (MAX(dest->length_W, s.length_W + word_shift) - dest->length_W) * sizeof(bigint_word_t));
215 x.wordv = dest->wordv + word_shift;
216 x.length_W = dest->length_W - word_shift;
217 if((int16_t)x.length_W < 0){
223 bigint_add_u(&x, &x, &s);
224 dest->length_W = x.length_W + word_shift;
233 bigint_wordplus_t t=0;
234 scale_w = (scale+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t);
235 if(scale>dest->length_W*sizeof(bigint_word_t)){
236 memset(((uint8_t*)dest->wordv)+dest->length_W*sizeof(bigint_word_t), 0, scale-dest->length_W*sizeof(bigint_word_t));
238 // a->wordv = (const uint32_t*)(((uint8_t*)a->wordv)+(scale&3));
239 dst = dest->wordv + (scale&(sizeof(bigint_word_t)-1));
240 for(i=scale/sizeof(bigint_word_t); i<a->length_W+scale_w; ++i,++j){
242 if(dest->length_W>i){
245 dst[i] = (bigint_word_t)t;
246 t>>=BIGINT_WORD_SIZE;
249 if(dest->length_W>i){
252 dst[i] = (bigint_word_t)t;
253 t>>=BIGINT_WORD_SIZE;
256 if(dest->length_W < i){
263 /******************************************************************************/
265 /* this should be implemented in assembly */
266 void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
269 bigint_wordplus_signed_t t=0LL;
271 r = bigint_cmp_u(a,b);
273 bigint_set_zero(dest);
277 bigint_copy(dest, a);
282 bigint_copy(dest, b);
287 bigint_sub_u(dest, b, a);
291 for(i=0; i < a->length_W; ++i){
297 dest->wordv[i]=(bigint_word_t)t;
309 /******************************************************************************/
311 int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){
312 if(a->length_W > b->length_W){
315 if(a->length_W < b->length_W){
318 if(a->length_W == 0){
324 if(a->wordv[i] != b->wordv[i]){
325 if(a->wordv[i] > b->wordv[i]){
335 /******************************************************************************/
337 void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
340 s |= GET_SIGN(b)?1:0;
342 case 0: /* both positive */
343 bigint_add_u(dest, a,b);
346 case 1: /* a positive, b negative */
347 bigint_sub_u(dest, a, b);
349 case 2: /* a negative, b positive */
350 bigint_sub_u(dest, b, a);
352 case 3: /* both negative */
353 bigint_add_u(dest, a, b);
356 default: /* how can this happen?*/
361 /******************************************************************************/
363 void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
366 s |= GET_SIGN(b)?1:0;
368 case 0: /* both positive */
369 bigint_sub_u(dest, a,b);
371 case 1: /* a positive, b negative */
372 bigint_add_u(dest, a, b);
375 case 2: /* a negative, b positive */
376 bigint_add_u(dest, a, b);
379 case 3: /* both negative */
380 bigint_sub_u(dest, b, a);
382 default: /* how can this happen?*/
388 /******************************************************************************/
390 int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){
392 if(a->length_W==0 && b->length_W==0){
396 s |= GET_SIGN(b)?1:0;
398 case 0: /* both positive */
399 return bigint_cmp_u(a, b);
401 case 1: /* a positive, b negative */
404 case 2: /* a negative, b positive */
407 case 3: /* both negative */
408 return bigint_cmp_u(b, a);
410 default: /* how can this happen?*/
413 return 0; /* just to satisfy the compiler */
416 /******************************************************************************/
418 void bigint_shiftleft(bigint_t* a, uint16_t shift){
419 uint16_t byteshift, words_to_shift;
423 bigint_wordplus_t t=0;
427 byteshift = shift / 8;
428 bitshift = shift & 7;
429 memset(&a->wordv[a->length_W], 0x00, byteshift);
431 memmove(((uint8_t*)a->wordv)+byteshift, a->wordv, a->length_W * sizeof(bigint_word_t));
432 memset(a->wordv, 0, byteshift);
435 p = (bigint_word_t*)((uint8_t*)a->wordv + byteshift / sizeof(bigint_word_t));
436 words_to_shift = a->length_W + ((byteshift % sizeof(bigint_word_t))?1:0);
438 for(i = 0; i < words_to_shift; ++i){
439 t |= ((bigint_wordplus_t)p[i]) << bitshift;
440 p[i] = (bigint_word_t)t;
441 t >>= BIGINT_WORD_SIZE;
443 p[i] = (bigint_word_t)t;
445 a->length_W += (shift + BIGINT_WORD_SIZE - 1) / BIGINT_WORD_SIZE;
449 /******************************************************************************/
451 void bigint_shiftright(bigint_t* a, uint16_t shift){
455 bigint_wordplus_t t=0;
458 if(byteshift >= a->length_W * sizeof(bigint_word_t)){ /* we would shift out more than we have */
462 if(byteshift == a->length_W * sizeof(bigint_word_t) - 1 && bitshift > GET_FBS(a)){
467 memmove(a->wordv, (uint8_t*)a->wordv + byteshift, a->length_W * sizeof(bigint_word_t) - byteshift);
468 memset((uint8_t*)a->wordv + a->length_W * sizeof(bigint_word_t) - byteshift, 0, byteshift);
470 byteshift /= sizeof(bigint_word_t);
471 a->length_W -= (byteshift + sizeof(bigint_word_t) - 1) / sizeof(bigint_word_t);
472 if(bitshift != 0 && a->length_W){
473 /* shift to the right */
476 t |= ((bigint_wordplus_t)(a->wordv[i])) << (BIGINT_WORD_SIZE - bitshift);
477 a->wordv[i] = (bigint_word_t)(t >> BIGINT_WORD_SIZE);
478 t <<= BIGINT_WORD_SIZE;
484 /******************************************************************************/
486 void bigint_xor(bigint_t* dest, const bigint_t* a){
488 for(i=0; i<a->length_W; ++i){
489 dest->wordv[i] ^= a->wordv[i];
494 /******************************************************************************/
496 void bigint_set_zero(bigint_t* a){
500 /******************************************************************************/
502 /* using the Karatsuba-Algorithm */
503 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
504 void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
505 if(a->length_W==0 || b->length_W==0){
506 bigint_set_zero(dest);
509 if(dest==a || dest==b){
511 bigint_word_t d_b[a->length_W + b->length_W];
513 bigint_mul_u(&d, a, b);
514 bigint_copy(dest, &d);
517 if(a->length_W==1 || b->length_W==1){
518 if(a->length_W != 1){
521 bigint_wordplus_t t=0;
523 bigint_word_t x = a->wordv[0];
524 for(i=0; i < b->length_W; ++i){
525 t += ((bigint_wordplus_t)b->wordv[i]) * ((bigint_wordplus_t)x);
526 dest->wordv[i] = (bigint_word_t)t;
527 t>>=BIGINT_WORD_SIZE;
529 dest->wordv[i] = (bigint_word_t)t;
530 dest->length_W = i+1;
535 if(a->length_W * sizeof(bigint_word_t) <= 4 && b->length_W * sizeof(bigint_word_t) <= 4){
538 memcpy(&p, a->wordv, a->length_W*sizeof(bigint_word_t));
539 memcpy(&q, b->wordv, b->length_W*sizeof(bigint_word_t));
540 r = (uint64_t)p * (uint64_t)q;
541 memcpy(dest->wordv, &r, (dest->length_W = a->length_W + b->length_W)*sizeof(bigint_word_t));
545 #if BIGINT_WORD_SIZE == 8
546 if(a->length_W <= 4 || b->length_W <= 4){
550 uint32_t x = 0, y = 0;
551 uint16_t j = b->length_W / 4, idx = 0;
553 memcpy(&x, a->wordv, a->length_W);
555 r += (uint64_t)((uint32_t*)b->wordv)[idx] * (uint64_t)x;
556 ((uint32_t*)dest->wordv)[idx] = (uint32_t)r;
562 memcpy(&y, b->wordv + idx, b->length_W - idx);
563 r += (uint64_t)y * (uint64_t)x;
565 dest->wordv[idx++] = (uint8_t)r;
568 dest->length_W = idx;
573 /* split a in xh & xl; split b in yh & yl */
574 const uint16_t n = (MAX(a->length_W, b->length_W)+1)/2;
575 bigint_t xl, xh, yl, yh;
578 if(a->length_W <= n){
579 bigint_set_zero(&xh);
580 xl.length_W = a->length_W;
586 xh.wordv = &(a->wordv[n]);
587 xh.length_W = a->length_W-n;
590 if(b->length_W <= n){
591 bigint_set_zero(&yh);
592 yl.length_W = b->length_W;
598 yh.wordv = &(b->wordv[n]);
599 yh.length_W = b->length_W-n;
602 /* now we have split up a and b */
603 /* remember we want to do:
604 * x*y = (xh * b ** n + xl) * (yh * b ** n + yl)
605 * x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + xl*yl
606 * 5 9 2 4 3 7 5 6 1 8 1
608 bigint_word_t tmp1_b[n*2+2];
611 tmp2.wordv = &tmp1_b[n+1];
613 bigint_add_u(&tmp2, &xh, &xl); /* 2: tmp2 <= xh + xl */
614 bigint_add_u(&tmp1, &yh, &yl); /* 3: tmp1 <= yh + yl */
615 bigint_mul_u(dest, &tmp2, &tmp1); /* 4: dest <= tmp2 * tmp1 */
616 bigint_mul_u(&tmp1, &xh, &yh); /* 5: tmp1 <= xh * yh */
617 bigint_sub_u(dest, dest, &tmp1); /* 7: dest <= dest - tmp1 */
618 bigint_word_t tmp3_b[2*n];
620 bigint_mul_u(&tmp2, &xl, &yl); /* 1: tmp3 <= xl * yl */
621 bigint_sub_u(dest, dest, &tmp2); /* 6: dest <= dest - tmp3 */
622 bigint_shiftleft(dest, n * sizeof(bigint_word_t) * 8);
623 bigint_add_u(dest, dest, &tmp2); /* 8: dest <= tmp3 + dest ** n */
624 bigint_add_scale_u(dest, &tmp1, 2*n*sizeof(bigint_word_t)); /* 9: dest <= dest + tmp1 ** (2 * n) */
627 bigint_mul_u(dest, &xl, &yl); /* 1: dest <= xl * yl */
628 bigint_add_u(&tmp2, &xh, &xl); /* 2: tmp2 <= xh + xl */
629 bigint_add_u(&tmp1, &yh, &yl); /* 3: tmp1 <= yh + yl */
630 bigint_mul_u(&tmp3, &tmp2, &tmp1); /* 4: tmp3 <= tmp2 * tmp1 */
631 bigint_mul_u(&tmp1, &xh, &yh); /* 5: h <= xh * yh */
632 bigint_sub_u(&tmp3, &tmp3, dest); /* 6: tmp3 <= tmp3 - dest */
633 bigint_sub_u(&tmp3, &tmp3, &tmp1); /* 7: tmp3 <= tmp3 - h */
634 bigint_add_scale_u(dest, &tmp3, n*sizeof(bigint_word_t)); /* 8: dest <= dest + tmp3 ** n */
635 bigint_add_scale_u(dest, &tmp1, 2*n*sizeof(bigint_word_t)); /* 9: dest <= dest + tmp1 ** (2 * n) */
639 /******************************************************************************/
641 void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
644 s |= GET_SIGN(b)?1:0;
646 case 0: /* both positive */
647 bigint_mul_u(dest, a,b);
650 case 1: /* a positive, b negative */
651 bigint_mul_u(dest, a,b);
654 case 2: /* a negative, b positive */
655 bigint_mul_u(dest, a,b);
658 case 3: /* both negative */
659 bigint_mul_u(dest, a,b);
662 default: /* how can this happen?*/
667 /******************************************************************************/
670 /* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */
671 void bigint_square(bigint_t* dest, const bigint_t* a){
672 if(a->length_W * sizeof(bigint_word_t) <= 4){
674 memcpy(&r, a->wordv, a->length_W * sizeof(bigint_word_t));
676 memcpy(dest->wordv, &r, 2 * a->length_W*sizeof(bigint_word_t));
678 dest->length_W = 2 * a->length_W;
684 bigint_word_t d_b[a->length_W * 2];
686 bigint_square(&d, a);
687 bigint_copy(dest, &d);
691 n = (a->length_W + 1) / 2;
692 bigint_t xh, xl, tmp; /* x-high, x-low, temp */
693 bigint_word_t buffer[2 * n + 1];
697 xh.wordv = &(a->wordv[n]);
698 xh.length_W = a->length_W - n;
702 /* (xh * b**n + xl)**2 = xh**2 * b**2n + 2 * xh * xl * b**n + xl**2 */
704 // cli_putstr("\r\nDBG (a): xl: "); bigint_print_hex(&xl);
705 // cli_putstr("\r\nDBG (b): xh: "); bigint_print_hex(&xh);
706 bigint_square(dest, &xl);
707 // cli_putstr("\r\nDBG (1): xl**2: "); bigint_print_hex(dest);
708 bigint_square(&tmp, &xh);
709 // cli_putstr("\r\nDBG (2): xh**2: "); bigint_print_hex(&tmp);
710 bigint_add_scale_u(dest, &tmp, 2 * n * sizeof(bigint_word_t));
711 // cli_putstr("\r\nDBG (3): xl**2 + xh**2*n**2: "); bigint_print_hex(dest);
712 bigint_mul_u(&tmp, &xl, &xh);
713 // cli_putstr("\r\nDBG (4): xl*xh: "); bigint_print_hex(&tmp);
714 bigint_shiftleft(&tmp, 1);
715 // cli_putstr("\r\nDBG (5): xl*xh*2: "); bigint_print_hex(&tmp);
716 bigint_add_scale_u(dest, &tmp, n*sizeof(bigint_word_t));
717 // cli_putstr("\r\nDBG (6): x**2: "); bigint_print_hex(dest);
718 // cli_putstr("\r\n");
721 /******************************************************************************/
722 void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
724 bigint_word_t tmp_b[b->length_W + 1];
725 const uint16_t word_shift = bitscale / BIGINT_WORD_SIZE;
727 if(a->length_W < b->length_W + word_shift){
729 cli_putstr("\r\nDBG: *bang*\r\n");
735 bigint_copy(&tmp, b);
736 bigint_shiftleft(&tmp, bitscale % BIGINT_WORD_SIZE);
738 // cli_putstr_P(PSTR("\r\nDBG: shifted value: ")); bigint_print_hex(&tmp);
741 x.wordv = &(a->wordv[word_shift]);
742 x.length_W = a->length_W - word_shift;
744 bigint_sub_u(&x, &x, &tmp);
745 a->length_W = x.length_W + word_shift;
750 /******************************************************************************/
752 void bigint_reduce(bigint_t* a, const bigint_t* r){
753 // bigint_adjust((bigint_t*)r);
754 uint8_t rfbs = GET_FBS(r);
756 cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a);
758 if(r->length_W==0 || a->length_W==0){
761 if((r->length_W*sizeof(bigint_word_t)<=4) && (a->length_W*sizeof(bigint_word_t)<=4)){
763 memcpy(&p, a->wordv, a->length_W*sizeof(bigint_word_t));
764 memcpy(&q, r->wordv, r->length_W*sizeof(bigint_word_t));
766 memcpy(a->wordv, &p, a->length_W*sizeof(bigint_word_t));
768 // cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a);
772 while(a->length_W > r->length_W){
773 shift = (a->length_W - r->length_W) * 8 * sizeof(bigint_word_t) + GET_FBS(a) - rfbs - 1;
775 if((a->wordv[a->length_W-1] & ((1LL<<GET_FBS(a)) - 1)) > r->wordv[r->length_W-1]){
777 cli_putstr("\r\n ~ [a] = ");
778 cli_hexdump_rev(&a->wordv[a->length_W-1], 4);
779 cli_putstr(" [r] = ");
780 cli_hexdump_rev(&r->wordv[r->length_W-1], 4);
784 // cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 2);
785 // cli_putstr(" a_len = "); cli_hexdump_rev(&a->length_W, 2);
786 // cli_putstr(" r_len = "); cli_hexdump_rev(&r->length_W, 2);
788 bigint_sub_u_bitscale(a, r, shift);
789 // cli_putstr("\r\nDBG: (1) = "); bigint_print_hex(a);
791 while((GET_FBS(a) > rfbs) && (a->length_W == r->length_W)){
792 shift = GET_FBS(a)-rfbs-1;
793 // cli_putstr("\r\nDBG: (2a) = "); bigint_print_hex(a);
794 // cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2);
795 bigint_sub_u_bitscale(a, r, shift);
796 // cli_putstr("\r\nDBG: (2b) = "); bigint_print_hex(a);
798 while(bigint_cmp_u(a,r)>=0){
800 // cli_putstr("\r\nDBG: (3) = "); bigint_print_hex(a);
804 // cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a);
805 // cli_putstr("\r\n");
808 /******************************************************************************/
810 /* calculate dest = a**exp % r */
811 /* using square&multiply */
812 void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
813 if(a->length_W==0 || r->length_W==0){
818 bigint_word_t t, base_b[MAX(a->length_W,r->length_W)], res_b[r->length_W*2];
821 // uint16_t *xaddr = &i;
822 // cli_putstr("\r\npre-alloc (");
823 // cli_hexdump_rev(&xaddr, 4);
824 // cli_putstr(") ...");
827 bigint_copy(&base, a);
828 // cli_putstr("\r\npost-copy");
829 bigint_reduce(&base, r);
834 if(exp->length_W == 0){
835 bigint_copy(dest, &res);
839 t=exp->wordv[exp->length_W - 1];
840 for(i=exp->length_W; i > 0; --i){
841 t = exp->wordv[i - 1];
842 for(j=BIGINT_WORD_SIZE; j > 0; --j){
844 if(t & (1<<(BIGINT_WORD_SIZE-1))){
849 bigint_square(&res, &res);
850 bigint_reduce(&res, r);
851 if(t & (1<<(BIGINT_WORD_SIZE-1))){
852 bigint_mul_u(&res, &res, &base);
853 bigint_reduce(&res, r);
862 bigint_copy(dest, &res);
865 /******************************************************************************/
867 #define cli_putstr(a)
868 #define bigint_print_hex(a)
869 #define cli_hexdump_rev(a,b)
870 #define uart_flush(a)
872 /* gcd <-- gcd(x,y) a*x+b*y=gcd */
873 void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){
874 bigint_t g, x_, y_, u, v, a_, b_, c_, d_;
876 if(x->length_W==0 || y->length_W==0){
879 if(x->length_W==1 && x->wordv[0]==1){
893 if(y->length_W==1 && y->wordv[0]==1){
908 while(x->wordv[i]==0 && y->wordv[i]==0){
911 bigint_word_t g_b[i+2], x_b[x->length_W-i], y_b[y->length_W-i];
912 bigint_word_t u_b[x->length_W-i], v_b[y->length_W-i];
913 bigint_word_t a_b[y->length_W+2], c_b[y->length_W+2];
914 bigint_word_t b_b[x->length_W+2], d_b[x->length_W+2];
919 memset(g_b, 0, i*sizeof(bigint_word_t));
923 x_.info = y_.info = 0;
924 x_.length_W = x->length_W-i;
925 y_.length_W = y->length_W-i;
926 memcpy(x_.wordv, x->wordv+i, x_.length_W*sizeof(bigint_word_t));
927 memcpy(y_.wordv, y->wordv+i, y_.length_W*sizeof(bigint_word_t));
928 for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
935 bigint_shiftleft(&g, i);
936 bigint_shiftright(&x_, i);
937 bigint_shiftright(&y_, i);
947 bigint_copy(&u, &x_);
948 bigint_copy(&v, &y_);
955 bigint_set_zero(&b_);
956 bigint_set_zero(&c_);
958 cli_putstr("\r\nDBG (gcdext) 0");
959 while((u.wordv[0]&1)==0){
960 cli_putstr("\r\nDBG (gcdext) 0.1");
961 bigint_shiftright(&u, 1);
962 if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
963 bigint_add_s(&a_, &a_, &y_);
964 bigint_sub_s(&b_, &b_, &x_);
966 bigint_shiftright(&a_, 1);
967 bigint_shiftright(&b_, 1);
969 while((v.wordv[0]&1)==0){
970 cli_putstr("\r\nDBG (gcdext) 0.2");
971 bigint_shiftright(&v, 1);
972 if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
973 bigint_add_s(&c_, &c_, &y_);
974 bigint_sub_s(&d_, &d_, &x_);
976 bigint_shiftright(&c_, 1);
977 bigint_shiftright(&d_, 1);
980 if(bigint_cmp_u(&u, &v)>=0){
981 bigint_sub_u(&u, &u, &v);
982 bigint_sub_s(&a_, &a_, &c_);
983 bigint_sub_s(&b_, &b_, &d_);
985 bigint_sub_u(&v, &v, &u);
986 bigint_sub_s(&c_, &c_, &a_);
987 bigint_sub_s(&d_, &d_, &b_);
991 bigint_mul_s(gcd, &v, &g);
1001 /******************************************************************************/
1003 void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
1004 bigint_gcdext(NULL, dest, NULL, a, m);
1005 while(dest->info&BIGINT_NEG_MASK){
1006 bigint_add_s(dest, dest, m);
1010 /******************************************************************************/
1012 void bigint_changeendianess(bigint_t* a){
1014 p = (uint8_t*)(a->wordv);
1015 q = p + a->length_W * sizeof(bigint_word_t) - 1;
1024 /******************************************************************************/