crypto/bn/bn_exp.c

   1 /* crypto/bn/bn_exp.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62 #ifdef ATALLA
  63 # include <alloca.h>
  64 # include <atasi.h>
  65 # include <assert.h>
  66 # include <dlfcn.h>
  67 #endif
  68
  69 #define TABLE_SIZE      16
  70
  71 /* slow but works */
  72 int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  73         {
  74         BIGNUM *t;
  75         int r=0;
  76
  77         bn_check_top(a);
  78         bn_check_top(b);
  79         bn_check_top(m);
  80
  81         BN_CTX_start(ctx);
  82         if ((t = BN_CTX_get(ctx)) == NULL) goto err;
  83         if (a == b)
  84                 { if (!BN_sqr(t,a,ctx)) goto err; }
  85         else
  86                 { if (!BN_mul(t,a,b,ctx)) goto err; }
  87         if (!BN_mod(ret,t,m,ctx)) goto err;
  88         r=1;
  89 err:
  90         BN_CTX_end(ctx);
  91         return(r);
  92         }
  93
  94 #if 0
  95 /* this one works - simple but works */
  96 int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
  97         {
  98         int i,bits,ret=0;
  99         BIGNUM *v,*tmp;
 100
 101         BN_CTX_start(ctx);
 102         v = BN_CTX_get(ctx);
 103         tmp = BN_CTX_get(ctx);
 104         if (v == NULL || tmp == NULL) goto err;
 105
 106         if (BN_copy(v,a) == NULL) goto err;
 107         bits=BN_num_bits(p);
 108
 109         if (BN_is_odd(p))
 110                 { if (BN_copy(r,a) == NULL) goto err; }
 111         else    { if (!BN_one(r)) goto err; }
 112
 113         for (i=1; i<bits; i++)
 114                 {
 115                 if (!BN_sqr(tmp,v,ctx)) goto err;
 116                 if (!BN_mod(v,tmp,m,ctx)) goto err;
 117                 if (BN_is_bit_set(p,i))
 118                         {
 119                         if (!BN_mul(tmp,r,v,ctx)) goto err;
 120                         if (!BN_mod(r,tmp,m,ctx)) goto err;
 121                         }
 122                 }
 123         ret=1;
 124 err:
 125         BN_CTX_end(ctx);
 126         return(ret);
 127         }
 128
 129 #endif
 130
 131 /* this one works - simple but works */
 132 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
 133         {
 134         int i,bits,ret=0;
 135         BIGNUM *v,*rr;
 136
 137         BN_CTX_start(ctx);
 138         if ((r == a) || (r == p))
 139                 rr = BN_CTX_get(ctx);
 140         else
 141                 rr = r;
 142         if ((v = BN_CTX_get(ctx)) == NULL) goto err;
 143
 144         if (BN_copy(v,a) == NULL) goto err;
 145         bits=BN_num_bits(p);
 146
 147         if (BN_is_odd(p))
 148                 { if (BN_copy(rr,a) == NULL) goto err; }
 149         else    { if (!BN_one(rr)) goto err; }
 150
 151         for (i=1; i<bits; i++)
 152                 {
 153                 if (!BN_sqr(v,v,ctx)) goto err;
 154                 if (BN_is_bit_set(p,i))
 155                         {
 156                         if (!BN_mul(rr,rr,v,ctx)) goto err;
 157                         }
 158                 }
 159         ret=1;
 160 err:
 161         if (r != rr) BN_copy(r,rr);
 162         BN_CTX_end(ctx);
 163         return(ret);
 164         }
 165
 166 #ifdef ATALLA
 167
 168 /*
 169  * This routine will dynamically check for the existance of an Atalla AXL-200
 170  * SSL accelerator module.  If one is found, the variable
 171  * asi_accelerator_present is set to 1 and the function pointers
 172  * ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls.
 173  */
 174 typedef int tfnASI_GetPerformanceStatistics(int reset_flag,
 175                                             unsigned int *ret_buf);
 176 typedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf);
 177 typedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey,
 178                                      unsigned char *output,
 179                                      unsigned char *input,
 180                                      unsigned int modulus_len);
 181
 182 static tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig;
 183 static tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn;
 184 static tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics;
 185 static int asi_accelerator_present;
 186 static int tried_atalla;
 187
 188 void atalla_initialize_accelerator_handle(void)
 189         {
 190         void *dl_handle;
 191         int status;
 192         unsigned int config_buf[1024];
 193         static int tested;
 194
 195         if(tested)
 196                 return;
 197
 198         tested=1;
 199
 200         bzero((void *)config_buf, 1024);
 201
 202         /*
 203          * Check to see if the library is present on the system
 204          */
 205         dl_handle = dlopen("atasi.so", RTLD_NOW);
 206         if (dl_handle == (void *) NULL)
 207                 {
 208 /*              printf("atasi.so library is not present on the system\n");
 209                 printf("No HW acceleration available\n");*/
 210                 return;
 211                 }
 212
 213         /*
 214          * The library is present.  Now we'll check to insure that the
 215          * LDM is up and running. First we'll get the address of the
 216          * function in the atasi library that we need to see if the
 217          * LDM is operating.
 218          */
 219
 220         ptr_ASI_GetHardwareConfig =
 221           (tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig");
 222
 223         if (ptr_ASI_GetHardwareConfig)
 224                 {
 225                 /*
 226                  * We found the call, now we'll get our config
 227                  * status.  If we get a non 0 result, the LDM is not
 228                  * running and we cannot use the Atalla ASI *
 229                  * library.
 230                  */
 231                 status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf);
 232                 if (status != 0)
 233                         {
 234                         printf("atasi.so library is present but not initialized\n");
 235                         printf("No HW acceleration available\n");
 236                         return;
 237                         }
 238                 }
 239         else
 240                 {
 241 /*              printf("We found the library, but not the function. Very Strange!\n");*/
 242                 return ;
 243                 }
 244
 245         /*
 246          * It looks like we have acceleration capabilities.  Load up the
 247          * pointers to our ASI API calls.
 248          */
 249         ptr_ASI_RSAPrivateKeyOpFn=
 250           (tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn");
 251         if (ptr_ASI_RSAPrivateKeyOpFn == NULL)
 252                 {
 253 /*              printf("We found the library, but no RSA function. Very Strange!\n");*/
 254                 return;
 255                 }
 256
 257         ptr_ASI_GetPerformanceStatistics =
 258           (tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics");
 259         if (ptr_ASI_GetPerformanceStatistics == NULL)
 260                 {
 261 /*              printf("We found the library, but no stat function. Very Strange!\n");*/
 262                 return;
 263               }
 264
 265         /*
 266          * Indicate that acceleration is available
 267          */
 268         asi_accelerator_present = 1;
 269
 270 /*      printf("This system has acceleration!\n");*/
 271
 272         return;
 273         }
 274
 275 /* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */
 276 int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
 277         {
 278         unsigned char *abin;
 279         unsigned char *pbin;
 280         unsigned char *mbin;
 281         unsigned char *rbin;
 282         int an,pn,mn,ret;
 283         RSAPrivateKey keydata;
 284
 285         atalla_initialize_accelerator_handle();
 286         if(!asi_accelerator_present)
 287                 return 0;
 288
 289
 290 /* We should be able to run without size testing */
 291 # define ASIZE  128
 292         an=BN_num_bytes(a);
 293         pn=BN_num_bytes(p);
 294         mn=BN_num_bytes(m);
 295
 296         if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE)
 297             {
 298             int size=mn;
 299
 300             assert(an <= mn);
 301             abin=alloca(size);
 302             memset(abin,'\0',mn);
 303             BN_bn2bin(a,abin+size-an);
 304
 305             pbin=alloca(pn);
 306             BN_bn2bin(p,pbin);
 307
 308             mbin=alloca(size);
 309             memset(mbin,'\0',mn);
 310             BN_bn2bin(m,mbin+size-mn);
 311
 312             rbin=alloca(size);
 313
 314             memset(&keydata,'\0',sizeof keydata);
 315             keydata.privateExponent.data=pbin;
 316             keydata.privateExponent.len=pn;
 317             keydata.modulus.data=mbin;
 318             keydata.modulus.len=size;
 319
 320             ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len);
 321 /*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/
 322             if(!ret)
 323                 {
 324                 BN_bin2bn(rbin,keydata.modulus.len,r);
 325 /*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/
 326                 return 1;
 327                 }
 328             }
 329         return 0;
 330         }
 331 #endif /* def ATALLA */
 332
 333 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 334                BN_CTX *ctx)
 335         {
 336         int ret;
 337
 338         bn_check_top(a);
 339         bn_check_top(p);
 340         bn_check_top(m);
 341
 342 #ifdef ATALLA
 343         if(BN_mod_exp_atalla(r,a,p,m))
 344             return 1;
 345 /* If it fails, try the other methods (but don't try atalla again) */
 346         tried_atalla=1;
 347 #endif
 348
 349 #ifdef MONT_MUL_MOD
 350         /* I have finally been able to take out this pre-condition of
 351          * the top bit being set.  It was caused by an error in BN_div
 352          * with negatives.  There was also another problem when for a^b%m
 353          * a >= m.  eay 07-May-97 */
 354 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 355
 356         if (BN_is_odd(m))
 357                 { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
 358         else
 359 #endif
 360 #ifdef RECP_MUL_MOD
 361                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
 362 #else
 363                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 364 #endif
 365
 366 #ifdef ATALLA
 367         tried_atalla=0;
 368 #endif
 369
 370         return(ret);
 371         }
 372
 373 /* #ifdef RECP_MUL_MOD */
 374 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 375                     const BIGNUM *m, BN_CTX *ctx)
 376         {
 377         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 378         int start=1,ts=0;
 379         BIGNUM *aa;
 380         BIGNUM val[TABLE_SIZE];
 381         BN_RECP_CTX recp;
 382
 383         bits=BN_num_bits(p);
 384
 385         if (bits == 0)
 386                 {
 387                 BN_one(r);
 388                 return(1);
 389                 }
 390
 391         BN_CTX_start(ctx);
 392         if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
 393
 394         BN_RECP_CTX_init(&recp);
 395         if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
 396
 397         BN_init(&(val[0]));
 398         ts=1;
 399
 400         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 401         if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
 402                 goto err;                               /* 2 */
 403
 404         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 405                 window=1;
 406         else if (bits >= 256)
 407                 window=5;       /* max size of window */
 408         else if (bits >= 128)
 409                 window=4;
 410         else
 411                 window=3;
 412
 413         j=1<<(window-1);
 414         for (i=1; i<j; i++)
 415                 {
 416                 BN_init(&val[i]);
 417                 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
 418                         goto err;
 419                 }
 420         ts=i;
 421
 422         start=1;        /* This is used to avoid multiplication etc
 423                          * when there is only the value '1' in the
 424                          * buffer. */
 425         wvalue=0;       /* The 'value' of the window */
 426         wstart=bits-1;  /* The top bit of the window */
 427         wend=0;         /* The bottom bit of the window */
 428
 429         if (!BN_one(r)) goto err;
 430
 431         for (;;)
 432                 {
 433                 if (BN_is_bit_set(p,wstart) == 0)
 434                         {
 435                         if (!start)
 436                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 437                                 goto err;
 438                         if (wstart == 0) break;
 439                         wstart--;
 440                         continue;
 441                         }
 442                 /* We now have wstart on a 'set' bit, we now need to work out
 443                  * how bit a window to do.  To do this we need to scan
 444                  * forward until the last set bit before the end of the
 445                  * window */
 446                 j=wstart;
 447                 wvalue=1;
 448                 wend=0;
 449                 for (i=1; i<window; i++)
 450                         {
 451                         if (wstart-i < 0) break;
 452                         if (BN_is_bit_set(p,wstart-i))
 453                                 {
 454                                 wvalue<<=(i-wend);
 455                                 wvalue|=1;
 456                                 wend=i;
 457                                 }
 458                         }
 459
 460                 /* wend is the size of the current window */
 461                 j=wend+1;
 462                 /* add the 'bytes above' */
 463                 if (!start)
 464                         for (i=0; i<j; i++)
 465                                 {
 466                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 467                                         goto err;
 468                                 }
 469
 470                 /* wvalue will be an odd number < 2^window */
 471                 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
 472                         goto err;
 473
 474                 /* move the 'window' down further */
 475                 wstart-=wend+1;
 476                 wvalue=0;
 477                 start=0;
 478                 if (wstart < 0) break;
 479                 }
 480         ret=1;
 481 err:
 482         BN_CTX_end(ctx);
 483         for (i=0; i<ts; i++)
 484                 BN_clear_free(&(val[i]));
 485         BN_RECP_CTX_free(&recp);
 486         return(ret);
 487         }
 488 /* #endif */
 489
 490 /* #ifdef MONT_MUL_MOD */
 491 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
 492                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
 493         {
 494         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 495         int start=1,ts=0;
 496         BIGNUM *d,*r;
 497         BIGNUM *aa;
 498         BIGNUM val[TABLE_SIZE];
 499         BN_MONT_CTX *mont=NULL;
 500
 501         bn_check_top(a);
 502         bn_check_top(p);
 503         bn_check_top(m);
 504
 505 #ifdef ATALLA
 506         if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m))
 507             return 1;
 508 /* If it fails, try the other methods */
 509 #endif
 510
 511         if (!(m->d[0] & 1))
 512                 {
 513                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
 514                 return(0);
 515                 }
 516         bits=BN_num_bits(p);
 517         if (bits == 0)
 518                 {
 519                 BN_one(rr);
 520                 return(1);
 521                 }
 522         BN_CTX_start(ctx);
 523         d = BN_CTX_get(ctx);
 524         r = BN_CTX_get(ctx);
 525         if (d == NULL || r == NULL) goto err;
 526
 527         /* If this is not done, things will break in the montgomery
 528          * part */
 529
 530 #if 1
 531         if (in_mont != NULL)
 532                 mont=in_mont;
 533         else
 534 #endif
 535                 {
 536                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
 537                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
 538                 }
 539
 540         BN_init(&val[0]);
 541         ts=1;
 542         if (BN_ucmp(a,m) >= 0)
 543                 {
 544                 BN_mod(&(val[0]),a,m,ctx);
 545                 aa= &(val[0]);
 546                 }
 547         else
 548                 aa=a;
 549         if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
 550         if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
 551
 552         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
 553                 window=1;
 554         else if (bits >= 256)
 555                 window=5;       /* max size of window */
 556         else if (bits >= 128)
 557                 window=4;
 558         else
 559                 window=3;
 560
 561         j=1<<(window-1);
 562         for (i=1; i<j; i++)
 563                 {
 564                 BN_init(&(val[i]));
 565                 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
 566                         goto err;
 567                 }
 568         ts=i;
 569
 570         start=1;        /* This is used to avoid multiplication etc
 571                          * when there is only the value '1' in the
 572                          * buffer. */
 573         wvalue=0;       /* The 'value' of the window */
 574         wstart=bits-1;  /* The top bit of the window */
 575         wend=0;         /* The bottom bit of the window */
 576
 577         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 578         for (;;)
 579                 {
 580                 if (BN_is_bit_set(p,wstart) == 0)
 581                         {
 582                         if (!start)
 583                                 {
 584                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 585                                 goto err;
 586                                 }
 587                         if (wstart == 0) break;
 588                         wstart--;
 589                         continue;
 590                         }
 591                 /* We now have wstart on a 'set' bit, we now need to work out
 592                  * how bit a window to do.  To do this we need to scan
 593                  * forward until the last set bit before the end of the
 594                  * window */
 595                 j=wstart;
 596                 wvalue=1;
 597                 wend=0;
 598                 for (i=1; i<window; i++)
 599                         {
 600                         if (wstart-i < 0) break;
 601                         if (BN_is_bit_set(p,wstart-i))
 602                                 {
 603                                 wvalue<<=(i-wend);
 604                                 wvalue|=1;
 605                                 wend=i;
 606                                 }
 607                         }
 608
 609                 /* wend is the size of the current window */
 610                 j=wend+1;
 611                 /* add the 'bytes above' */
 612                 if (!start)
 613                         for (i=0; i<j; i++)
 614                                 {
 615                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 616                                         goto err;
 617                                 }
 618
 619                 /* wvalue will be an odd number < 2^window */
 620                 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
 621                         goto err;
 622
 623                 /* move the 'window' down further */
 624                 wstart-=wend+1;
 625                 wvalue=0;
 626                 start=0;
 627                 if (wstart < 0) break;
 628                 }
 629         BN_from_montgomery(rr,r,mont,ctx);
 630         ret=1;
 631 err:
 632         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 633         BN_CTX_end(ctx);
 634         for (i=0; i<ts; i++)
 635                 BN_clear_free(&(val[i]));
 636         return(ret);
 637         }
 638 /* #endif */
 639
 640 /* The old fallback, simple version :-) */
 641 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
 642              BN_CTX *ctx)
 643         {
 644         int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
 645         int start=1;
 646         BIGNUM *d;
 647         BIGNUM val[TABLE_SIZE];
 648
 649         bits=BN_num_bits(p);
 650
 651         if (bits == 0)
 652                 {
 653                 BN_one(r);
 654                 return(1);
 655                 }
 656
 657         BN_CTX_start(ctx);
 658         if ((d = BN_CTX_get(ctx)) == NULL) goto err;
 659
 660         BN_init(&(val[0]));
 661         ts=1;
 662         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 663         if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
 664                 goto err;                               /* 2 */
 665
 666         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 667                 window=1;
 668         else if (bits >= 256)
 669                 window=5;       /* max size of window */
 670         else if (bits >= 128)
 671                 window=4;
 672         else
 673                 window=3;
 674
 675         j=1<<(window-1);
 676         for (i=1; i<j; i++)
 677                 {
 678                 BN_init(&(val[i]));
 679                 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
 680                         goto err;
 681                 }
 682         ts=i;
 683
 684         start=1;        /* This is used to avoid multiplication etc
 685                          * when there is only the value '1' in the
 686                          * buffer. */
 687         wvalue=0;       /* The 'value' of the window */
 688         wstart=bits-1;  /* The top bit of the window */
 689         wend=0;         /* The bottom bit of the window */
 690
 691         if (!BN_one(r)) goto err;
 692
 693         for (;;)
 694                 {
 695                 if (BN_is_bit_set(p,wstart) == 0)
 696                         {
 697                         if (!start)
 698                                 if (!BN_mod_mul(r,r,r,m,ctx))
 699                                 goto err;
 700                         if (wstart == 0) break;
 701                         wstart--;
 702                         continue;
 703                         }
 704                 /* We now have wstart on a 'set' bit, we now need to work out
 705                  * how bit a window to do.  To do this we need to scan
 706                  * forward until the last set bit before the end of the
 707                  * window */
 708                 j=wstart;
 709                 wvalue=1;
 710                 wend=0;
 711                 for (i=1; i<window; i++)
 712                         {
 713                         if (wstart-i < 0) break;
 714                         if (BN_is_bit_set(p,wstart-i))
 715                                 {
 716                                 wvalue<<=(i-wend);
 717                                 wvalue|=1;
 718                                 wend=i;
 719                                 }
 720                         }
 721
 722                 /* wend is the size of the current window */
 723                 j=wend+1;
 724                 /* add the 'bytes above' */
 725                 if (!start)
 726                         for (i=0; i<j; i++)
 727                                 {
 728                                 if (!BN_mod_mul(r,r,r,m,ctx))
 729                                         goto err;
 730                                 }
 731
 732                 /* wvalue will be an odd number < 2^window */
 733                 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
 734                         goto err;
 735
 736                 /* move the 'window' down further */
 737                 wstart-=wend+1;
 738                 wvalue=0;
 739                 start=0;
 740                 if (wstart < 0) break;
 741                 }
 742         ret=1;
 743 err:
 744         BN_CTX_end(ctx);
 745         for (i=0; i<ts; i++)
 746                 BN_clear_free(&(val[i]));
 747         return(ret);
 748         }
 749