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
32 #include "bigint_io.h"
36 #define MAX(a,b) (((a)>(b))?(a):(b))
40 #define MIN(a,b) (((a)<(b))?(a):(b))
43 #define SET_FBS(a, v) do{(a)->info &=0xF8; (a)->info |= (v);}while(0)
44 #define GET_FBS(a) ((a)->info&BIGINT_FBS_MASK)
45 #define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK
46 #define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK
47 #define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0)
48 #define XCHG_PTR(a,b) do{ a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
49 b = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
50 a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b)));}while(0)
52 #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK)
54 /******************************************************************************/
55 void bigint_adjust(bigint_t* a){
56 while(a->length_B!=0 && a->wordv[a->length_B-1]==0){
65 t = a->wordv[a->length_B-1];
66 while((t&0x80)==0 && i){
73 /******************************************************************************/
75 void bigint_copy(bigint_t* dest, const bigint_t* src){
76 memcpy(dest->wordv, src->wordv, src->length_B);
77 dest->length_B = src->length_B;
78 dest->info = src->info;
81 /******************************************************************************/
83 /* this should be implemented in assembly */
85 void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
87 if(a->length_B < b->length_B){
90 for(i=0; i<b->length_B; ++i){
91 t = a->wordv[i] + b->wordv[i] + t;
92 dest->wordv[i] = (uint8_t)t;
95 for(; i<a->length_B; ++i){
97 dest->wordv[i] = (uint8_t)t;
100 dest->wordv[i++] = t;
105 /******************************************************************************/
107 /* this should be implemented in assembly */
108 void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){
111 if(scale>dest->length_B)
112 memset(dest->wordv+dest->length_B, 0, scale-dest->length_B);
113 for(i=scale; i<a->length_B+scale; ++i,++j){
115 if(dest->length_B>i){
118 dest->wordv[i] = (uint8_t)t;
122 if(dest->length_B>i){
123 t = dest->wordv[i] + t;
125 dest->wordv[i] = (uint8_t)t;
129 if(dest->length_B < i){
135 /******************************************************************************/
137 /* this should be implemented in assembly */
138 void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
142 uint16_t i, min, max;
143 min = MIN(a->length_B, b->length_B);
144 max = MAX(a->length_B, b->length_B);
145 r = bigint_cmp_u(a,b);
153 dest->length_B = a->length_B;
154 memcpy(dest->wordv, a->wordv, a->length_B);
155 dest->info = a->info;
160 dest->length_B = b->length_B;
161 memcpy(dest->wordv, b->wordv, b->length_B);
162 dest->info = b->info;
167 for(i=0; i<min; ++i){
168 t = a->wordv[i] - b->wordv[i] - borrow;
171 dest->wordv[i]=(uint8_t)(-t);
174 dest->wordv[i]=(uint8_t)(-t);
178 t = b->wordv[i] + borrow;
181 dest->wordv[i]=(uint8_t)t;
184 dest->wordv[i]=(uint8_t)t;
191 for(i=0; i<min; ++i){
192 t = a->wordv[i] - b->wordv[i] - borrow;
195 dest->wordv[i]=(uint8_t)t;
198 dest->wordv[i]=(uint8_t)t;
202 t = a->wordv[i] - borrow;
205 dest->wordv[i]=(uint8_t)t;
208 dest->wordv[i]=(uint8_t)t;
218 /******************************************************************************/
220 int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){
221 if(a->length_B > b->length_B){
224 if(a->length_B < b->length_B){
227 if(GET_FBS(a) > GET_FBS(b)){
230 if(GET_FBS(a) < GET_FBS(b)){
239 if(a->wordv[i]!=b->wordv[i]){
240 if(a->wordv[i]>b->wordv[i]){
250 /******************************************************************************/
252 void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
255 s |= GET_SIGN(b)?1:0;
257 case 0: /* both positive */
258 bigint_add_u(dest, a,b);
261 case 1: /* a positive, b negative */
262 bigint_sub_u(dest, a, b);
264 case 2: /* a negative, b positive */
265 bigint_sub_u(dest, b, a);
267 case 3: /* both negative */
268 bigint_add_u(dest, a, b);
271 default: /* how can this happen?*/
276 /******************************************************************************/
278 void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
281 s |= GET_SIGN(b)?1:0;
283 case 0: /* both positive */
284 bigint_sub_u(dest, a,b);
286 case 1: /* a positive, b negative */
287 bigint_add_u(dest, a, b);
290 case 2: /* a negative, b positive */
291 bigint_add_u(dest, a, b);
294 case 3: /* both negative */
295 bigint_sub_u(dest, b, a);
297 default: /* how can this happen?*/
303 /******************************************************************************/
305 int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){
308 s |= GET_SIGN(b)?1:0;
310 case 0: /* both positive */
311 return bigint_cmp_u(a, b);
313 case 1: /* a positive, b negative */
316 case 2: /* a negative, b positive */
319 case 3: /* both negative */
320 return bigint_cmp_u(b, a);
322 default: /* how can this happen?*/
325 return 0; /* just to satisfy the compiler */
328 /******************************************************************************/
330 void bigint_shiftleft(bigint_t* a, uint16_t shift){
335 byteshift = (shift+3)/8;
337 memmove(a->wordv+byteshift, a->wordv, a->length_B);
338 memset(a->wordv, 0, byteshift);
340 if(bitshift<=4){ /* shift to the left */
341 for(i=byteshift; i<a->length_B+byteshift; ++i){
342 t |= (a->wordv[i])<<bitshift;
343 a->wordv[i] = (uint8_t)t;
346 a->wordv[i] = (uint8_t)t;
347 }else{ /* shift to the right */
348 bitshift = 8 - bitshift;
349 for(i=a->length_B+byteshift-1; i>byteshift; --i){
350 t |= (a->wordv[i])<<(8-bitshift);
351 a->wordv[i] = (uint8_t)(t>>8);
354 t |= (a->wordv[i])<<(8-bitshift);
355 a->wordv[i] = (uint8_t)(t>>8);
359 a->length_B += byteshift+1;
363 /******************************************************************************/
365 void bigint_shiftright(bigint_t* a, uint16_t shift){
372 if(byteshift >= a->length_B){ /* we would shift out more than we have */
378 if(byteshift == a->length_B-1 && bitshift>GET_FBS(a)){
385 memmove(a->wordv, a->wordv+byteshift, a->length_B-byteshift);
386 memset(a->wordv+a->length_B-byteshift, 0, byteshift);
389 /* shift to the right */
390 for(i=a->length_B-byteshift-1; i>0; --i){
391 t |= (a->wordv[i])<<(8-bitshift);
392 a->wordv[i] = (uint8_t)(t>>8);
395 t |= (a->wordv[0])<<(8-bitshift);
396 a->wordv[0] = (uint8_t)(t>>8);
398 a->length_B -= byteshift;
402 /******************************************************************************/
404 void bigint_xor(bigint_t* dest, const bigint_t* a){
406 for(i=0; i<a->length_B; ++i){
407 dest->wordv[i] ^= a->wordv[i];
412 /******************************************************************************/
414 void bigint_set_zero(bigint_t* a){
418 /******************************************************************************/
420 /* using the Karatsuba-Algorithm */
421 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
422 void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
423 if(a->length_B==0 || b->length_B==0){
424 bigint_set_zero(dest);
428 if(a->length_B==1 || b->length_B==1){
433 uint8_t x = a->wordv[0];
434 for(i=0; i<b->length_B; ++i){
436 dest->wordv[i] = (uint8_t)t;
439 dest->wordv[i] = (uint8_t)t;
444 if(a->length_B<=4 && b->length_B<=4){
447 memcpy(&p, a->wordv, a->length_B);
448 memcpy(&q, b->wordv, b->length_B);
449 r = (uint64_t)p*(uint64_t)q;
450 memcpy(dest->wordv, &r, a->length_B+b->length_B);
451 dest->length_B = a->length_B+b->length_B;
455 bigint_set_zero(dest);
456 /* split a in xh & xl; split b in yh & yl */
458 n=(MAX(a->length_B, b->length_B)+1)/2;
459 bigint_t xl, xh, yl, yh;
465 xl.length_B = a->length_B;
471 xh.wordv = a->wordv+n;
472 xh.length_B = a->length_B-n;
478 yl.length_B = b->length_B;
484 yh.wordv = b->wordv+n;
485 yh.length_B = b->length_B-n;
488 /* now we have split up a and b */
489 uint8_t tmp_b[2*n+2], m_b[2*(n+1)];
490 bigint_t tmp, tmp2, m;
491 /* calculate h=xh*yh; l=xl*yl; sx=xh+xl; sy=yh+yl */
493 tmp2.wordv = tmp_b+n+1;
496 bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */
497 bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */
498 bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */
499 bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp*tmp */
500 bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */
501 bigint_sub_u(&m, &m, dest); /* m <= m-dest */
502 bigint_sub_u(&m, &m, &tmp); /* m <= m-h */
503 bigint_add_scale_u(dest, &m, n);
504 bigint_add_scale_u(dest, &tmp, 2*n);
507 /******************************************************************************/
509 void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
512 s |= GET_SIGN(b)?1:0;
514 case 0: /* both positive */
515 bigint_mul_u(dest, a,b);
518 case 1: /* a positive, b negative */
519 bigint_mul_u(dest, a,b);
522 case 2: /* a negative, b positive */
523 bigint_mul_u(dest, a,b);
526 case 3: /* both negative */
527 bigint_mul_u(dest, a,b);
530 default: /* how can this happen?*/
535 /******************************************************************************/
538 /* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */
539 void bigint_square(bigint_t* dest, const bigint_t* a){
542 memcpy(&r, a->wordv, a->length_B);
544 memcpy(dest->wordv, &r, 2*a->length_B);
546 dest->length_B=2*a->length_B;
552 bigint_t xh, xl, tmp; /* x-high, x-low, temp */
553 uint8_t buffer[2*n+1];
556 xh.wordv = a->wordv+n;
557 xh.length_B = a->length_B-n;
559 bigint_square(dest, &xl);
560 bigint_square(&tmp, &xh);
561 bigint_add_scale_u(dest, &tmp, 2*n);
562 bigint_mul_u(&tmp, &xl, &xh);
563 bigint_shiftleft(&tmp, 1);
564 bigint_add_scale_u(dest, &tmp, n);