3 This file is part of the AVR-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__)
37 #include "bigint_io.h"
40 #define MAX(a,b) (((a)>(b))?(a):(b))
44 #define MIN(a,b) (((a)<(b))?(a):(b))
47 #define SET_FBS(a, v) do{(a)->info &=0xF8; (a)->info |= (v);}while(0)
48 #define GET_FBS(a) ((a)->info&BIGINT_FBS_MASK)
49 #define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK
50 #define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK
51 #define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0)
52 #define XCHG_PTR(a,b) do{ a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
53 b = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
54 a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b)));}while(0)
56 #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK)
59 /******************************************************************************/
61 void bigint_copy(bigint_t* dest, const bigint_t* src){
62 memcpy(dest->wordv, src->wordv, src->length_W);
63 dest->length_W = src->length_W;
64 dest->info = src->info;
67 /******************************************************************************/
69 /* this should be implemented in assembly */
71 void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
73 if(a->length_W < b->length_W){
76 for(i=0; i<b->length_W; ++i){
77 t = a->wordv[i] + b->wordv[i] + t;
78 dest->wordv[i] = (uint8_t)t;
81 for(; i<a->length_W; ++i){
83 dest->wordv[i] = (uint8_t)t;
91 /******************************************************************************/
93 /* this should be implemented in assembly */
95 void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){
98 if(scale>dest->length_W)
99 memset(dest->wordv+dest->length_W, 0, scale-dest->length_W);
100 for(i=scale; i<a->length_W+scale; ++i,++j){
102 if(dest->length_W>i){
105 dest->wordv[i] = (uint8_t)t;
109 if(dest->length_W>i){
110 t = dest->wordv[i] + t;
112 dest->wordv[i] = (uint8_t)t;
116 if(dest->length_W < i){
122 /******************************************************************************/
124 /* this should be implemented in assembly */
125 void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
129 uint16_t i, min, max;
130 min = MIN(a->length_W, b->length_W);
131 max = MAX(a->length_W, b->length_W);
132 r = bigint_cmp_u(a,b);
140 dest->length_W = a->length_W;
141 memcpy(dest->wordv, a->wordv, a->length_W);
142 dest->info = a->info;
147 dest->length_W = b->length_W;
148 memcpy(dest->wordv, b->wordv, b->length_W);
149 dest->info = b->info;
154 bigint_sub_u(dest, b, a);
157 for(i=0; i<min; ++i){
158 t = a->wordv[i] - b->wordv[i] - borrow;
161 dest->wordv[i]=(uint8_t)t;
164 dest->wordv[i]=(uint8_t)t;
168 t = a->wordv[i] - borrow;
171 dest->wordv[i]=(uint8_t)t;
174 dest->wordv[i]=(uint8_t)t;
184 /******************************************************************************/
186 int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){
187 if(a->length_W > b->length_W){
190 if(a->length_W < b->length_W){
199 if(a->wordv[i]!=b->wordv[i]){
200 if(a->wordv[i]>b->wordv[i]){
210 /******************************************************************************/
212 void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
215 s |= GET_SIGN(b)?1:0;
217 case 0: /* both positive */
218 bigint_add_u(dest, a,b);
221 case 1: /* a positive, b negative */
222 bigint_sub_u(dest, a, b);
224 case 2: /* a negative, b positive */
225 bigint_sub_u(dest, b, a);
227 case 3: /* both negative */
228 bigint_add_u(dest, a, b);
231 default: /* how can this happen?*/
236 /******************************************************************************/
238 void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
241 s |= GET_SIGN(b)?1:0;
243 case 0: /* both positive */
244 bigint_sub_u(dest, a,b);
246 case 1: /* a positive, b negative */
247 bigint_add_u(dest, a, b);
250 case 2: /* a negative, b positive */
251 bigint_add_u(dest, a, b);
254 case 3: /* both negative */
255 bigint_sub_u(dest, b, a);
257 default: /* how can this happen?*/
263 /******************************************************************************/
265 int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){
267 if(a->length_W==0 && b->length_W==0){
271 s |= GET_SIGN(b)?1:0;
273 case 0: /* both positive */
274 return bigint_cmp_u(a, b);
276 case 1: /* a positive, b negative */
279 case 2: /* a negative, b positive */
282 case 3: /* both negative */
283 return bigint_cmp_u(b, a);
285 default: /* how can this happen?*/
288 return 0; /* just to satisfy the compiler */
291 /******************************************************************************/
293 void bigint_shiftleft(bigint_t* a, uint16_t shift){
298 byteshift = (shift+3)/8;
300 memmove(a->wordv+byteshift, a->wordv, a->length_W);
301 memset(a->wordv, 0, byteshift);
303 if(bitshift<=4){ /* shift to the left */
304 for(i=byteshift; i<a->length_W+byteshift; ++i){
305 t |= (a->wordv[i])<<bitshift;
306 a->wordv[i] = (uint8_t)t;
309 a->wordv[i] = (uint8_t)t;
311 }else{ /* shift to the right */
312 for(i=a->length_W+byteshift-1; i>byteshift-1; --i){
313 t |= (a->wordv[i])<<(bitshift);
314 a->wordv[i] = (uint8_t)(t>>8);
317 t |= (a->wordv[i])<<(bitshift);
318 a->wordv[i] = (uint8_t)(t>>8);
321 a->length_W += byteshift;
325 /******************************************************************************/
327 void bigint_shiftright(bigint_t* a, uint16_t shift){
334 if(byteshift >= a->length_W){ /* we would shift out more than we have */
338 if(byteshift == a->length_W-1 && bitshift>GET_FBS(a)){
343 memmove(a->wordv, a->wordv+byteshift, a->length_W-byteshift);
344 memset(a->wordv+a->length_W-byteshift, 0, byteshift);
347 /* shift to the right */
348 for(i=a->length_W-byteshift-1; i>0; --i){
349 t |= (a->wordv[i])<<(8-bitshift);
350 a->wordv[i] = (uint8_t)(t>>8);
353 t |= (a->wordv[0])<<(8-bitshift);
354 a->wordv[0] = (uint8_t)(t>>8);
356 a->length_W -= byteshift;
360 /******************************************************************************/
362 void bigint_xor(bigint_t* dest, const bigint_t* a){
364 for(i=0; i<a->length_W; ++i){
365 dest->wordv[i] ^= a->wordv[i];
370 /******************************************************************************/
372 void bigint_set_zero(bigint_t* a){
376 /******************************************************************************/
378 /* using the Karatsuba-Algorithm */
379 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
380 void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
381 if(a->length_W==0 || b->length_W==0){
382 bigint_set_zero(dest);
385 if(dest==a || dest==b){
387 uint8_t d_b[a->length_W+b->length_W];
389 bigint_mul_u(&d, a, b);
390 bigint_copy(dest, &d);
393 if(a->length_W==1 || b->length_W==1){
398 uint8_t x = a->wordv[0];
399 for(i=0; i<b->length_W; ++i){
401 dest->wordv[i] = (uint8_t)t;
404 dest->wordv[i] = (uint8_t)t;
409 if(a->length_W<=4 && b->length_W<=4){
412 memcpy(&p, a->wordv, a->length_W);
413 memcpy(&q, b->wordv, b->length_W);
414 r = (uint64_t)p*(uint64_t)q;
415 memcpy(dest->wordv, &r, a->length_W+b->length_W);
416 dest->length_W = a->length_W+b->length_W;
420 bigint_set_zero(dest);
421 /* split a in xh & xl; split b in yh & yl */
423 n=(MAX(a->length_W, b->length_W)+1)/2;
424 bigint_t xl, xh, yl, yh;
430 xl.length_W = a->length_W;
436 xh.wordv = a->wordv+n;
437 xh.length_W = a->length_W-n;
443 yl.length_W = b->length_W;
449 yh.wordv = b->wordv+n;
450 yh.length_W = b->length_W-n;
453 /* now we have split up a and b */
454 uint8_t tmp_b[2*n+2], m_b[2*(n+1)];
455 bigint_t tmp, tmp2, m;
457 tmp2.wordv = tmp_b+n+1;
460 bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */
461 bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */
462 bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */
463 bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp2*tmp */
464 bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */
465 bigint_sub_u(&m, &m, dest); /* m <= m-dest */
466 bigint_sub_u(&m, &m, &tmp); /* m <= m-h */
467 bigint_add_scale_u(dest, &m, n);
468 bigint_add_scale_u(dest, &tmp, 2*n);
471 /******************************************************************************/
473 void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
476 s |= GET_SIGN(b)?1:0;
478 case 0: /* both positive */
479 bigint_mul_u(dest, a,b);
482 case 1: /* a positive, b negative */
483 bigint_mul_u(dest, a,b);
486 case 2: /* a negative, b positive */
487 bigint_mul_u(dest, a,b);
490 case 3: /* both negative */
491 bigint_mul_u(dest, a,b);
494 default: /* how can this happen?*/
499 /******************************************************************************/
502 /* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */
503 void bigint_square(bigint_t* dest, const bigint_t* a){
506 memcpy(&r, a->wordv, a->length_W);
508 memcpy(dest->wordv, &r, 2*a->length_W);
510 dest->length_W=2*a->length_W;
516 uint8_t d_b[a->length_W*2];
518 bigint_square(&d, a);
519 bigint_copy(dest, &d);
524 bigint_t xh, xl, tmp; /* x-high, x-low, temp */
525 uint8_t buffer[2*n+1];
528 xh.wordv = a->wordv+n;
529 xh.length_W = a->length_W-n;
531 bigint_square(dest, &xl);
532 bigint_square(&tmp, &xh);
533 bigint_add_scale_u(dest, &tmp, 2*n);
534 bigint_mul_u(&tmp, &xl, &xh);
535 bigint_shiftleft(&tmp, 1);
536 bigint_add_scale_u(dest, &tmp, n);
539 /******************************************************************************/
541 void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
543 uint8_t tmp_b[b->length_W+1];
544 uint16_t i,j,byteshift=bitscale/8;
548 if(a->length_W < b->length_W+byteshift){
554 bigint_copy(&tmp, b);
555 bigint_shiftleft(&tmp, bitscale&7);
557 for(j=0,i=byteshift; i<tmp.length_W+byteshift; ++i, ++j){
558 t = a->wordv[i] - tmp.wordv[j] - borrow;
559 a->wordv[i] = (uint8_t)t;
567 if(i+1 > a->length_W){
571 a->wordv[i] -= borrow;
572 if(a->wordv[i]!=0xff){
580 /******************************************************************************/
582 void bigint_reduce(bigint_t* a, const bigint_t* r){
584 uint8_t rfbs = GET_FBS(r);
586 if(r->length_W==0 || a->length_W==0){
589 while(a->length_W > r->length_W){
590 bigint_sub_u_bitscale(a, r, (a->length_W-r->length_W)*8+GET_FBS(a)-rfbs-1);
592 while((GET_FBS(a) > rfbs+1) && (a->length_W == r->length_W)){
593 bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1);
595 while(bigint_cmp_u(a,r)>=0){
601 /******************************************************************************/
603 /* calculate dest = a**exp % r */
604 /* using square&multiply */
605 void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
606 if(a->length_W==0 || r->length_W==0){
611 uint8_t base_b[MAX(a->length_W,r->length_W*2)], res_b[r->length_W*2];
616 bigint_copy(&base, a);
617 bigint_reduce(&base, r);
622 for(i=0; i+1<exp->length_W; ++i){
626 bigint_mul_u(&res, &res, &base);
627 bigint_reduce(&res, r);
629 bigint_square(&base, &base);
630 bigint_reduce(&base, r);
637 bigint_mul_u(&res, &res, &base);
638 bigint_reduce(&res, r);
640 bigint_square(&base, &base);
641 bigint_reduce(&base, r);
645 bigint_copy(dest, &res);
648 /******************************************************************************/
649 /* gcd <-- gcd(x,y) a*x+b*y=gcd */
650 void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){
651 bigint_t g, x_, y_, u, v, a_, b_, c_, d_;
652 volatile uint16_t i=0;
653 if(x->length_W==0 || y->length_W==0){
656 while(x->wordv[i]==0 && y->wordv[i]==0){
659 uint8_t g_b[i+2], x_b[x->length_W-i], y_b[y->length_W-i];
660 uint8_t u_b[x->length_W-i], v_b[y->length_W-i];
661 uint8_t a_b[y->length_W+2], c_b[y->length_W+2];
662 uint8_t b_b[x->length_W+2], d_b[x->length_W+2];
671 x_.info = y_.info = 0;
672 x_.length_W = x->length_W-i;
673 y_.length_W = y->length_W-i;
674 memcpy(x_.wordv, x->wordv+i, x_.length_W);
675 memcpy(y_.wordv, y->wordv+i, y_.length_W);
676 for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
683 bigint_shiftleft(&g, i);
684 bigint_shiftright(&x_, i);
685 bigint_shiftright(&y_, i);
694 bigint_copy(&u, &x_);
695 bigint_copy(&v, &y_);
702 bigint_set_zero(&b_);
703 bigint_set_zero(&c_);
705 while((u.wordv[0]&1)==0){
706 bigint_shiftright(&u, 1);
707 if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
708 bigint_add_s(&a_, &a_, &y_);
709 bigint_sub_s(&b_, &b_, &x_);
711 bigint_shiftright(&a_, 1);
712 bigint_shiftright(&b_, 1);
714 while((v.wordv[0]&1)==0){
715 bigint_shiftright(&v, 1);
716 if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
717 bigint_add_s(&c_, &c_, &y_);
718 bigint_sub_s(&d_, &d_, &x_);
720 bigint_shiftright(&c_, 1);
721 bigint_shiftright(&d_, 1);
724 if(bigint_cmp_u(&u, &v)>=0){
725 bigint_sub_u(&u, &u, &v);
726 bigint_sub_s(&a_, &a_, &c_);
727 bigint_sub_s(&b_, &b_, &d_);
729 bigint_sub_u(&v, &v, &u);
730 bigint_sub_s(&c_, &c_, &a_);
731 bigint_sub_s(&d_, &d_, &b_);
735 bigint_mul_s(gcd, &v, &g);
745 /******************************************************************************/
747 void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
748 bigint_gcdext(NULL, dest, NULL, a, m);
749 while(dest->info&BIGINT_NEG_MASK){
750 bigint_add_s(dest, dest, m);
754 /******************************************************************************/
756 void bigint_changeendianess(bigint_t* a){
768 /******************************************************************************/