bigint/bigint-stub.c

   1 /* bigint.c */
   2 /*
   3     This file is part of the ARM-Crypto-Lib.
   4     Copyright (C) 2008  Daniel Otte (daniel.otte@rub.de)
   5
   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.
  10
  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.
  15
  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/>.
  18 */
  19 /**
  20  * \file                bigint.c
  21  * \author              Daniel Otte
  22  * \date                2010-02-22
  23  *
  24  * \license         GPLv3 or later
  25  *
  26  */
  27
  28
  29 #define STRING2(x) #x
  30 #define STRING(x) STRING2(x)
  31 #define STR_LINE STRING(__LINE__)
  32
  33 #include "bigint.h"
  34 #include <string.h>
  35 /*
  36 #include "cli.h"
  37 #include "bigint_io.h"
  38 */
  39 #ifndef MAX
  40  #define MAX(a,b) (((a)>(b))?(a):(b))
  41 #endif
  42
  43 #ifndef MIN
  44  #define MIN(a,b) (((a)<(b))?(a):(b))
  45 #endif
  46
  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)
  55
  56 #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK)
  57
  58
  59 /******************************************************************************/
  60 /*
  61 void bigint_copy(bigint_t* dest, const bigint_t* src){
  62         memcpy(dest->wordv, src->wordv, src->length_B);
  63         dest->length_B = src->length_B;
  64         dest->info = src->info;
  65 }
  66 */
  67 /******************************************************************************/
  68
  69 /* this should be implemented in assembly */
  70 /*
  71 void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
  72         uint16_t t=0, i;
  73         if(a->length_B < b->length_B){
  74                 XCHG_PTR(a,b);
  75         }
  76         for(i=0; i<b->length_B; ++i){
  77                 t = a->wordv[i] + b->wordv[i] + t;
  78                 dest->wordv[i] = (uint8_t)t;
  79                 t>>=8;
  80         }
  81         for(; i<a->length_B; ++i){
  82                 t = a->wordv[i] + t;
  83                 dest->wordv[i] = (uint8_t)t;
  84                 t>>=8;
  85         }
  86         dest->wordv[i++] = t;
  87         dest->length_B = i;
  88         bigint_adjust(dest);
  89 }
  90 */
  91 /******************************************************************************/
  92
  93 /* this should be implemented in assembly */
  94 void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){
  95         uint16_t i,j=0;
  96         uint16_t t=0;
  97         if(scale>dest->length_B)
  98                 memset(dest->wordv+dest->length_B, 0, scale-dest->length_B);
  99         for(i=scale; i<a->length_B+scale; ++i,++j){
 100                 t = a->wordv[j] + t;
 101                 if(dest->length_B>i){
 102                         t += dest->wordv[i];
 103                 }
 104                 dest->wordv[i] = (uint8_t)t;
 105                 t>>=8;
 106         }
 107         while(t){
 108                 if(dest->length_B>i){
 109                         t = dest->wordv[i] + t;
 110                 }
 111                 dest->wordv[i] = (uint8_t)t;
 112                 t>>=8;
 113                 ++i;
 114         }
 115         if(dest->length_B < i){
 116                 dest->length_B = i;
 117         }
 118         bigint_adjust(dest);
 119 }
 120
 121 /******************************************************************************/
 122
 123 /* this should be implemented in assembly */
 124 void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 125         int8_t borrow=0;
 126         int8_t  r;
 127         int16_t t;
 128         uint16_t i, min, max;
 129         min = MIN(a->length_B, b->length_B);
 130         max = MAX(a->length_B, b->length_B);
 131         r = bigint_cmp_u(a,b);
 132         if(r==0){
 133                 dest->length_B = 0;
 134                 dest->wordv[0] = 0;
 135                 bigint_adjust(dest);
 136                 return;
 137         }
 138         if(b->length_B==0){
 139                 dest->length_B = a->length_B;
 140                 memcpy(dest->wordv, a->wordv, a->length_B);
 141                 dest->info = a->info;
 142                 SET_POS(dest);
 143                 return;
 144         }
 145         if(a->length_B==0){
 146                         dest->length_B = b->length_B;
 147                         memcpy(dest->wordv, b->wordv, b->length_B);
 148                         dest->info = b->info;
 149                         SET_NEG(dest);
 150                         return;
 151         }
 152         if(r<0){
 153                 bigint_sub_u(dest, b, a);
 154                 SET_NEG(dest);
 155         }else{
 156                 for(i=0; i<min; ++i){
 157                         t = a->wordv[i] - b->wordv[i] - borrow;
 158                         if(t<0){
 159                                 borrow = 1;
 160                                 dest->wordv[i]=(uint8_t)t;
 161                         }else{
 162                                 borrow = 0;
 163                                 dest->wordv[i]=(uint8_t)t;
 164                         }
 165                 }
 166                 for(;i<max; ++i){
 167                         t = a->wordv[i] - borrow;
 168                         if(t<0){
 169                                 borrow = 1;
 170                                 dest->wordv[i]=(uint8_t)t;
 171                         }else{
 172                                 borrow = 0;
 173                                 dest->wordv[i]=(uint8_t)t;
 174                         }
 175
 176                 }
 177                 SET_POS(dest);
 178                 dest->length_B = i;
 179                 bigint_adjust(dest);
 180         }
 181 }
 182
 183 /******************************************************************************/
 184
 185 int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){
 186         if(a->length_B > b->length_B){
 187                 return 1;
 188         }
 189         if(a->length_B < b->length_B){
 190                 return -1;
 191         }
 192         if(a->length_B==0){
 193                 return 0;
 194         }
 195         uint16_t i;
 196         i = a->length_B-1;
 197         do{
 198                 if(a->wordv[i]!=b->wordv[i]){
 199                         if(a->wordv[i]>b->wordv[i]){
 200                                 return 1;
 201                         }else{
 202                                 return -1;
 203                         }
 204                 }
 205         }while(i--);
 206         return 0;
 207 }
 208
 209 /******************************************************************************/
 210
 211 void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 212         uint8_t s;
 213         s  = GET_SIGN(a)?2:0;
 214         s |= GET_SIGN(b)?1:0;
 215         switch(s){
 216                 case 0: /* both positive */
 217                         bigint_add_u(dest, a,b);
 218                         SET_POS(dest);
 219                         break;
 220                 case 1: /* a positive, b negative */
 221                         bigint_sub_u(dest, a, b);
 222                         break;
 223                 case 2: /* a negative, b positive */
 224                         bigint_sub_u(dest, b, a);
 225                         break;
 226                 case 3: /* both negative */
 227                         bigint_add_u(dest, a, b);
 228                         SET_NEG(dest);
 229                         break;
 230                 default: /* how can this happen?*/
 231                         break;
 232         }
 233 }
 234
 235 /******************************************************************************/
 236
 237 void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 238         uint8_t s;
 239         s  = GET_SIGN(a)?2:0;
 240         s |= GET_SIGN(b)?1:0;
 241         switch(s){
 242                 case 0: /* both positive */
 243                         bigint_sub_u(dest, a,b);
 244                         break;
 245                 case 1: /* a positive, b negative */
 246                         bigint_add_u(dest, a, b);
 247                         SET_POS(dest);
 248                         break;
 249                 case 2: /* a negative, b positive */
 250                         bigint_add_u(dest, a, b);
 251                         SET_NEG(dest);
 252                         break;
 253                 case 3: /* both negative */
 254                         bigint_sub_u(dest, b, a);
 255                         break;
 256                 default: /* how can this happen?*/
 257                                         break;
 258         }
 259
 260 }
 261
 262 /******************************************************************************/
 263
 264 int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){
 265         uint8_t s;
 266         if(a->length_B==0 && b->length_B==0){
 267                 return 0;
 268         }
 269         s  = GET_SIGN(a)?2:0;
 270         s |= GET_SIGN(b)?1:0;
 271         switch(s){
 272                 case 0: /* both positive */
 273                         return bigint_cmp_u(a, b);
 274                         break;
 275                 case 1: /* a positive, b negative */
 276                         return 1;
 277                         break;
 278                 case 2: /* a negative, b positive */
 279                         return -1;
 280                         break;
 281                 case 3: /* both negative */
 282                         return bigint_cmp_u(b, a);
 283                         break;
 284                 default: /* how can this happen?*/
 285                                         break;
 286         }
 287         return 0; /* just to satisfy the compiler */
 288 }
 289
 290 /******************************************************************************/
 291
 292 void bigint_shiftleft(bigint_t* a, uint16_t shift){
 293         uint16_t byteshift;
 294         uint16_t i;
 295         uint8_t bitshift;
 296         uint16_t t=0;
 297         byteshift = (shift+3)/8;
 298         bitshift = shift&7;
 299         memmove(a->wordv+byteshift, a->wordv, a->length_B);
 300         memset(a->wordv, 0, byteshift);
 301         if(bitshift!=0){
 302                 if(bitshift<=4){ /* shift to the left */
 303                         for(i=byteshift; i<a->length_B+byteshift; ++i){
 304                                 t |= (a->wordv[i])<<bitshift;
 305                                 a->wordv[i] = (uint8_t)t;
 306                                 t >>= 8;
 307                         }
 308                         a->wordv[i] = (uint8_t)t;
 309                         byteshift++;
 310                 }else{ /* shift to the right */
 311                         for(i=a->length_B+byteshift-1; i>byteshift-1; --i){
 312                                 t |= (a->wordv[i])<<(bitshift);
 313                                 a->wordv[i] = (uint8_t)(t>>8);
 314                                 t <<= 8;
 315                         }
 316                         t |= (a->wordv[i])<<(bitshift);
 317                         a->wordv[i] = (uint8_t)(t>>8);
 318                 }
 319         }
 320         a->length_B += byteshift;
 321         bigint_adjust(a);
 322 }
 323
 324 /******************************************************************************/
 325
 326 void bigint_shiftright(bigint_t* a, uint16_t shift){
 327         uint16_t byteshift;
 328         uint16_t i;
 329         uint8_t bitshift;
 330         uint16_t t=0;
 331         byteshift = shift/8;
 332         bitshift = shift&7;
 333         if(byteshift >= a->length_B){ /* we would shift out more than we have */
 334                 bigint_set_zero(a);
 335                 return;
 336         }
 337         if(byteshift == a->length_B-1 && bitshift>GET_FBS(a)){
 338                 bigint_set_zero(a);
 339                 return;
 340         }
 341         if(byteshift){
 342                 memmove(a->wordv, a->wordv+byteshift, a->length_B-byteshift);
 343                 memset(a->wordv+a->length_B-byteshift, 0,  byteshift);
 344         }
 345         if(bitshift!=0){
 346          /* shift to the right */
 347                 for(i=a->length_B-byteshift-1; i>0; --i){
 348                         t |= (a->wordv[i])<<(8-bitshift);
 349                         a->wordv[i] = (uint8_t)(t>>8);
 350                         t <<= 8;
 351                 }
 352                 t |= (a->wordv[0])<<(8-bitshift);
 353                 a->wordv[0] = (uint8_t)(t>>8);
 354         }
 355         a->length_B -= byteshift;
 356         bigint_adjust(a);
 357 }
 358
 359 /******************************************************************************/
 360
 361 void bigint_xor(bigint_t* dest, const bigint_t* a){
 362         uint16_t i;
 363         for(i=0; i<a->length_B; ++i){
 364                 dest->wordv[i] ^= a->wordv[i];
 365         }
 366         bigint_adjust(dest);
 367 }
 368
 369 /******************************************************************************/
 370
 371 void bigint_set_zero(bigint_t* a){
 372         a->length_B=0;
 373 }
 374
 375 /******************************************************************************/
 376
 377 /* using the Karatsuba-Algorithm */
 378 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
 379 void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 380         if(a->length_B==0 || b->length_B==0){
 381                 bigint_set_zero(dest);
 382                 return;
 383         }
 384         if(dest==a || dest==b){
 385                 bigint_t d;
 386                 uint8_t d_b[a->length_B+b->length_B];
 387                 d.wordv = d_b;
 388                 bigint_mul_u(&d, a, b);
 389                 bigint_copy(dest, &d);
 390                 return;
 391         }
 392         if(a->length_B==1 || b->length_B==1){
 393                 if(a->length_B!=1){
 394                         XCHG_PTR(a,b);
 395                 }
 396                 uint16_t i, t=0;
 397                 uint8_t x = a->wordv[0];
 398                 for(i=0; i<b->length_B; ++i){
 399                         t += b->wordv[i]*x;
 400                         dest->wordv[i] = (uint8_t)t;
 401                         t>>=8;
 402                 }
 403                 dest->wordv[i] = (uint8_t)t;
 404                 dest->length_B=i+1;
 405                 bigint_adjust(dest);
 406                 return;
 407         }
 408         if(a->length_B<=4 && b->length_B<=4){
 409                 uint32_t p=0, q=0;
 410                 uint64_t r;
 411                 memcpy(&p, a->wordv, a->length_B);
 412                 memcpy(&q, b->wordv, b->length_B);
 413                 r = (uint64_t)p*(uint64_t)q;
 414                 memcpy(dest->wordv, &r, a->length_B+b->length_B);
 415                 dest->length_B =  a->length_B+b->length_B;
 416                 bigint_adjust(dest);
 417                 return;
 418         }
 419         bigint_set_zero(dest);
 420         /* split a in xh & xl; split b in yh & yl */
 421         uint16_t n;
 422         n=(MAX(a->length_B, b->length_B)+1)/2;
 423         bigint_t xl, xh, yl, yh;
 424         xl.wordv = a->wordv;
 425         yl.wordv = b->wordv;
 426         if(a->length_B<=n){
 427                 xh.info=0;
 428                 xh.length_B = 0;
 429                 xl.length_B = a->length_B;
 430                 xl.info = 0;
 431         }else{
 432                 xl.length_B=n;
 433                 xl.info = 0;
 434                 bigint_adjust(&xl);
 435                 xh.wordv = a->wordv+n;
 436                 xh.length_B = a->length_B-n;
 437                 xh.info = 0;
 438         }
 439         if(b->length_B<=n){
 440                 yh.info=0;
 441                 yh.length_B = 0;
 442                 yl.length_B = b->length_B;
 443                 yl.info = b->info;
 444         }else{
 445                 yl.length_B=n;
 446                 yl.info = 0;
 447                 bigint_adjust(&yl);
 448                 yh.wordv = b->wordv+n;
 449                 yh.length_B = b->length_B-n;
 450                 yh.info = 0;
 451         }
 452         /* now we have split up a and b */
 453         uint8_t  tmp_b[2*n+2], m_b[2*(n+1)];
 454         bigint_t tmp, tmp2, m;
 455         tmp.wordv = tmp_b;
 456         tmp2.wordv = tmp_b+n+1;
 457         m.wordv = m_b;
 458
 459         bigint_mul_u(dest, &xl, &yl);  /* dest <= xl*yl     */
 460         bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl     */
 461         bigint_add_u(&tmp, &yh, &yl);  /* tmp  <= yh+yl     */
 462         bigint_mul_u(&m, &tmp2, &tmp); /* m    <= tmp2*tmp  */
 463         bigint_mul_u(&tmp, &xh, &yh);  /* h    <= xh*yh     */
 464         bigint_sub_u(&m, &m, dest);    /* m    <= m-dest    */
 465     bigint_sub_u(&m, &m, &tmp);    /* m    <= m-h       */
 466         bigint_add_scale_u(dest, &m, n);
 467         bigint_add_scale_u(dest, &tmp, 2*n);
 468 }
 469
 470 /******************************************************************************/
 471
 472 void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){
 473         uint8_t s;
 474         s  = GET_SIGN(a)?2:0;
 475         s |= GET_SIGN(b)?1:0;
 476         switch(s){
 477                 case 0: /* both positive */
 478                         bigint_mul_u(dest, a,b);
 479                         SET_POS(dest);
 480                         break;
 481                 case 1: /* a positive, b negative */
 482                         bigint_mul_u(dest, a,b);
 483                         SET_NEG(dest);
 484                         break;
 485                 case 2: /* a negative, b positive */
 486                         bigint_mul_u(dest, a,b);
 487                         SET_NEG(dest);
 488                         break;
 489                 case 3: /* both negative */
 490                         bigint_mul_u(dest, a,b);
 491                         SET_POS(dest);
 492                         break;
 493                 default: /* how can this happen?*/
 494                         break;
 495         }
 496 }
 497
 498 /******************************************************************************/
 499
 500 /* square */
 501 /* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */
 502 void bigint_square(bigint_t* dest, const bigint_t* a){
 503         if(a->length_B<=4){
 504                 uint64_t r=0;
 505                 memcpy(&r, a->wordv, a->length_B);
 506                 r = r*r;
 507                 memcpy(dest->wordv, &r, 2*a->length_B);
 508                 SET_POS(dest);
 509                 dest->length_B=2*a->length_B;
 510                 bigint_adjust(dest);
 511                 return;
 512         }
 513         if(dest==a){
 514                 bigint_t d;
 515                 uint8_t d_b[a->length_B*2];
 516                 d.wordv = d_b;
 517                 bigint_square(&d, a);
 518                 bigint_copy(dest, &d);
 519                 return;
 520         }
 521         uint16_t n;
 522         n=(a->length_B+1)/2;
 523         bigint_t xh, xl, tmp; /* x-high, x-low, temp */
 524         uint8_t buffer[2*n+1];
 525         xl.wordv = a->wordv;
 526         xl.length_B = n;
 527         xh.wordv = a->wordv+n;
 528         xh.length_B = a->length_B-n;
 529         tmp.wordv = buffer;
 530         bigint_square(dest, &xl);
 531         bigint_square(&tmp, &xh);
 532         bigint_add_scale_u(dest, &tmp, 2*n);
 533         bigint_mul_u(&tmp, &xl, &xh);
 534         bigint_shiftleft(&tmp, 1);
 535         bigint_add_scale_u(dest, &tmp, n);
 536 }
 537
 538 /******************************************************************************/
 539
 540 void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
 541         bigint_t tmp;
 542         uint8_t tmp_b[b->length_B+1];
 543         uint16_t i,j,byteshift=bitscale/8;
 544         uint8_t borrow=0;
 545         int16_t t;
 546
 547         if(a->length_B < b->length_B+byteshift){
 548                 bigint_set_zero(a);
 549                 return;
 550         }
 551
 552         tmp.wordv = tmp_b;
 553         bigint_copy(&tmp, b);
 554         bigint_shiftleft(&tmp, bitscale&7);
 555
 556         for(j=0,i=byteshift; i<tmp.length_B+byteshift; ++i, ++j){
 557                 t = a->wordv[i] - tmp.wordv[j] - borrow;
 558                 a->wordv[i] = (uint8_t)t;
 559                 if(t<0){
 560                         borrow = 1;
 561                 }else{
 562                         borrow = 0;
 563                 }
 564         }
 565         while(borrow){
 566                 if(i+1 > a->length_B){
 567                         bigint_set_zero(a);
 568                         return;
 569                 }
 570                 a->wordv[i] -= borrow;
 571                 if(a->wordv[i]!=0xff){
 572                         borrow=0;
 573                 }
 574                 ++i;
 575         }
 576         bigint_adjust(a);
 577 }
 578
 579 /******************************************************************************/
 580
 581 void bigint_reduce(bigint_t* a, const bigint_t* r){
 582 //      bigint_adjust(r);
 583         uint8_t rfbs = GET_FBS(r);
 584
 585         if(r->length_B==0 || a->length_B==0){
 586                 return;
 587         }
 588         while(a->length_B > r->length_B){
 589                 bigint_sub_u_bitscale(a, r, (a->length_B-r->length_B)*8+GET_FBS(a)-rfbs-1);
 590         }
 591         while((GET_FBS(a) > rfbs+1) && (a->length_B == r->length_B)){
 592                 bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1);
 593         }
 594         while(bigint_cmp_u(a,r)>=0){
 595                 bigint_sub_u(a,a,r);
 596         }
 597         bigint_adjust(a);
 598 }
 599
 600 /******************************************************************************/
 601
 602 /* calculate dest = a**exp % r */
 603 /* using square&multiply */
 604 void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
 605         if(a->length_B==0 || r->length_B==0){
 606                 return;
 607         }
 608
 609         bigint_t res, base;
 610         uint8_t base_b[MAX(a->length_B,r->length_B*2)], res_b[r->length_B*2];
 611         uint16_t i;
 612         uint8_t j, t;
 613         res.wordv = res_b;
 614         base.wordv = base_b;
 615         bigint_copy(&base, a);
 616         bigint_reduce(&base, r);
 617         res.wordv[0]=1;
 618         res.length_B=1;
 619         res.info = 0;
 620         bigint_adjust(&res);
 621         for(i=0; i+1<exp->length_B; ++i){
 622                 t=exp->wordv[i];
 623                 for(j=0; j<8; ++j){
 624                         if(t&1){
 625                                 bigint_mul_u(&res, &res, &base);
 626                                 bigint_reduce(&res, r);
 627                         }
 628                         bigint_square(&base, &base);
 629                         bigint_reduce(&base, r);
 630                         t>>=1;
 631                 }
 632         }
 633         t=exp->wordv[i];
 634         while(t){
 635                 if(t&1){
 636                         bigint_mul_u(&res, &res, &base);
 637                         bigint_reduce(&res, r);
 638                 }
 639                 bigint_square(&base, &base);
 640                 bigint_reduce(&base, r);
 641                 t>>=1;
 642         }
 643         SET_POS(&res);
 644         bigint_copy(dest, &res);
 645 }
 646
 647 /******************************************************************************/
 648 /* gcd <-- gcd(x,y) a*x+b*y=gcd */
 649 void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){
 650          bigint_t g, x_, y_, u, v, a_, b_, c_, d_;
 651          volatile uint16_t i=0;
 652          if(x->length_B==0 || y->length_B==0){
 653                  return;
 654          }
 655          while(x->wordv[i]==0 && y->wordv[i]==0){
 656                  ++i;
 657          }
 658          uint8_t g_b[i+2], x_b[x->length_B-i], y_b[y->length_B-i];
 659          uint8_t u_b[x->length_B-i], v_b[y->length_B-i];
 660          uint8_t a_b[y->length_B+2], c_b[y->length_B+2];
 661          uint8_t b_b[x->length_B+2], d_b[x->length_B+2];
 662
 663          g.wordv = g_b;
 664          x_.wordv = x_b;
 665          y_.wordv = y_b;
 666          memset(g_b, 0, i);
 667          g_b[i]=1;
 668          g.length_B = i+1;
 669          g.info=0;
 670          x_.info = y_.info = 0;
 671          x_.length_B = x->length_B-i;
 672          y_.length_B = y->length_B-i;
 673          memcpy(x_.wordv, x->wordv+i, x_.length_B);
 674          memcpy(y_.wordv, y->wordv+i, y_.length_B);
 675          for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
 676          }
 677
 678          bigint_adjust(&x_);
 679          bigint_adjust(&y_);
 680
 681          if(i){
 682                  bigint_shiftleft(&g, i);
 683                  bigint_shiftright(&x_, i);
 684                  bigint_shiftright(&y_, i);
 685          }
 686          u.wordv = u_b;
 687          v.wordv = v_b;
 688          a_.wordv = a_b;
 689          b_.wordv = b_b;
 690          c_.wordv = c_b;
 691          d_.wordv = d_b;
 692
 693          bigint_copy(&u, &x_);
 694          bigint_copy(&v, &y_);
 695          a_.wordv[0] = 1;
 696          a_.length_B = 1;
 697          a_.info = 0;
 698          d_.wordv[0] = 1;
 699          d_.length_B = 1;
 700          d_.info = 0;
 701          bigint_set_zero(&b_);
 702          bigint_set_zero(&c_);
 703          do{
 704                  while((u.wordv[0]&1)==0){
 705                          bigint_shiftright(&u, 1);
 706                          if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
 707                                  bigint_add_s(&a_, &a_, &y_);
 708                                  bigint_sub_s(&b_, &b_, &x_);
 709                          }
 710                          bigint_shiftright(&a_, 1);
 711                          bigint_shiftright(&b_, 1);
 712                  }
 713                  while((v.wordv[0]&1)==0){
 714                          bigint_shiftright(&v, 1);
 715                          if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
 716                                  bigint_add_s(&c_, &c_, &y_);
 717                                  bigint_sub_s(&d_, &d_, &x_);
 718                          }
 719                          bigint_shiftright(&c_, 1);
 720                          bigint_shiftright(&d_, 1);
 721
 722                  }
 723                  if(bigint_cmp_u(&u, &v)>=0){
 724                         bigint_sub_u(&u, &u, &v);
 725                         bigint_sub_s(&a_, &a_, &c_);
 726                         bigint_sub_s(&b_, &b_, &d_);
 727                  }else{
 728                         bigint_sub_u(&v, &v, &u);
 729                         bigint_sub_s(&c_, &c_, &a_);
 730                         bigint_sub_s(&d_, &d_, &b_);
 731                  }
 732          }while(u.length_B);
 733          if(gcd){
 734                  bigint_mul_s(gcd, &v, &g);
 735          }
 736          if(a){
 737                 bigint_copy(a, &c_);
 738          }
 739          if(b){
 740                  bigint_copy(b, &d_);
 741          }
 742 }
 743
 744 /******************************************************************************/
 745
 746 void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
 747         bigint_gcdext(NULL, dest, NULL, a, m);
 748         while(dest->info&BIGINT_NEG_MASK){
 749                 bigint_add_s(dest, dest, m);
 750         }
 751 }
 752
 753 /******************************************************************************/
 754
 755 void bigint_changeendianess(bigint_t* a){
 756         uint8_t t, *p, *q;
 757         p = a->wordv;
 758         q = p+a->length_B-1;
 759         while(p<q){
 760                 t = *p;
 761                 *p = *q;
 762                 *q = t;
 763                 ++p; --q;
 764         }
 765 }
 766
 767 /******************************************************************************/
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790